二叉树的构建以及遍历

一、前言

　　今天学习了下二叉树的构建以及遍历，感觉还是挺简单的。

二、树的构建

　　我们利用输入的字符串，依次是从根节点到左儿子再到右儿子，也就是根据字符如果不是'#'就创建节点返回，如果是，再创建它的左右节点，依次结束树的创建。

　　比如说我们输入一串字符串“AB#D##C##”（#代表空）

　　它的树图为：

 代码实现为：

 1 node *CreateTree()
 2 {
 3     scanf("%c",&ch);
 4     node *Tree;
 5     if(ch == '#')//空节点则返回
 6         Tree = NULL;
 7     else {
 8         Tree = new node();//c++申请空间的方法，c语言的为Tree = (node *)malloc (sizeof(node));
 9         Tree->date = ch;
10         Tree->leftChild = CreateTree();//创建左孩子节点
11         Tree->rightChild = CreateTree();//创建右孩子节点
12     }
13     return Tree;
14 }

三、树的遍历：

　　1.前序遍历：

　　所谓前序遍历，就是先从根部，走左子树，再走右子树。

　　根据画的树图可以标明顺序为

 代码实现如下：

 1 void PreTraverse(node *root)//前序遍历
 2 {
 3     if(root == NULL)
 4         return;
 5     else {
 6         printf("%c",root->date);
 7         PreTraverse(root->leftChild);
 8         PreTraverse(root->rightChild);//AB#D##C##
 9     }
10 }

　　2.中序遍历：

　　所谓中序遍历就是，先走左子树，再走根部，再走右子树。

　　根据树图不难写出顺序如下：

 　　代码实现就是在前序的情况下换下printf的位置即可

 1 void MidTraverse(node *root)//中序遍历
 2 {
 3     if(root == NULL)
 4         return;
 5     else {
 6         MidTraverse(root->leftChild);
 7         printf("%c",root->date);
 8         MidTraverse(root->rightChild);
 9     }
10 }

　　3.后序遍历：

　　后序遍历就是先走左子树，再走右子树，再走根部

　　树图为：

 　　代码改动也不大，如下：

 1 void AftTraverse(node *root)//后序遍历
 2 {
 3     if(root == NULL)
 4         return;
 5     else {
 6         AftTraverse(root->leftChild);
 7         AftTraverse(root->rightChild);
 8         printf("%c",root->date);
 9     }
10 }

4.层次遍历：

 1 int bfs(node *root)
 2 {
 3     queue  ans;
 4     int f = 0;
 5     ans.push(root);
 6     while(!ans.empty()){
 7         f++;
 8         int len = ans.size();
 9         for(int i = 1;i <= len;i++){
10             node *v = ans.front();
11             ans.pop();
12             cout << f << ',' << v->val << endl;
13             if(v->left) ans.push(v->left);
14             if(v->right) ans.push(v->right);
15         }
16     }
17     return f;//层数
18 }

四、完整的代码以及运行情况

 1 #include "bits/stdc++.h"
 2 using namespace std;
 3 struct node{
 4     char date;
 5     node *leftChild;
 6     node *rightChild;
 7 };
 8 char ch;
 9 node *CreateTree()
10 {
11     scanf("%c",&ch);
12     node *Tree;
13     if(ch == '#')//防止数组越界
14         Tree = NULL;
15     else {
16         Tree = new node();
17         Tree->date = ch;
18         Tree->leftChild = CreateTree();
19         Tree->rightChild = CreateTree();
20     }
21     return Tree;
22 }
23 void PreTraverse(node *root)//前序遍历
24 {
25     if(root == NULL)
26         return;
27     else {
28         printf("%c",root->date);
29         PreTraverse(root->leftChild);
30         PreTraverse(root->rightChild);//AB#D##C##
31     }
32 }
33 void MidTraverse(node *root)//中序遍历
34 {
35     if(root == NULL)
36         return;
37     else {
38         MidTraverse(root->leftChild);
39         printf("%c",root->date);
40         MidTraverse(root->rightChild);
41     }
42 }
43 void AftTraverse(node *root)//后序遍历
44 {
45     if(root == NULL)
46         return;
47     else {
48         AftTraverse(root->leftChild);
49         AftTraverse(root->rightChild);
50         printf("%c",root->date);
51     }
52 }
53 int main()
54 {
55     node *root;
56     root = CreateTree();
57     PreTraverse(root);
58     printf("\n");
59     MidTraverse(root);
60     printf("\n");
61     AftTraverse(root);
62     printf("\n");
63     return 0;
64 }

五、总结

　　今天是放假时间，顺便补个时长，复习了一下二叉树的构建与遍历，感觉收获了挺多的，加油！