1. #include<iostream>   
2. #include<stack>   
3. #include<queue>   
4. using namespace std; 
5.  
6. //二叉树结点   
7. typedef struct BiTNode{ 
8.     //数据   
9.     char data; 
10.     //左右孩子指针   
11.     struct BiTNode *lchild,*rchild; 
12. }BiTNode,*BiTree; 
13.  
14. //按先序序列创建二叉树   
15. int CreateBiTree(BiTree &T){ 
16.     char data; 
17.     //按先序次序输入二叉树中结点的值（一个字符），‘#’表示空树   
18.     scanf("%c",&data); 
19.     if(data == '#'){ 
20.         T = NULL; 
21.     } 
22.     else{ 
23.         T = (BiTree)malloc(sizeof(BiTNode)); 
24.         //生成根结点   
25.         T->data = data; 
26.         //构造左子树   
27.         CreateBiTree(T->lchild); 
28.         //构造右子树   
29.         CreateBiTree(T->rchild); 
30.     } 
31.     return 0; 
32. } 
33. //输出   
34. void Visit(BiTree T){ 
35.     if(T->data != '#'){ 
36.         printf("%c ",T->data); 
37.     } 
38. } 
39. //先序遍历   
40. void PreOrder(BiTree T){ 
41.     if(T != NULL){ 
42.         //访问根节点   
43.         Visit(T); 
44.         //访问左子结点   
45.         PreOrder(T->lchild); 
46.         //访问右子结点   
47.         PreOrder(T->rchild); 
48.     } 
49. } 
50. //中序遍历     
51. void InOrder(BiTree T){   
52.     if(T != NULL){   
53.         //访问左子结点     
54.         InOrder(T->lchild);   
55.         //访问根节点     
56.         Visit(T);   
57.         //访问右子结点     
58.         InOrder(T->rchild);   
59.     }   
60. }   
61. //后序遍历   
62. void PostOrder(BiTree T){ 
63.     if(T != NULL){ 
64.         //访问左子结点   
65.         PostOrder(T->lchild); 
66.         //访问右子结点   
67.         PostOrder(T->rchild); 
68.         //访问根节点   
69.         Visit(T); 
70.     } 
71. } 
72. /* 先序遍历(非递归) 
73.    思路：访问T->data后，将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，再先序遍历T的右子树。 
74. */ 
75. void PreOrder2(BiTree T){ 
76.     stack<BiTree> stack; 
77.     //p是遍历指针   
78.     BiTree p = T; 
79.     //栈不空或者p不空时循环   
80.     while(p || !pty()){ 
81.         if(p != NULL){ 
82.             //存入栈中   
83.             stack.push(p); 
84.             //访问根节点   
85.             printf("%c ",p->data); 
86.             //遍历左子树   
87.             p = p->lchild; 
88.         } 
89.         else{ 
90.             //退栈   
91.             p =&p(); 
92.             stack.pop(); 
93.             //访问右子树   
94.             p = p->rchild; 
95.         } 
96.     }//while   
97. } 
98. /* 中序遍历(非递归) 
99.    思路：T是要遍历树的根指针，中序遍历要求在遍历完左子树后，访问根，再遍历右子树。 
100.          先将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，访问T->data，再中序遍历T的右子树。 
101. */ 
102. void InOrder2(BiTree T){ 
103.     stack<BiTree> stack; 
104.     //p是遍历指针   
105.     BiTree p = T; 
106.     //栈不空或者p不空时循环   
107.     while(p || !pty()){ 
108.         if(p != NULL){ 
109.             //存入栈中   
110.             stack.push(p); 
111.             //遍历左子树   
112.             p = p->lchild; 
113.         } 
114.         else{ 
115.             //退栈，访问根节点   
116.             p =&p(); 
117.             printf("%c ",p->data); 
118.             stack.pop(); 
119.             //访问右子树   
120.             p = p->rchild; 
121.         } 
122.     }//while   
123. } 
124.  
125. //后序遍历(非递归)   二叉树中序遍历非递归算法
126. typedef struct BiTNodePost{ 
127.     BiTree biTree; 
128.     char tag; 
129. }BiTNodePost,*BiTreePost; 
130.  
131. void PostOrder2(BiTree T){ 
132.     stack<BiTreePost> stack; 
133.     //p是遍历指针   
134.     BiTree p = T; 
135.     BiTreePost BT; 
136.     //栈不空或者p不空时循环   
137.     while(p != NULL || !pty()){ 
138.         //遍历左子树   
139.         while(p != NULL){ 
140.             BT = (BiTreePost)malloc(sizeof(BiTNodePost)); 
141.             BT->biTree = p; 
142.             //访问过左子树   
143.             BT->tag = 'L'; 
144.             stack.push(BT); 
145.             p = p->lchild; 
146.         } 
147.         //左右子树访问完毕访问根节点   
148.         while(!pty() && (p())->tag == 'R'){ 
149.             BT =&p(); 
150.             //退栈   
151.             stack.pop(); 
152.             BT->biTree; 
153.             printf("%c ",BT->biTree->data); 
154.         } 
155.         //遍历右子树   
156.         if(!pty()){ 
157.             BT =&p(); 
158.             //访问过右子树   
159.             BT->tag = 'R'; 
160.             p = BT->biTree; 
161.             p = p->rchild; 
162.         } 
163.     }//while   
164. } 
165. //层次遍历   
166. void LevelOrder(BiTree T){ 
167.     BiTree p = T; 
168.     //队列   
169.     queue<BiTree> queue; 
170.     //根节点入队   
171.     queue.push(p); 
172.     //队列不空循环   
173.     while(!pty()){ 
174.         //对头元素出队   
175.         p = queue.front(); 
176.         //访问p指向的结点   
177.         printf("%c ",p->data); 
178.         //退出队列   
179.         queue.pop(); 
180.         //左子树不空，将左子树入队   
181.         if(p->lchild != NULL){ 
182.             queue.push(p->lchild); 
183.         } 
184.         //右子树不空，将右子树入队   
185.         if(p->rchild != NULL){ 
186.             queue.push(p->rchild); 
187.         } 
188.     } 
189. } 
190. int main() 

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。