数据结构之二叉树遍历

最近学习了数据结构关于树的一些知识，发现很多的面试题考的都是树的非递归遍历，今天就总结了一下，代码如下所示：
  1 #include<iostream>
  2 #include<queue>
  3 #include<stack> 
  4 using namespace std;
  5 
  6 typedef char status;
  7 int index = 0; 
  8 status str[24] ="A#B#C#D##";//ABC##DE#G##F###   ABDH#K###E##CFI###G#J##   ABCD#####   四组测试数据
  9 typedef struct treeNode{
 10 　　status data;
 11 　　treeNode *lchild;
 12 　　treeNode *rchild; 
 13 }treeNode,*treelink;
 14 
 15 /*初始化树*/
 16 void Init(treelink *t){
 17 *t = NULL;
 18 }
 19 /*创建二叉树*/
 20 void Create_tree(treelink *t){
 21 　　status ch;
 22 　　ch = str[index++];
 23 
 24 　　if(ch=='#'){
 25 　　　　(*t) = NULL;
 26 　　}else{
 27 　　　　(*t) = (treelink)malloc(sizeof(treeNode));
 28 　　　　if(!*t)exit(0);
 29 　　　　(*t)->data = ch;
 30 　　　　Create_tree(&(*t)->lchild);
 31 　　　　Create_tree(&(*t)->rchild);
 32 　　}
 33 }
 34 
 35 /*前序遍历递归实现*/
 36 void Preordertraverse(treelink t){
 37 　　if(!t)return ;
 38 　　　　cout<<t->data;
 39 　　Preordertraverse(t->lchild);
 40 　　Preordertraverse(t->rchild);
 41 }
 42 /*前序遍历非递归实现*/
 43 void Preordertraverse1(treelink t){
 44 　　stack<treelink> s;
 45 　　treelink p;
 46 　　p = t;
 47 　　while(!s.empty() || p!= NULL){
 48 　　　　while(p!=NULL){
 49 　　　　　　cout<<p->data;
 50 　　　　　　s.push(p);
 51 　　　　　　p=p->lchild;
 52 　　　　}
 53 　　　　if(!s.empty()){
 54 　　　　　　p = s.top();
 55 　　　　　　s.pop();
 56 　　　　　　p = p->rchild; 
 57 　　　　}
 58 　　}
 59 }
 60 
 61 
 62 /*中序遍历递归实现*/
 63 void Inordertraverse(treelink t){
 64 　　if(!t)return ;
 65 　　Inordertraverse(t->lchild);
 66 　　cout<<t->data;
 67 　　Inordertraverse(t->rchild);
 68 }
 69 /*中序遍历非递归实现*/
 70 void Inordertraverse1(treelink t){
 71 　　stack<treelink> s;
 72 　　treelink p;
 73 　　p = t;
 74 　　while(!s.empty() || p!= NULL){
 75 　　　　while(p!=NULL){
 76 　　　　　　s.push(p);
 77 　　　　　　p=p->lchild;
 78 　　　　}
 79 　　　　if(!s.empty()){
 80 　　　　　　p = s.top();
 81 　　　　　　cout<<p->data;
 82 　　　　　　s.pop();
 83 　　　　　　p = p->rchild; 
 84 　　　　}
 85 　　}
 86 }
 87 
 88 /*后序遍历递归实现*/
 89 void Postordertraverse(treelink t){
 90 　　if(!t)return ;
 91 　　Postordertraverse(t->lchild);
 92 　　Postordertraverse(t->rchild);
 93 　　cout<<t->data;
 94 }
 95 /*后序遍历非递归实现*/
 96 void Postordertraverse1(treelink t){
 97 　　stack<treelink> s;
 98 　　treelink cur,pre = NULL;
 99 　　s.push(t);
100 　　while(!s.empty()){
101 　　　　cur = s.top();
102 　　　　if((cur->lchild == NULL && cur->rchild == NULL) || (pre!=NULL && (pre == cur->lchild || pre == cur->rchild))){
103 　　　　　　cout<<cur->data;
104 　　　　　　s.pop();
105 　　　　　　pre=cur;
106 　　　　}else{
107 　　　　　　if(cur->rchild != NULL){
108 　　　　　　　　s.push(cur->rchild);
109 　　　　　　}
110 　　　　　　if(cur->lchild != NULL){
111 　　　　　　　　s.push(cur->lchild);
112 　　　　　　} 
113 　　　　}
114 　　}
115 }
116 /*层次遍历非递归实现*/
117 void levelorder(treelink t){
118 　　queue<treelink> qu;
119 　　qu.push(t);
120 　　do{
121 　　　　treelink n = qu.front();
122 　　　　cout<<n->data;
123 　　　　qu.pop();
124 　　　　if(n->lchild!=NULL){
125 　　　　　　qu.push(n->lchild);
126 　　　　}
127 　　　　if(n->rchild!=NULL){
128 　　　　　　qu.push(n->rchild);
129 　　　　}
130 　　}while(!qu.empty());
131 }
132 /*分层打印*/
133 void level(treelink t){
134 　　queue<treelink> qu;
135 　　treelink m,n;
136 　　treelink p = (treelink)malloc(sizeof(treeNode));
137 　　p->data = '*'; 
138 　　qu.push(t);
139 　　qu.push(p);
140 　　do{
141 　　　　n = qu.front();
142 　　　　qu.pop();
143 　　　　if( n && n->data == '*'){
144 　　　　　　m = qu.back(); //可以使用qu.size()函数判断队里元素是否为1（*）如果是*的话就break 
145 　　　　　　if(n == m)break;
146 　　　　　　qu.push(p);
147 　　　　　　cout<<endl;
148 　　　　　　continue;
149 　　　　}else{
150 　　　　　　cout<<n->data;
151 　　　　}    
152 　　　　if(n->lchild != NULL){
153 　　　　　　qu.push(n->lchild);
154 　　　　}
155 　　　　if(n->rchild!=NULL){
156 　　　　　　qu.push(n->rchild);
157 　　　　}
158 　　}while(!qu.empty());
159 } 
160 
161 
162 /*求树的深度*/ 
163 int Tdepth(treelink t){
164 　　if(!t)return 0;
165 　　int ldepth = Tdepth(t->lchild);
166 　　int rdepth = Tdepth(t->rchild);
167 　　return 1 + max(ldepth,rdepth); 
168 }
169 /*递归实现求树指定层的节点*/
170 void printatlevel(treelink t,int level){
171 　　if(!t || level <0){
172 　　　　return ;
173 　　}
174 　　if(level == 0){
175 　　　　cout<<t->data;
176 　　}
177 
178 　　printatlevel(t->lchild,level - 1);
179 　　printatlevel(t->rchild,level - 1);
180 }
181 /*分层打印二叉树*/
182 void printbylevel(treelink t){
183 　　int i;
184 　　int level = Tdepth(t);
185 　　for(i = 0;i<level;i++){
186 　　　　printatlevel(t,i);
187 　　　　cout<<endl;
188 　　}
189 }
190 int main(){
191 　　treelink t;
192 　　Init(&t);
193 　　Create_tree(&t);    
194 　　cout<<endl;
195 　　Postordertraverse1(t);
196 　　/*
197 　　Preordertraverse(t);
198 　　cout<<endl;
199 　　Preordertraverse1(t);
200 　　cout<<endl;
201 　　Inordertraverse(t);
202 　　cout<<endl;
203 　　Inordertraverse1(t);
204 　　cout<<endl;
205 　　Postordertraverse(t);
206 　　cout<<endl;
207 　　Postordertraverse1(t);
208 　　cout<<endl;
209 　　levelorder(t);
210 　　cout<<endl;
211 　　printbylevel(t);
212 　　cout<<endl;
213 　　level(t);*/
214 　　return 0;
215 }