数据结构-5-二叉树的实现以及递归遍历的实现

一开始学的时候写的是递归遍历。。。好入门啊！！1真的！！！比非递归遍历树理解起来感觉简单多了！！！

二叉树是一种树形结构。每个节点至多只有两棵子树。其子树有左右之分，次序是不能任意颠倒的。

先说一下树的建立。

用一个结构体来表示二叉树的节点。

节点包括其一个数据域和left、right两个指针域分别指向左右子树节点的地址。

1 typedef struct node
2 {
3     int data;
4     struct node *left;
5     struct node *right;
6 } BTree;

二叉树的构造：

传入根节点，从左子树开始构造。

控制条件为当输入的x大于0，一旦小于或者等于零，该节点为空。

若大于0，将树节点中指针指向该地址空间。需要判断是否分配内存成功，若失败返回0。

将输入的x存入到tp指向结点的数据域内。

指针一直向左走，递归调用种树函数，左边走完之后向右走。（顺序与前序遍历一致）

 1 Status BTreeCreate (BTree **tp)
 2 {
 3     //从左子数开始构造
 4     int x;
 5     scanf("%d",&x);
 6     if(x<=0)
 7     {
 8         *tp=NULL;
 9         return 0;
10     }
11     *tp=(BTree*)malloc(sizeof(BTree));//将树节点中指针指向该地址空间
12     if(tp==NULL) return 0;//内存分配失败
13     (*tp)->data=x;
14     BTreeCreate(&((*tp)->left));
15     BTreeCreate(&((*tp)->right));
16     return OK;
17 }

三种递归遍历的实现:

前序遍历：从根开始一直向左走，左边走完了向右走，右边也读完了就返回上一个未走完的结点继续向右走…… 根→左→右

中序遍历：从根开始向左走到最左读出数据后又往回走一个结点，向右结点走（走到最左）……天啊我的表达能力实在不行。。。。左→根→右

后序遍历：把左边的读完了就读右边的，左边大子树读完了就读右边的大子树，依然是把左边的读完了就读右边的，最后再读根结点。左→右→根

递归遍历的算法比较好理解，代码也比较简洁。三种都基本长一个样，不同的就是读数据输出的那一条语句与递归调用遍历函数的两个语句次序不同。

 1 void PreOrder(BTree *tree)//前序遍历，先根节点，再左子树后右子树
 2 {
 3     if(tree==NULL)
 4     {
 5         return ;
 6     }
 7     printf("%d ",tree->data);
 8     PreOrder(tree->left);
 9     PreOrder(tree->right);
10 }
11 void MidOrder(BTree *tree)
12 {
13     if(tree==NULL)
14     {
15         return ;
16     }
17     MidOrder(tree->left);
18     printf("%d ",tree->data);
19     MidOrder(tree->right);
20 }
21 void PostOrder(BTree *tree)
22 {
23     if(tree==NULL)
24     {
25         return ;
26     }
27     PostOrder(tree->left);
28     PostOrder(tree->right);
29     printf("%d ",tree->data);
30 }

求二叉树的深度：

这里也是用了递归调用，一开始设定树的深度为1（只要不为空就为1）。递归调用函数通过遍历树（每走一个点深度+1）求出左右子树的深度，最后返回树的深度比较大的值即为树的深度。

1 int TreeDepth(BTree *tree)//求二叉树的深度
2 {
3     if(tree==NULL)//如果tree为NULL 深度为0 ，也是递归返回的条件。
4      return 0;
5     int left=1,right=1;//如果tree不为NULL则深度是至少为1的 所以right和left为1
6     left+=TreeDepth(tree->left);//求左子树的深度
7     right+=TreeDepth(tree->right);//求右子树的深度
8     return left>right?left:right;//返回深度比较大的那一个
9 }

完整的代码实现：

  1 #include<stdio.h>
  2 #include<stdlib.h>
  3 #include<iostream>
  4 using namespace std;
  5 #define TRUE 1
  6 #define FALSE 0
  7 #define OK 1
  8 #define ERROR 0
  9 #define OVERFLOW -2
 10 typedef int Status;
 11 typedef int ElemType;
 12 
 13 typedef struct node
 14 {
 15     int data;
 16     struct node *left;
 17     struct node *right;
 18 } BTree;
 19 
 20 Status BTreeCreate (BTree **tp)
 21 {
 22     //从左子数开始构造
 23     int x;
 24     scanf("%d",&x);
 25     if(x<=0)
 26     {
 27         *tp=NULL;
 28         return 0;
 29     }
 30     *tp=(BTree*)malloc(sizeof(BTree));//将树节点中指针指向该地址空间
 31     if(tp==NULL) return 0;//内存分配失败
 32     (*tp)->data=x;
 33     BTreeCreate(&((*tp)->left));
 34     BTreeCreate(&((*tp)->right));
 35     return OK;
 36 }
 37 void PreOrder(BTree *tree)//前序遍历，先根节点，再左子树后右子树
 38 {
 39     if(tree==NULL)
 40     {
 41         return ;
 42     }
 43     printf("%d ",tree->data);
 44     PreOrder(tree->left);
 45     PreOrder(tree->right);
 46 }
 47 void MidOrder(BTree *tree)
 48 {
 49     if(tree==NULL)
 50     {
 51         return ;
 52     }
 53     MidOrder(tree->left);
 54     printf("%d ",tree->data);
 55     MidOrder(tree->right);
 56 }
 57 void PostOrder(BTree *tree)
 58 {
 59     if(tree==NULL)
 60     {
 61         return ;
 62     }
 63     PostOrder(tree->left);
 64     PostOrder(tree->right);
 65     printf("%d ",tree->data);
 66 }
 67 
 68 
 69 void BTreeSetNULL(BTree *tree)//做完实验就记得释放空间。。节约内存从我做起（笑）
 70 {
 71     if(tree==NULL)
 72     {
 73         return ;
 74     }
 75     BTreeSetNULL(tree->left);
 76     BTreeSetNULL(tree->right);
 77     free(tree);
 78 }
 79 int TreeDepth(BTree *tree)//求二叉树的深度
 80 {
 81     if(tree==NULL)//如果tree为NULL 深度为0 ，也是递归返回的条件。
 82      return 0;
 83     int left=1,right=1;//如果tree不为NULL则深度是至少为1的 所以right和left为1
 84     left+=TreeDepth(tree->left);//求左子树的深度
 85     right+=TreeDepth(tree->right);//求右子树的深度
 86     return left>right?left:right;//返回深度比较大的那一个
 87 }
 88 int main()
 89 {
 90     BTree *tree;
 91     cout<<"Create binary tree:
"<<endl;
 92     BTreeCreate(&tree);
 93 
 94     printf("Pre Order:
");
 95     PreOrder(tree);
 96     printf("
");
 97 
 98     printf("Mid Order:
");
 99     MidOrder(tree);
100     printf("
");
101 
102     printf("Post Order:
");
103     PostOrder(tree);
104     printf("
");
105 
106     cout<<"The depth of the tree is"<<TreeDepth(tree)<<endl;
107 
108     BTreeSetNULL(tree);
109 
110 
111 
112     return 0;
113 }