二叉树各种相关操作(建立二叉树、前序、中序、后序、求二叉树的深度、查找二叉树节点，层次遍历二叉树等）（C语言版)

1 typedef struct TreeNode{
2     int data;
3     struct TreeNode *left;
4     struct TreeNode *right; 
5 }TreeNode;

 1 TreeNode *creatRoot(){
 2     TreeNode * root =(TreeNode *)malloc(sizeof(TreeNode));
 3     if(NULL==root){
 4         printf("CreatRoot is failing!
");
 5         return NULL;
 6     }
 7     root->left=NULL;
 8     root->right=NULL;
 9     printf("Input the data of root!
");
10     scanf("%d",&root->data);
11     printf("Root created!
");
12     return root;
13 } 

1 void clearTree(TreeNode * root){
2     if(root){
3         clearTree(root->left);
4         clearTree(root->right);
5         free(root);
6     }
7 }

 1 void addSubTreeNode(TreeNode* root,TreeNode*node,int select){
 2     if(NULL==root){
 3         printf("Root is NULL
");
 4         return ;
 5     }
 6     switch(select){
 7         case 1:
 8             if(root->left){
 9                 printf("The root has left subtree!
");
10                 return ;
11             }else{
12                 root->left=node;
13                 break;
14             }
15         case 2:
16                 if(root->right){
17                 printf("The root has right subtree!
");
18                 return ;
19             }else{
20                 root->right=node;
21                 break;
22             }
23         default:
24             printf("The input of select is wrong!
");
25     }
26 }

 1 void DLR(TreeNode * root){
 2     if(NULL==root)
 3     return;
 4     printf("The First root input %d
",root->data);
 5     DLR(root->left);
 6     DLR(root->right);
 7 }
 8 
 9 void LDR(TreeNode * root){
10     if(NULL==root)
11     return;
12     LDR(root->left);
13     printf("The Middle root input %d
",root->data);
14     LDR(root->right);
15 }
16 
17 void LRD(TreeNode * root){
18     if(NULL==root)
19     return;
20     LRD(root->left);
21     LRD(root->right);
22     printf("The Last root input %d
",root->data);
23 }

 1 int lengthTree(TreeNode *root){
 2     int lenLeft,lenRight;
 3     if(NULL==root)
 4     return 0;
 5     else{
 6         lenLeft=lengthTree(root->left);
 7         lenRight=lengthTree(root->right);
 8         if(lenLeft<lenRight)
 9         return lenRight+1;
10         else
11         return lenLeft+1;
12     }
13 }

 1 TreeNode *treeFind(TreeNode *node,int number){
 2     TreeNode *p;
 3     if(NULL==node)
 4     return NULL;
 5     else{
 6         if(node->data==number){
 7             return node;
 8         }else{
 9             if(p=treeFind(node->left,number)){
10                 printf("Parent found!
");
11                 return p;
12             }
13             
14             else if(p=treeFind(node->right,number)){
15                 printf("Parent found!
");
16                 return p;
17             }
18             else
19             return NULL;
20         }
21     }
22 }

 1 void addNode(TreeNode *root){
 2     TreeNode *node,*parent;
 3     int number,select;
 4     printf("Please input the parent data!
");
 5     scanf("%d",&number);
 6     parent=treeFind(root,number);
 7     if(NULL==parent){
 8         printf("parent is not found!
");
 9         return ;
10     }
11             printf("Please choice the operation: 0 Exit; 1 insert left subtree; 2 insert right subtree!
");
12             scanf("%d",&select);
13             if(select==0)
14             return ;
15             if(node=(TreeNode*)malloc(sizeof(TreeNode))){
16                 printf("Please input the data of BinTreeData that you want to insert!
");
17                 scanf("%d",&node->data);
18                 node->left=NULL;
19                 node->right=NULL;
20                 switch(select){
21                     case 1:
22                         addSubTreeNode(parent,node,1);
23                         break;
24                     case 2:
25                         addSubTreeNode(parent,node,2);
26                         break;
27                 }
28             }
29 }

 1 void levelFind(TreeNode * root){
 2     TreeNode *node;
 3     TreeNode *Queue[MAX];
 4     int head,tail;
 5     head=tail=0;
 6     if(root==NULL){
 7         printf("Queue is empty!
");
 8         return ;
 9     }
10     if((tail+1)%MAX!=head)
11         Queue[tail++]=root;
12     else
13         printf("Queue is full!
");
14     if(head!=tail)
15         node=Queue[head++];
16     else
17         printf("Queue is empty!
");
18     printf("The bintree level find is: 
");
19     while(NULL!=node){
20         printf("%d  ",node->data);
21         if(node->left!=NULL){
22             Queue[tail++]=node->left;
23         }
24         if(node->right!=NULL){
25             Queue[tail++]=node->right;
26         }
27         if(head==tail){
28             printf("Queue is empty!
");
29             return;
30         }
31         node=Queue[head++];
32     }
33 }

 1 int main(){
 2     TreeNode *root=NULL;
 3     int n;
 4     do{
 5         printf("1 set root, 2 addNode, 3 the First root input, 4 the Middle root input, 5 the last root input, 6 according to level find, 7 caculate the depth, 0 exit!
");
 6         scanf("%d",&n);
 7         switch(n){
 8             case 0:
 9                 break;
10             case 1:
11                 if(NULL==root)
12                 root=creatRoot();
13                 else
14                 printf("The root is exist!
");
15                 break;
16             case 2:
17                 addNode(root);
18                 break;
19             case 3:
20                 DLR(root);
21                 break;
22             case 4:
23                 LDR(root);
24                 break;
25             case 5:
26                 LRD(root);
27                 break;
28             case 6:
29                 levelFind(root);
30                 break;
31             case 7:
32             printf("the depth of tree is %d
",lengthTree(root));
33                 break;
34         }
35     }while(n!=0);
36     clearTree(root);
37     printf("Tree are cleared all!
");
38     getch();
39     return 0;
40     
41 }