c++学习笔记—二叉树基本操作的实现

用c++语言实现的二叉树基本操作，包括二叉树的创建、二叉树的遍历（包括前序、中序、后序递归和非递归算法）、求二叉树高度，计数叶子节点数、计数度为1的节点数等基本操作。

IDE：vs2013

具体实现代码如下：

1. #include “stdafx.h”
2. #include <malloc.h>
3. #include <stack>
4. #include <iostream>
5. #define MAXSIZE 100
6. using namespace std;
7. typedef struct node   //二叉树结构体
8. {
9. int data;
10. struct node *lchild;
11. struct node *rchild;
12. }Bnode,*BTree;
13. BTree CreateBinaryTree(BTree &tree){            //创建二叉树
14. int inputdata;
15. cin >> inputdata;
16. if (-1 == inputdata)
17. {
18. tree = NULL;
19. }
20. else
21. {
22. if (!(tree = (Bnode*)malloc(sizeof(Bnode))))
23. {
24. cout<<“ERROR”;
25. }
26. tree->data = inputdata;
27. tree->lchild=CreateBinaryTree(tree->lchild);
28. tree->rchild=CreateBinaryTree(tree->rchild);
29. }
30. return tree;
31. }
32. void preorderTraverse(BTree tree)    //递归前序遍历
33. {
34. if (tree != NULL)
35. {
36. cout<<tree->data;
37. }
38. if (tree->lchild != NULL)
39. {
40. preorderTraverse(tree->lchild);
41. }
42. if (tree->rchild)
43. {
44. preorderTraverse(tree->rchild);
45. }
46. }
47. void preorderTraverse2(BTree tree)
48. {
49. //////////////////////////////////////////////////////////////////////////
50. //          非递归前序
51. //    根据前序遍历访问的顺序，优先访问根结点，
52. //    然后再分别访问左孩子和右孩子。
53. //    即对于任一结点，其可看做是根结点，因此可以直接访问，访问完之后，
54. //    若其左孩子不为空，按相同规则访问它的左子树；当访问其左子树时，
55. //    再访问它的右子树。因此其处理过程如下：
56. //
57. //////////////////////////////////////////////////////////////////////////
58. stack<BTree> s;
59. if (!tree)
60. {
61. cout << “空树” << endl;
62. return;
63. }
64. while (tree || !s.empty())
65. {
66. while (tree)
67. {
68. s.push(tree);
69. cout << tree->data;
70. tree = tree->lchild;
71. }
72. tree = s.top();
73. s.pop();
74. tree = tree->rchild;
75. }
76. }
77. void inorderTraverse(BTree tree)      //递归中序遍历
78. {
79. if (tree->lchild)
80. {
81. inorderTraverse(tree->lchild);
82. }
83. cout << tree->data;
84. if (tree->rchild)
85. {
86. inorderTraverse(tree->rchild);
87. }
88. }
89. void inorderTraverse2(BTree tree)
90. {
91. //////////////////////////////////////////////////////////////////////////
92. //            非递归中序遍历
93. //      根据中序遍历的顺序，对于任一结点，优先访问其左孩子，
94. //      而左孩子结点又可以看做一根结点，然后继续访问其左孩子结点，
95. //       直到遇到左孩子结点为空的结点才进行访问，
96. //       然后按相同的规则访问其右子树。
97. //       因此其处理过程如下：
98. //
99. ///////////////////////////////////////////////////////////////////////////
100. stack<BTree> s;
101. if (!tree)
102. {
103. cout << “空树” << endl;
104. return;
105. }
106. while (tree || !s.empty())
107. {
108. while (tree)
109. {
110. s.push(tree);
111. tree = tree->lchild;
112. }
113. tree = s.top();
114. s.pop();
115. cout << tree->data;
116. tree = tree->rchild;
117. }
118. }
119. void postoderTraverse(BTree tree)     //递归后序遍历
120. {
121. if (tree->lchild)
122. {
123. postoderTraverse(tree->lchild);
124. }
125. if (tree->rchild)
126. {
127. postoderTraverse(tree->rchild);
128. }
129. cout << tree->data;
130. }
131. void postoderTraverse2(BTree tree)
132. {
133. //////////////////////////////////////////////////////////////////////////
134. //          非递归后序遍历
135. //      要保证根结点在左孩子和右孩子访问之后才能访问，
136. //  因此对于任一结点P，先将其入栈。如果P不存在左孩子和右孩子，
137. //  则可以直接访问它；或者P存在左孩子或者右孩子，
138. //  但是其左孩子和右孩子都已被访问过了，则同样可以直接访问该结点。
139. //  若非上述两种情况，则将P的右孩子和左孩子依次入栈，
140. //  这样就保证了每次取栈顶元素的时候，左孩子在右孩子前面被访问，
141. //  左孩子和右孩子都在根结点前面被访问。
142. //////////////////////////////////////////////////////////////////////////
143. stack<BTree> s;
144. BTree cur;                        //当前结点
145. BTree pre = NULL;                 //前一次访问的结点
146. s.push(tree);
147. while (!s.empty())
148. {
149. cur = s.top();
150. if ((cur->lchild == NULL&&cur->rchild == NULL) ||(pre != NULL && (pre == cur->lchild || pre == cur->rchild)))
151. {
152. cout << cur->data;  //如果当前结点没有孩子结点或者孩子节点都已被访问过
153. s.pop();
154. pre = cur;
155. }
156. else
157. {
158. if (cur->rchild != NULL)
159. s.push(cur->rchild);
160. if (cur->lchild != NULL)
161. s.push(cur->lchild);
162. }
163. }
164. }
165. int Depth(BTree T)   //求二叉树的深度
166. {
167. int dep = 0, depl, depr;
168. if (!T) dep = 0;
169. else
170. {
171. depl = Depth(T->lchild);
172. depr = Depth(T->rchild);
173. dep = 1 + (depl>depr ? depl : depr);
174. }
175. return dep;
176. }
177. int sumLeaf(BTree tree)   //求叶子节点的个数
178. {
179. int sum = 0, m, n;
180. if (tree)
181. {
182. if ((!tree->lchild) && (!tree->rchild))
183. sum++;
184. m = sumLeaf(tree->lchild);
185. sum += m;
186. n = sumLeaf(tree->rchild);
187. sum += n;
188. }
189. return sum;
190. }
191. int numnSinglePoint(BTree tree )    //统计度为1的节点数目
192. {
193. int sum = 0, m, n;
194. if (tree)
195. {
196. if ((tree->lchild!=NULL) && (tree->rchild == NULL))
197. sum++;
198. if ((tree->lchild == NULL) && (tree->rchild != NULL))
199. sum++;
200. m = numnSinglePoint(tree->lchild);
201. sum += m;
202. n = m = numnSinglePoint(tree->rchild);
203. sum += n;
204. }
205. return sum;
206. }
207. int _tmain(int argc, _TCHAR* argv[])
208. {
209. BTree t;
210. t= CreateBinaryTree(t);
211. cout<<endl<<“非递归前序遍历:”;
212. preorderTraverse2(t);
213. cout << endl<<“———————-“<<endl;
214. cout << “递归前序遍历：”;
215. preorderTraverse(t);
216. cout << endl << “———————“<<endl;
217. cout << “非递归中序遍历:”;
218. inorderTraverse2(t);
219. cout << endl << “———————“<<endl;
220. cout << “递归中序遍历:”;
221. inorderTraverse(t);
222. cout << endl << “———————“<<endl;
223. cout << “非递归后序遍历:”;
224. postoderTraverse2(t);
225. cout << endl << “———————“<<endl;
226. cout << “递归后序遍历:”;
227. postoderTraverse(t);
228. cout << endl << “———————-“<<endl;
229. cout << “链表深度为：”<<Depth(t);
230. cout << endl << “———————-“<<endl;
231. cout << “链表的叶子节点个数为：” << sumLeaf(t);
232. cout << endl << “———————-“<<endl;
233. cout << “链表中度为1的节点数目为：” << numnSinglePoint(t) << endl;
234. return 0;
235. }

构建二叉树示意图为：

运行程序结果为：