1. //二叉树结点  
2. typedef struct BiTNode{  
3.     //数据  
4.     char data;  
5.     //左右孩子指针  
6.     struct BiTNode *lchild,*rchild;  
7. }BiTNode,*BiTree;  

[cpp] view plaincopy

 

1. // 二叉树节点结构  
2. struct TreeNode{  
3.     int val;  
4.     TreeNode *left;  
5.     TreeNode *right;  
6.     TreeNode(int x):val(x),left(nullptr),right(nullptr){}  
7. };  

1. //按先序序列创建二叉树  
2. int CreateBiTree(BiTree &T){  
3.     char data;  
4.     //按先序次序输入二叉树中结点的值（一个字符），‘#’表示空树  
5.     scanf("%c",&data);  
6.     if(data == ‘#‘){  
7.         T = NULL;  
8.     }  
9.     else{  
10.         T = (BiTree)malloc(sizeof(BiTNode));  
11.         //生成根结点  
12.         T->data = data;  
13.         //构造左子树  
14.         CreateBiTree(T->lchild);  
15.         //构造右子树  
16.         CreateBiTree(T->rchild);  
17.     }  
18.     return 0;  
19. }  

[cpp] view plaincopy

 

1. // 1.创建二叉树  
2. void CreateTree(TreeNode* &root){  
3.     int val;  
4.     //按先序次序输入二叉树中结点的值,‘-1’表示空树  
5.     cin>>val;  
6.     // 空节点  
7.     if(val == -1){  
8.         root = nullptr;  
9.         return;  
10.     }//if  
11.     root = new TreeNode(val);  
12.     //构造左子树  
13.     CreateTree(root->left);  
14.     //构造右子树  
15.     CreateTree(root->right);  
16. }  

[cpp] view plaincopy

 

1. struct TreeNode {  
2.     int val;  
3.     TreeNode *left;  
4.     TreeNode *right;  
5.     TreeNode(int x) : val(x), left(NULL), right(NULL) {}  
6. };  

[cpp] view plaincopy

 

1. // 创建二叉树  
2. TreeNode* CreateTreeByLevel(vector<char> num){  
3.     int len = num.size();  
4.     if(len == 0){  
5.         return NULL;  
6.     }//if  
7.     queue<TreeNode*> queue;  
8.     int index = 0;  
9.     // 创建根节点  
10.     TreeNode *root = new TreeNode(num[index++]);  
11.     // 入队列  
12.     queue.push(root);  
13.     TreeNode *p = NULL;  
14.     while(!queue.empty() && index < len){  
15.         // 出队列  
16.         p = queue.front();  
17.         queue.pop();  
18.         // 左节点  
19.         if(index < len && num[index] != -1){  
20.             // 如果不空创建一个节点  
21.             TreeNode *leftNode = new TreeNode(num[index]);  
22.             p->left = leftNode;  
23.             queue.push(leftNode);  
24.         }  
25.         index++;  
26.         // 右节点  
27.         if(index < len && num[index] != -1){  
28.             // 如果不空创建一个节点  
29.             TreeNode *rightNode = new TreeNode(num[index]);  
30.             p->right = rightNode;  
31.             queue.push(rightNode);  
32.         }  
33.         index++;  
34.     }//while  
35.     return root;  
36. }  

1. //输出  
2. void Visit(BiTree T){  
3.     if(T->data != ‘#‘){  
4.         printf("%c ",T->data);  
5.     }  
6. }  
7. //先序遍历  
8. void PreOrder(BiTree T){  
9.     if(T != NULL){  
10.         //访问根节点  
11.         Visit(T);  
12.         //访问左子结点  
13.         PreOrder(T->lchild);  
14.         //访问右子结点  
15.         PreOrder(T->rchild);  
16.     }  
17. }  
18. //中序遍历  
19. void InOrder(BiTree T){  
20.     if(T != NULL){  
21.         //访问左子结点  
22.         InOrder(T->lchild);  
23.         //访问根节点  
24.         Visit(T);  
25.         //访问右子结点  
26.         InOrder(T->rchild);  
27.     }  
28. }  
29. //后序遍历  
30. void PostOrder(BiTree T){  
31.     if(T != NULL){  
32.         //访问左子结点  
33.         PostOrder(T->lchild);  
34.         //访问右子结点  
35.         PostOrder(T->rchild);  
36.         //访问根节点  
37.         Visit(T);  
38.     }  
39. }  

1. /* 先序遍历(非递归) 
2.    思路：访问T->data后，将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，再先序遍历T的右子树。 
3. */  
4. void PreOrder2(BiTree T){  
5.     stack<BiTree> stack;  
6.     //p是遍历指针  
7.     BiTree p = T;  
8.     //栈不空或者p不空时循环  
9.     while(p || !stack.empty()){  
10.         if(p != NULL){  
11.             //存入栈中  
12.             stack.push(p);  
13.             //访问根节点  
14.             printf("%c ",p->data);  
15.             //遍历左子树  
16.             p = p->lchild;  
17.         }  
18.         else{  
19.             //退栈  
20.             p = stack.top();  
21.             stack.pop();  
22.             //访问右子树  
23.             p = p->rchild;  
24.         }  
25.     }//while  
26. }  

[cpp] view plaincopy

 

1. // 先序遍历  
2. void PreOrder(TreeNode* root){  
3.     if(root == NULL){  
4.         return;  
5.     }  
6.     stack<TreeNode*> stack;  
7.     stack.push(root);  
8.     TreeNode *p = NULL;  
9.     while(!stack.empty()){  
10.         p = stack.top();  
11.         stack.pop();  
12.         cout<<p->val<<endl;  
13.         // 右子节点不空压入栈中  
14.         if(p->right){  
15.             stack.push(p->right);  
16.         }  
17.         // 左子节点不空压入栈中  
18.         if(p->left){  
19.             stack.push(p->left);  
20.         }  
21.     }//while  
22. }  

1. void InOrder2(BiTree T){  
2.     stack<BiTree> stack;  
3.     //p是遍历指针  
4.     BiTree p = T;  
5.     //栈不空或者p不空时循环  
6.     while(p || !stack.empty()){  
7.         if(p != NULL){  
8.             //存入栈中  
9.             stack.push(p);  
10.             //遍历左子树  
11.             p = p->lchild;  
12.         }  
13.         else{  
14.             //退栈，访问根节点  
15.             p = stack.top();  
16.             printf("%c ",p->data);  
17.             stack.pop();  
18.             //访问右子树  
19.             p = p->rchild;  
20.         }  
21.     }//while  
22. }  

1. //后序遍历(非递归)  
2. typedef struct BiTNodePost{  
3.     BiTree biTree;  
4.     char tag;  
5. }BiTNodePost,*BiTreePost;  
6.   
7. void PostOrder2(BiTree T){  
8.     stack<BiTreePost> stack;  
9.     //p是遍历指针  
10.     BiTree p = T;  
11.     BiTreePost BT;  
12.     //栈不空或者p不空时循环  
13.     while(p != NULL || !stack.empty()){  
14.         //遍历左子树  
15.         while(p != NULL){  
16.             BT = (BiTreePost)malloc(sizeof(BiTNodePost));  
17.             BT->biTree = p;  
18.             //访问过左子树  
19.             BT->tag = ‘L‘;  
20.             stack.push(BT);  
21.             p = p->lchild;  
22.         }  
23.         //左右子树访问完毕访问根节点  
24.         while(!stack.empty() && (stack.top())->tag == ‘R‘){  
25.             BT = stack.top();  
26.             //退栈  
27.             stack.pop();   
28.             printf("%c ",BT->biTree->data);  
29.         }  
30.         //遍历右子树  
31.         if(!stack.empty()){  
32.             BT = stack.top();  
33.             //访问过右子树  
34.             BT->tag = ‘R‘;  
35.             p = BT->biTree;  
36.             p = p->rchild;  
37.         }  
38.     }//while  
39. }  

[cpp] view plaincopy

 

1. vector<int> postorderTraversal(TreeNode *root) {  
2.     vector<int> result;  
3.     if(root == nullptr){  
4.         return result;  
5.     }//if  
6.     stack<TreeNode*> s;  
7.     s.push(root);  
8.     TreeNode *node;  
9.     while(!s.empty()){  
10.         node = s.top();  
11.         s.pop();  
12.         result.insert(result.begin(),node->val);  
13.         // 左子树  
14.         if(node->left){  
15.             s.push(node->left);  
16.         }//if  
17.         // 右子树  
18.         if(node->right){  
19.             s.push(node->right);  
20.         }//if  
21.     }//while  
22.     return result;  
23. }  

1. //层次遍历  
2. void LevelOrder(BiTree T){  
3.     BiTree p = T;  
4.     //队列  
5.     queue<BiTree> queue;  
6.     //根节点入队  
7.     queue.push(p);  
8.     //队列不空循环  
9.     while(!queue.empty()){  
10.         //对头元素出队  
11.         p = queue.front();  
12.         //访问p指向的结点  
13.         printf("%c ",p->data);  
14.         //退出队列  
15.         queue.pop();  
16.         //左子树不空，将左子树入队  
17.         if(p->lchild != NULL){  
18.             queue.push(p->lchild);  
19.         }  
20.         //右子树不空，将右子树入队  
21.         if(p->rchild != NULL){  
22.             queue.push(p->rchild);  
23.         }  
24.     }  
25. }  

[cpp] view plaincopy

 

1. /*------------------------------------- 
2. *   日期：2015-03-25 
3. *   作者：SJF0115 
4. *   题目: 二叉树各种遍历 
5. *   来源： 
6. *   博客： 
7. ------------------------------------*/  
8. #include <iostream>  
9. #include <vector>  
10. #include <stack>  
11. #include <queue>  
12. using namespace std;  
13.   
14. // 二叉树节点结构  
15. struct TreeNode{  
16.     int val;  
17.     TreeNode *left;  
18.     TreeNode *right;  
19.     TreeNode(int x):val(x),left(nullptr),right(nullptr){}  
20. };  
21. // 1.创建二叉树  
22. void CreateTree(TreeNode* &root){  
23.     int val;  
24.     //按先序次序输入二叉树中结点的值,‘-1’表示空树  
25.     cin>>val;  
26.     // 空节点  
27.     if(val == -1){  
28.         root = nullptr;  
29.         return;  
30.     }//if  
31.     root = new TreeNode(val);  
32.     //构造左子树  
33.     CreateTree(root->left);  
34.     //构造右子树  
35.     CreateTree(root->right);  
36. }  
37. // 2.1 递归先序遍历  
38. void PreOrder(TreeNode* root,vector<int> &result){  
39.     if(root == nullptr){  
40.         return;  
41.     }//if  
42.     result.push_back(root->val);  
43.     // 左子树  
44.     PreOrder(root->left,result);  
45.     // 右子树  
46.     PreOrder(root->right,result);  
47. }  
48. // 2.2 非递归先序遍历  
49. void PreOrder2(TreeNode* root,vector<int> &result){  
50.     if(root == nullptr){  
51.         return;  
52.     }//if  
53.     stack<TreeNode*> s;  
54.     s.push(root);  
55.     TreeNode *node;  
56.     while(!s.empty()){  
57.         node = s.top();  
58.         s.pop();  
59.         result.push_back(node->val);  
60.         // 右子树  
61.         if(node->right){  
62.             s.push(node->right);  
63.         }//if  
64.         // 左子树  
65.         if(node->left){  
66.             s.push(node->left);  
67.         }//if  
68.     }//while  
69. }  
70. // 3.1 递归中序遍历  
71. void InOrder(TreeNode* root,vector<int> &result){  
72.     if(root == nullptr){  
73.         return;  
74.     }//if  
75.     // 左子树  
76.     InOrder(root->left,result);  
77.     result.push_back(root->val);  
78.     // 右子树  
79.     InOrder(root->right,result);  
80. }  
81. // 3.2 非递归中序遍历  
82. void InOrder2(TreeNode* root,vector<int> &result){  
83.     if(root == nullptr){  
84.         return;  
85.     }//if  
86.     stack<TreeNode*> s;  
87.     TreeNode *node = root;  
88.     while(node != nullptr || !s.empty()){  
89.         // 左子树  
90.         if(node != nullptr){  
91.             s.push(node);  
92.             node = node->left;  
93.         }//if  
94.         // 右子树  
95.         else{  
96.             node = s.top();  
97.             s.pop();  
98.             result.push_back(node->val);  
99.             node = node->right;  
100.         }  
101.     }//while  
102. }  
103. // 4.1 递归后序遍历  
104. void PostOrder(TreeNode* root,vector<int> &result){  
105.     if(root == nullptr){  
106.         return;  
107.     }//if  
108.     // 左子树  
109.     PostOrder(root->left,result);  
110.     // 右子树  
111.     PostOrder(root->right,result);  
112.     result.push_back(root->val);  
113. }  
114. // 4.2 非递归后序遍历  
115. void PostOrder2(TreeNode *root,vector<int> &result) {  
116.     if(root == nullptr){  
117.         return;  
118.     }//if  
119.     stack<TreeNode*> s;  
120.     s.push(root);  
121.     TreeNode *node;  
122.     while(!s.empty()){  
123.         node = s.top();  
124.         s.pop();  
125.         result.insert(result.begin(),node->val);  
126.         // 左子树  
127.         if(node->left){  
128.             s.push(node->left);  
129.         }//if  
130.         // 右子树  
131.         if(node->right){  
132.             s.push(node->right);  
133.         }//if  
134.     }//while  
135. }  
136. // 5 层次遍历  
137. void LevelOrder(TreeNode* root,vector<int> &result){  
138.     if(root == nullptr){  
139.         return;  
140.     }//if  
141.     queue<TreeNode*> queue;  
142.     queue.push(root);  
143.     TreeNode *node;  
144.     while(!queue.empty()){  
145.         node = queue.front();  
146.         queue.pop();  
147.         result.push_back(node->val);  
148.         // 左子树  
149.         if(node->left){  
150.             queue.push(node->left);  
151.         }//if  
152.         // 右子树  
153.         if(node->right){  
154.             queue.push(node->right);  
155.         }//if  
156.     }//while  
157. }  
158. // 输出结果  
159. void Print(vector<int> result){  
160.     int size = result.size();  
161.     for(int i = 0;i < size;++i){  
162.         cout<<result[i]<<" ";  
163.     }//for  
164.     cout<<endl;  
165. }  
166. int main(){  
167.     freopen("C:\\Users\\Administrator\\Desktop\\c++.txt", "r", stdin);  
168.     TreeNode* root = nullptr;  
169.     vector<int> result;  
170.     // 创建二叉树  
171.     cout<<"1. 创建二叉树"<<endl;  
172.     CreateTree(root);  
173.     cout<<"-----------------------------"<<endl;  
174.   
175.     cout<<"2.1 递归先序遍历"<<endl;  
176.     PreOrder(root,result);  
177.     Print(result);  
178.     result.clear();  
179.     cout<<"-----------------------------"<<endl;  
180.   
181.     cout<<"2.2 非递归先序遍历"<<endl;  
182.     PreOrder2(root,result);  
183.     Print(result);  
184.     result.clear();  
185.     cout<<"-----------------------------"<<endl;  
186.   
187.     cout<<"3.1 递归中序遍历"<<endl;  
188.     InOrder(root,result);  
189.     Print(result);  
190.     result.clear();  
191.     cout<<"-----------------------------"<<endl;  
192.   
193.     cout<<"3.2 非递归中序遍历"<<endl;  
194.     InOrder2(root,result);  
195.     Print(result);  
196.     result.clear();  
197.     cout<<"-----------------------------"<<endl;  
198.   
199.     cout<<"4.1 递归后序遍历"<<endl;  
200.     PostOrder(root,result);  
201.     Print(result);  
202.     result.clear();  
203.     cout<<"-----------------------------"<<endl;  
204.   
205.     cout<<"4.2 非递归后序遍历"<<endl;  
206.     PostOrder2(root,result);  
207.     Print(result);  
208.     result.clear();  
209.     cout<<"-----------------------------"<<endl;  
210.   
211.     cout<<"5 层次遍历"<<endl;  
212.     LevelOrder(root,result);  
213.     Print(result);  
214.     result.clear();  
215.     cout<<"-----------------------------"<<endl;  
216.     return 0;  
217. }  

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 || !stack.empty()){  
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 = stack.top();  
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 || !stack.empty()){  
108.         if(p != NULL){  
109.             //存入栈中  
110.             stack.push(p);  
111.             //遍历左子树  
112.             p = p->lchild;  
113.         }  
114.         else{  
115.             //退栈，访问根节点  
116.             p = stack.top();  
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 || !stack.empty()){  
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(!stack.empty() && (stack.top())->tag == ‘R‘){  
149.             BT = stack.top();  
150.             //退栈  
151.             stack.pop();  
152.             BT->biTree;  
153.             printf("%c ",BT->biTree->data);  
154.         }  
155.         //遍历右子树  
156.         if(!stack.empty()){  
157.             BT = stack.top();  
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(!queue.empty()){  
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()  
191. {  
192.     BiTree T;  
193.     CreateBiTree(T);  
194.     printf("先序遍历：\n");  
195.     PreOrder(T);  
196.     printf("\n");  
197.     printf("先序遍历(非递归)：\n");  
198.     PreOrder2(T);  
199.     printf("\n");  
200.     printf("中序遍历：\n");  
201.     InOrder(T);  
202.     printf("\n");  
203.     printf("中序遍历(非递归)：\n");  
204.     InOrder2(T);  
205.     printf("\n");  
206.     printf("后序遍历：\n");  
207.     PostOrder(T);  
208.     printf("\n");  
209.     printf("后序遍历(非递归)：\n");  
210.     PostOrder2(T);  
211.     printf("\n");  
212.     printf("层次遍历：\n");  
213.     LevelOrder(T);  
214.     printf("\n");  
215.     return 0;  
216. }  

出处：http://blog.csdn.NET/sjf0115/article/details/8645991