3 二叉树的存储

3.1 顺序存储结构

顺序存储格式，只适合完全二叉树

3.1.1 定义

typedef    int  elem_type;
typedef   elem_type sq_bi_tree[100];
//给一个有100个元素，元素类型为elem_type的数组 
//重命名为 sq_bi_tree;

sq_bi_tree  bt;//定义一个有100个元素，元素类型是elem_type 的一维数组，数组名为bt;
//真的二叉树的定义

存储时如何体现逻辑关系：把任何的二叉树都 当做满二叉树填充，如果对应位置没有结点，则存储一个不可能的数值代表空

（1）完全二叉树：

方法1：在主函数外定义模板：
    在主函数里：
sq_bi_tree  bt1={1,2,3,4,5,6,7,8,9,10,11,12,13};
    bt1[0]=100;//把根节点的值修改为100
方法2：
   main()
{
    	int sq_bi_tree[100]={1,2,3,4,5,#,6};
    	 sq_bi_tree[0]=100;//把根节点的值修改为100
}

（2）非完全二叉树

sq_bi_tree  btc ={1,2,3,4,5,#,#,#,#,6,7};// #代表不可能的值
sq_bi_tree  btd={1,2,3,4,5,#,6};

最不理想的情况:只有右子树

如果k=3,只有3个结点，但需要2^3-1=7个结点空间存储该二叉树

如果k=4,只有4个结点，但需要2^4-1=15个结点空间存储该叉树

结论：顺序存储格式，只适合完全二叉树

3.2 链式存储结构

3.2.1 存储结构分析

结构b :二叉链表

结构c: 三叉链表

3.2.2 逻辑示意图

规律：含有n个结点的二叉链表中有n+1个空链域。

typedef char elem_type;
typedef struct bi_node
{
    elem_type data;
	struct bi_node *lchild;
	struct bi_node *rchild;
}bi_node,*bi_tree;//结点,树名(二叉链表的表名)

4 二叉树的遍历

4.1 概念

按照某种规定的次序，访问树的结点，使得每个结点均被访问一次，且仅被访问一次。

访问：输出结点的信息，对结点进行运算，对结点信息进行修改

4.2 实现

对二叉树进行线性化的过程。

遍历的结果 就是把 非线性结构的二叉树中 的排成一个线性序列。

根据 二叉树的递归性：把二叉树分为三个基本单元

（1）根节点（D）

（2）左子树（L）

（3）右子树®

通过限定访问顺序，依次遍历这三个基本单元，可以实现线性化

DLR ,DRL ,LDR ,LRD, RDL,RLD。

若限定自左向右的顺序：DLR,LDR,LRD

根据根被 访问的顺序：

• 先序（根）遍历(DLR),

• 中序(根)遍历(LDR)

• 后序（根）遍历(LRD)

4.3 先序遍历

4.3.1 读取顺序

4.3.2 算法步骤

如果二叉树为空，则返回
如果非空 ：DLR
  D:(1)访问根节点，打印
  L:(2)先序遍历左子树
  R:(3)先序遍历右子树

4.3.3 递归算法—DLR

void pre_order_traverse(bi_tree t)//根节点的地址
{
	if(t==NULL)//空树
		return ;//结束函数
	printf("%c",t->data);//打印根节点
	pre_order_traverse(t->lchild);
	pre_order_traverse(t->rchild);
}

4.3.4 递归过程

4.4 中序遍历（LDR）

4.4.1 读取顺序

4.4.2 算法步骤

如果二叉树为空，则返回;
如果非空 ：LDR
	L:(1)中序遍历左子树
  	D:(2)访问根节点：打印
    R:(3)中序遍历右子树

4.4.3 递归算法—LDR

void mid_order_traverse(bi_tree t)//根节点
{
	if(t==NULL)//空树
		return ;//结束函数
	mid_order_traverse(t->lchild);//中序遍历左子树
	printf("%c",t->data);//打印结点
	mid_order_traverse(t->rchild);//中序遍历右子树
}

4.4.4 递归过程—LDR

4.5 后序遍历—LRD

4.5.1 读取顺序

abcd-*+ef/-

4.5.2 算法步骤—LRD

如果二叉树为空，则返回;
如果非空 ：LRD
	L:(1)后序遍历左子树(t->lchild)
	R:(2)后序遍历右子树(t->rchild)
  	D:(3)访问根节点，打印(printf)

4.5.3 参考代码

void last_order_traverse(bi_tree t)
{
	if(t==NULL)//空树
		return ;//结束函数
	last_order_traverse(t->lchild);//后序遍历左子树
	last_order_traverse(t->rchild);//后序遍历右子树
	printf("%c",t->data);//根节点：打印当前结点
}

4.6 迭代算法-中序遍历

（1）初始化空栈S
（2）指针p指向二叉树的 根节点
（3）循环：p!=NULL || 栈S不为空 
    ·如果p为非空：push();p指向左结点
    ·如果p为空：pop()出栈, 指向右节点
                （指向右结点后：若p为空，循环结束）

int* inorderTraversal(struct TreeNode* root, int* returnSize) {
    // 含有n个结点的二叉树有n+1个空链域
    struct TreeNode **stk = malloc(sizeof(struct TreeNode *) * 201);
    int top = 0;
    struct TreeNode* cur_node = root;
    int* res = malloc(sizeof(int) * 100);
    int cnt = 0;

    // 非空树，进入循环
    // 栈中存在元素，继续循环
    while(cur_node != NULL || top > 0) {

        // find leftest最左子结点
        while(cur_node) {// 叶子结点的left为nuLL结束
            // 进栈
            stk[top++] = cur_node;
            cur_node = cur_node->left;
        }

        // 空结点不计数，--top;
        cur_node = stk[--top];// 结束循环时为null， 回退到父节点

        res[cnt++] = cur_node->val;// 保存当前结点的值-遍历结果

        // cur_node 已经无左子结点，找右子结点
        cur_node = cur_node->right;
    }

    *returnSize = cnt;
    return res;
}

5 二叉树的建立

5.1 扩展二叉树

假设要建立一个二叉树，以先序遍历（DLR）的格式ABDC建立 二叉树

扩展后：按照先序遍历的格式：重新读取

扩展后：AB#D##C##  （链式：#代表空：顺序：设置一个绝对不可能的数）

参考图：

5.2 算法步骤

先拓展二叉树：把每个结点的左右结点都补全，空用#代替
 采用先序遍历的读法，写出序列 
（1）依次扫描扩展后的字符序列，存入ch
（2）如果 ch== #  ,则该二叉树为空树，即t=NULL
     如果ch!= # ,则进行以下操作
     		{
            	申请新结点bi_node  new;
            	设置新结点的数据域  new->data=ch;
            	递归创建新结点的左子树；
            	递归创建新结点的右子树
     		}

示例1：

扩展后：AB#D##C##  
bi_tree  creat_bi_tree(void)
{
    char  ch;
    bi_tree t;
    bi_node new;
    ch=getchar();
    if(ch=='#')
    {
        t=NULL;
    }
    else
    {
        new=(bi_tree)malloc(sizeof(bi_node));
        t=new;
        t->data=ch;
       	t->lchild=creat_bi_tree();
        t->rchild=creat_bi_tree();
    }
    return t
}

5.3 参考代码

黑板上的表达式扩展后的先序遍历：
-+a##*b##-c##d##/e##f##

6 统计结点个数

6.1 算法分析

n=0  空树  结点个数为0
n>0 非空树，结点总数= 左子树的结点个数+右子树的结点个数+1

6.2 示例：

集体夏游去爬山，一共有n个台阶。爬楼梯的方式有两种
一次跨一个台阶，或者一次跨两个台阶
问：我要爬完n个台阶，有多少种爬法？
n=1  1
n=1  1+1  2  2种
n=3  1+2  2+1 1+1+1
int func(int n)
{
	if(n==1 || n==2)
	return n;
	else
	return func(n-1)+func(n-2);
}

6.3 参考代码

int count_node(bi_tree t)
{
	if(t==NULL)
		return 0;
    else
	return count_node(t->lchild)+count_node(t->rchild)+1;
}

练习：

实现二叉树的建立，和先序打印(三选一 )

(打印图二(b))

先序遍历：
 ABC##DE#G##F###