必备算法之二叉树的相关操作

树的结构定义如下

1 typedef struct TNode *Position;
2 typedef Position BinTree;
3 struct TNode{
4     ElementType Data;
5     BinTree Left;
6     BinTree Right;
7 };

1、求树的高度

 1 int GetHeight( BinTree BT )
 2 {
 3     int h=0;
 4     int hl,hr;
 5     if( !BT)
 6     {
 7         h = 0;
 8     }
 9     else
10     {
11         hl = GetHeight(BT->Left);  //左子树高度
12         hr = GetHeight(BT->Right); //右子树高度
13         if( hl>hr)
14         {
15             h = hl+1;
16         }
17         else
18         {
19             h = hr+1;
20         }
21     }
22 
23     return h;
24 }

2、树的先序遍历

1 void PreorderTraversal( BinTree BT )
2 {
3     if( BT==NULL )
4         return;
5 
6     printf(" %c",BT->Data);
7     PreorderTraversal(BT->Left);
8     PreorderTraversal(BT->Right);
9 }

3、树的中序遍历

1 void InorderTraversal( BinTree BT )
2 {
3     if( BT==NULL )
4         return;
5 
6     InorderTraversal(BT->Left);
7     printf(" %c",BT->Data);
8     InorderTraversal(BT->Right);
9 }

4、树的后序遍历

1 void PostorderTraversal( BinTree BT )
2 {
3     if( BT==NULL )
4         return;
5 
6     PostorderTraversal(BT->Left);
7     PostorderTraversal(BT->Right);
8     printf(" %c",BT->Data);
9 }

5、树的层次遍历

 1 void LevelorderTraversal( BinTree BT )
 2 {
 3     if(BT==NULL)
 4         return ;
 5         
 6     BinTree T[100];
 7     int i=0,j=0;
 8     T[j++]=BT;
 9     while(i<j)
10     {
11         BinTree s=T[i];
12         printf(" %c",s->Data);
13         if(s->Left)
14             T[j++]=s->Left;
15         if(s->Right)
16             T[j++]=s->Right;
17         i++;
18     }
19 }

6.树的还原——已知先序中序

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 #include<string.h>
 4 
 5 typedef struct TNode
 6 {
 7     char data;
 8     struct TNode *lchild,*rchild;
 9 } TNode,*Tree;
10 
11 Tree CreatTree( char xian[],char zhong[],int n);
12 int GetHigh( Tree t);
13 
14 char xian[55];   //先序序列
15 char zhong[55];  //中序序列
16 int n;
17 
18 int main()
19 {
20     scanf("%d",&n);
21     scanf("%s",xian);
22     scanf("%s",zhong);
23     Tree tree = CreatTree( xian,zhong,n);
24     printf("%d",GetHigh(tree));
25     return 0;
26 }
27 
28 Tree CreatTree( char xian[],char zhong[],int n)
29 {
30     if( n==0 ) return NULL;
31     int index = 0;
32     Tree temp = (Tree) malloc(sizeof(struct TNode));
33 
34     while( index < n)
35     {
36         if( zhong[index]==xian[0]) break;
37         index ++;
38     }
39     temp->data = xian[0];
40     temp->lchild = CreatTree(xian+1,zhong,index);
41     temp->rchild = CreatTree(xian+1+index,zhong+index+1,n-index-1);
42     return temp;
43 }

树的还原——已知中序后序

 1 BinTree Creathou( char zhong[],char hou[],int n)
 2 {
 3     if( n==0 ) return NULL;
 4     int index=0;
 5     BinTree temp;
 6     temp=( BinTree)malloc(sizeof(struct Node));
 7     while( index<n)
 8     {
 9         if( zhong[index]==hou[n-1])
10             break;
11         index++;
12     }
13     temp->data = hou[n-1];
14     temp->left = Creathou( zhong,hou,index);
15     temp->right = Creathou(zhong+index+1,hou+index,n-index-1);
16     return temp;
17 }

在这个国度中，必须不停地奔跑，才能使你保持在原地。如果想要寻求突破，就要以两倍现在速度奔跑！