二叉树的建立与遍历方法

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 #include<cmath>
 5 #include<cstring>
 6 #include<set>
 7 #include<map>
 8 #include<queue>
 9 #include<vector>
10 
11 using namespace std;
12 
13 typedef struct node{
14     char data;
15     struct node *left, *right;
16 }node, *BiTree;
17 
18 //创建一个二叉树
19 BiTree CreateBiTree(BiTree T){
20     char ch;
21     cin>>ch;
22     if (ch == '#')
23         T = NULL;
24     else {
25         T = new node;
26         if (!T)
27             exit(-1);
28         T->data = ch;
29         T->left = CreateBiTree(T->left);
30         T->right = CreateBiTree(T->right);
31     }
32     return T;
33 }
34 
35 //二叉树的先序遍历
36 void PreOrder(BiTree T){
37     if (T){
38         cout<<T->data<<" ";
39         PreOrder(T->left);
40         PreOrder(T->right);
41     }
42 }
43 
44 //二叉树的中序遍历
45 void InOrder(BiTree T){
46     if (T){
47         InOrder(T->left);
48         cout<<T->data<<" ";
49         InOrder(T->right);
50     }
51 }
52 
53 //二叉树的后序遍历
54 void PostOrder(BiTree T){
55     if (T){
56         PostOrder(T->left);
57         PostOrder(T->right);
58         cout<<T->data<<" ";
59     }
60 }
61 
62 //二叉树的层序遍历
63 void bfsOrder(BiTree T){
64     queue<BiTree> q;
65     q.push(T);
66     while(!q.empty()){
67         BiTree t = q.front();
68         cout<<t->data<<" ";
69         q.pop();
70         if (t->left != NULL) q.push(t->left);
71         if (t->right != NULL) q.push(t->right);
72     }
73 }
74 
75 int main()
76 {
77     BiTree BTree;
78     BTree = CreateBiTree(BTree);
79     PreOrder(BTree);
80     cout<<endl;
81     InOrder(BTree);
82     cout<<endl;
83     PostOrder(BTree);
84     cout<<endl;
85     bfsOrder(BTree);
86     cout<<endl;
87 
88     return 0;
89 }