二叉树的基本操作——遍历

最近在看数据结构看到树这一部分。二叉树是树的最重要的一部分，而二叉树的遍历又是对二叉树进行操作最基本的部分。小弟有些懒，懒得敲代码，导致学了这么久，也没真正自己写过二叉树的遍历部分。今天不过来，大部分代码都是参考别人的。留给自己以后看

  1 #include <iostream>
  2 #include <stack>
  3 #include<queue>
  4 using namespace std;
  5 
  6 
  7 typedef char Elemtype;
  8 typedef struct BiNode{
  9 Elemtype data;
 10 BiNode* lchild;
 11 BiNode* rchild;
 12 }BiTnode,*BiTree;
 13 
 14 int CreatBiTree(BiTree& T)
 15 {
 16 char data;
 17 cin>>data;
 18 if (data == '#')
 19 T = NULL;
 20 else
 21 {
 22 T = new BiTnode;
 23 T->data = data;
 24 CreatBiTree(T->lchild);
 25 CreatBiTree(T->rchild);
 26 }
 27 return 0;
 28 }
 29 
 30 inline void visit(BiTree T)
 31 {
 32 if (T->data != '#')
 33 cout << T->data;
 34 }
 35 ////递归算法进行遍历
 36 void PreOrderTraversr(BiTree T)
 37 {
 38 if (T != NULL)
 39 {
 40 visit(T);
 41 PreOrderTraversr(T->lchild);
 42 PreOrderTraversr(T->rchild);
 43 }    
 44 }
 45 
 46 void InOrderTraversr(BiTree T)
 47 {
 48 if (T != NULL)
 49 {
 50 InOrderTraversr(T->lchild);
 51 visit(T);
 52 InOrderTraversr(T->rchild);
 53 }
 54 }
 55 
 56 void PosOrderTraversr(BiTree T)
 57 {
 58 if (T != NULL)
 59 {
 60 PosOrderTraversr(T->lchild);
 61 PosOrderTraversr(T->rchild);
 62 visit(T);
 63 }
 64 }
 65 /////非递归遍历
 66 void PreOrder2(BiTree T)
 67 {
 68 stack<BiTree> stackBi;
 69 BiTree p = T;
 70 while (p || !stackBi.empty())
 71 {
 72 if (p)
 73 {
 74 visit(p);
 75 stackBi.push(p);
 76 p = p->lchild;
 77 }
 78 else
 79 {
 80 p = stackBi.top();
 81 stackBi.pop();
 82 p = p->rchild;
 83 }
 84 }
 85 }
 86 
 87 void InOrder2(BiTree T)
 88 {
 89 stack<BiTree> stackBi;
 90 BiTree p = T;
 91 while(p || !stackBi.empty())
 92 {
 93 if (p)
 94 {
 95 stackBi.push(p);
 96 p = p->lchild;
 97 }
 98 else
 99 {
100 p = stackBi.top();
101 visit(p);
102 stackBi.pop();
103 p = p->rchild;
104 }
105 }
106 
107 }
108 
109 //非递归后序遍历二叉树
110 typedef struct BiTNodePost{ 
111 BiTree biTree; 
112 char tag; 
113 }BiTNodePost,*BiTreePost;
114 
115 void PosOrder2(BiTree T)
116 {
117 stack<BiTreePost> stackBi;
118 BiTree p = T;
119 BiTreePost BT;
120 while(p || !stackBi.empty())
121 {
122 while(p)
123 {
124 BT = new BiTNodePost;
125 BT->biTree = p;
126 BT->tag = 'L';
127 stackBi.push(BT);
128 p = p->lchild;
129 }
130 while (!stackBi.empty() && (stackBi.top())->tag =='R')
131 {
132 BT = stackBi.top(); 
133 //退栈 
134 stackBi.pop(); 
135 visit(BT->biTree); 
136 }
137 if (!stackBi.empty())
138 {
139 BT = stackBi.top();
140 BT->tag = 'R';
141 p = BT->biTree;
142 p = p->rchild;
143 }
144 
145 }
146 
147 }
148 ////层次遍历二叉树
149 void LevelOrder(BiTree T)
150 {
151 BiTree p = T;
152 queue<BiTree> queBi;
153 if (p)
154 queBi.push(p);
155 while (!queBi.empty())
156 {
157 BiTree q = queBi.front();
158 visit(q);
159 queBi.pop();
160 if (q->lchild)
161 queBi.push(q->lchild);
162 if (q->rchild)
163 queBi.push(q->rchild);
164 }
165 }
166 
167 int main()
168 {
169 BiTree T;
170 CreatBiTree(T);
171 cout<<"递归先序遍历：";
172 PreOrderTraversr(T);
173 cout<<"递归中序遍历：";
174 InOrderTraversr(T);
175 cout<<"递归后序遍历";
176 PosOrderTraversr(T);
177 cout<<endl;
178 
179 cout<<"非递归先序遍历：";
180 PreOrder2(T);
181 cout<<"非递归中序遍历：";
182 InOrder2(T);
183 cout<<"非递归后序遍历";
184 PosOrder2(T);
185 cout <<endl;
186 cout<<"层次遍历：";
187 LevelOrder(T);
188 
189 
190 return 0;
191 }

秒客网

二叉树的基本操作——遍历

相关文章