二叉树的常见操作

【输出二叉树中的叶子结点】

无论前序、中序、后序遍历，叶子结点的输出顺序都是一样的吗？？都是一样的，输出顺序为：从树的左边到右边叶子！！在二叉树的遍历算法中增加检测结点的“左右子树是否都为空”。

 1 void PreOrderPrintLeaves(BinTree Bt)
 2 {
 3     if(Bt)
 4     {
 5         if(Bt->Left == NULL && Bt->Right == NULL)
 6             printf("%c ", Bt->Data);
 7         PreOrderPrintLeaves(Bt->Left);
 8         PreOrderPrintLeaves(Bt->Right);
 9     }
10 }
11 
12 void InOrderPrintLeaves(BinTree Bt)
13 {
14     if(Bt)
15     {
16         InOrderPrintLeaves(Bt->Left);
17         if(Bt->Left == NULL && Bt->Right == NULL)
18             printf("%c ", Bt->Data);
19         InOrderPrintLeaves(Bt->Right);
20     }
21 }
22 
23 void PostOrderPrintLeaves(BinTree Bt)
24 {
25     if(Bt)
26     {
27         PostOrderPrintLeaves(Bt->Left);
28         PostOrderPrintLeaves(Bt->Right);
29         if(Bt->Left == NULL && Bt->Right == NULL)
30             printf("%c ", Bt->Data);
31     }
32 }

【求二叉树的叶子结点数】

1 int BinTreeGetLeaves(BinTree Bt)
2 {
3     if(Bt == NULL)
4         return 0;
5     if(Bt->Left == NULL && Bt->Right == NULL)
6         return 1;
7     else
8         return BinTreeGetLeaves(Bt->Left) + BinTreeGetLeaves(Bt->Right);
9 }

【求二叉树的高度】

 1 int PostOrderGetHeight(BinTree Bt)
 2 {
 3     int HL, HR, MaxH;
 4 
 5     if(Bt)
 6     {
 7         HL = PostOrderGetHeight(Bt->Left);
 8         HR = PostOrderGetHeight(Bt->Right);
 9         MaxH = (HL > HR) ? HL : HR;
10         return (MaxH + 1);
11     }
12     else
13     {
14         return 0;
15     }
16 }

【由两种遍历序列确定二叉树】

已知三种遍历中的任意两种遍历序列，能否唯一确定一棵二叉树呢？？必须要有中序遍历才行！！

1、先序和中序遍历序列来确定一棵二叉树？？

根据先序遍历序列第一个结点确定根结点；
根据根结点在中序遍历序列中分割出左右两个子序列；
对左子树和右子树分别递归使用相同的方式继续分解；

 1 struct node
 2 {
 3     char data;
 4     struct node *lt, *rt;
 5 };
 6 
 7 // 用先序序列和中序序列建立二叉树
 8 struct node *create_by_pre_and_mid(int n, char *pre, char *mid)
 9 {
10     struct node *root;
11     int i;
12 
13     if(n==0)
14         return NULL;
15 
16     root=(struct node *)malloc(sizeof(struct node));
17     root->data=pre[0];
18 
19     for(i=0;i<n;i++) // 寻找左右子树的元素
20         if(pre[0]==mid[i])
21             break;
22 
23     root->lt = create_by_pre_and_mid(i, pre+1, mid); // 建立左子树
24     root->rt = create_by_pre_and_mid(n-i-1, pre+i+1, mid+i+1); // 建立右子树
25 
26     return root;
27 }

2、后序和中序遍历序列来确定一棵二叉树？？

根据后序遍历序列最后一个结点确定根结点；
根据根结点在中序遍历序列中分割出左右两个子序列；
对左子树和右子树分别递归使用相同的方式继续分解；

 1 // 用后序序列和中序序列建立二叉树
 2 struct node *create_by_post_and_mid(int n, char *post, char *mid)
 3 {
 4     struct node *root;
 5     int i;
 6 
 7     if(n==0)
 8         return NULL;
 9 
10     root=(struct node *)malloc(sizeof(struct node));
11     root->data=post[n-1];
12 
13     for(i=0;i<n;i++) // 寻找左右子树的元素
14         if(post[n-1]==mid[i])
15             break;
16 
17     root->lt = create_by_post_and_mid(i, post, mid); // 建立左子树
18     root->rt = create_by_post_and_mid(n-i-1, post+i, mid+i+1); // 建立右子树
19 
20     return root;
21 }