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

2022-04-23 11:10:43

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

IDE：vs2013

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

具体实现代码如下：

  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. }

构建二叉树示意图为：

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

运行程序结果为：

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

上一篇：java 并发容器一之BoundedConcurrentHashMap(基于JDK1.8)


下一篇：curl 伪装来路（referer）