二叉树的创建与遍历

二叉树的创建，递归遍历，非递归遍历，直接看代码

#include<iostream>
#include<stack>
using namespace std;

//结构体
typedef struct Node
{ char data; Node *lchild; Node *rchild;
}Node, *Tree;

//创建一个结点
Node *CreateNode()
{ Node*p = new(nothrow)(Node); if(p==NULL) { exit(-1); } memset(p, 0, sizeof(Node)); return p;
}

//创建一棵二叉树
Node* CreateTree(char *&s)
{ if(s==NULL) { return NULL; } Node*p =NULL; if(*s != '$') { p =  CreateNode(); p->data = *s; p->lchild = CreateTree(++s); p->rchild = CreateTree(++s); } return p;
}

//先序
void preorder(Node *root)
{ if(root != NULL) { cout<<root->data<<" "; preorder(root->lchild   ); preorder(root->rchild); }
}
//后序
void back(Node*p)
{ if(p) { back(p->lchild); back(p->rchild); cout<<p->data<<" "; }
}

//后序非递归遍历
void Back(Node *root)
{ if(root==NULL) { return ; } stack<Node*>s; Node*cur=NULL; Node*pre =NULL; cur = root; s.push(cur); while(!s.empty()) { cur = s.top(); if((cur->lchild==NULL && cur->rchild==NULL) || (pre !=NULL &&(pre==cur->lchild || pre==cur->rchild))) {//肯定先访问右孩子，在访问左孩子，因为入栈是先右孩子再左孩子； //我认为主要是防止只有左孩子，或只有右孩子； cout<<cur->data<<" "; pre = cur; s.pop(); } else { if(cur->rchild != NULL) { s.push(cur->rchild); } if(cur->lchild != NULL) { s.push(cur->lchild); } } }
}

//中序递归遍历
void Inorder(Node*root)
{ if(root != NULL) { Inorder(root->lchild); cout<<root->data<<" "; Inorder(root->rchild); }
} //非递归先序遍历
void Pre2(Node*root)
{ if(root == NULL) { return ; } stack<Node*>s; Node* p =root; while(p !=NULL || !s.empty() ) { while(p !=NULL) { s.push(p); cout<<p->data<<" "; p=p->lchild ; } if(!s.empty()) { p=s.top(); s.pop(); p=p->rchild; } }
}

//费递归中序遍历
void _Inorder(Node*root)
{ if(root ==NULL) { return ; } stack<Node*>s; Node*p = root; while(p !=NULL || !s.empty()) { while(p!=NULL) { s.push(p); p=p->lchild; } if(!s.empty()) { p=s.top(); s.pop(); cout<<p->data<<" "; p=p->rchild; } }
}


int main()
{ char *s="fdba$$c$$e$$g$ih$$j$$"; Node*root = CreateTree(s); back(root); cout<<endl; preorder(root); cout<<endl; Pre2(root); cout<<endl; Inorder(root); cout<<endl; Back(root); cout<<endl; _Inorder(root); cout<<endl; return 0;
}


  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
  
58
  
59
  
60
  
61
  
62
  
63
  
64
  
65
  
66
  
67
  
68
  
69
  
70
  
71
  
72
  
73
  
74
  
75
  
76
  
77
  
78
  
79
  
80
  
81
  
82
  
83
  
84
  
85
  
86
  
87
  
88
  
89
  
90
  
91
  
92
  
93
  
94
  
95
  
96
  
97
  
98
  
99
  
100
  
101
  
102
  
103
  
104
  
105
  
106
  
107
  
108
  
109
  
110
  
111
  
112
  
113
  
114
  
115
  
116
  
117
  
118
  
119
  
120
  
121
  
122
  
123
  
124
  
125
  
126
  
127
  
128
  
129
  
130
  
131
  
132
  
133
  
134
  
135
  
136
  
137
  
138
  
139
  
140
  
141
  
142
  
143
  
144
  
145
  
146
  
147
  
148
  
149
  
150
  
151
  
152
  
153
  
154
  
155
  
156
  
157
  
158
  
159
  
160
  
161
  
162
  
163
  
164
  
165
  
166
  
167
  
168
  
169
  
170
  
171
  
172
  
173
  
174
  
175
  
176
  
177
  
178
  
179
  
180
  
181
  
182
  
183
  
184
  
185
  
186
 

文章来源: blog.csdn.net，作者：IM-STONE，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/doubleintfloat/article/details/52398872