深圳幻海软件技术有限公司 欢迎您！
更多

二叉树相关操作---纯代码实现详解

2023-04-14

null cout endl
目录前言(很重要)二叉树的概念二叉树的相关术语相关操作菜单  二叉树的构造 创建二叉树先序遍历二叉树   中序遍历二叉树 后序遍历二叉树 层次遍历二叉树 二叉树的深度 二叉树的叶子结点数 二

目录

前言 (很重要)

二叉树的概念

二叉树的相关术语

相关操作菜单

  二叉树的构造

 创建二叉树

先序遍历二叉树  

 中序遍历二叉树

 后序遍历二叉树

 层次遍历二叉树

 二叉树的深度

 二叉树的叶子结点数

 二叉树的结点数

整体代码

结果展示

结束语

前言 (很重要)

        大家好，今天给大家带来的是二叉树的相关操作，希望能够给大家带来帮助。

        另外有很多小伙伴们在学习算法的时候，只去学习一些关于算法理论的知识，并不知道自己的代码实战能力如何，也不清楚到底对该算法的了解有多深，所以在这里小张给大家推荐一个很棒的平台，在这里有很多的面试和算法题，也有很多的面试和求职的机会，大家可以点击下方链接进入牛客网刷算法真题，提高自己代码实战能力，早日拿到满意的offer！点击这里进入牛客网刷算法和面试真题提高代码实战能力

二叉树的概念

        二叉树（Binary tree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。二叉树特点是每个节点最多只能有两棵子树，且有左右之分 。

二叉树的相关术语

①节点：包含一个数据元素及若干指向子树分支的信息 。

②节点的度：一个节点拥有子树的数目称为节点的度 。

③叶子节点：也称为终端节点，没有子树的节点或者度为零的节点 。

④分支节点：也称为非终端节点，度不为零的节点称为非终端节点 。

⑤树的度：树中所有节点的度的最大值 。

⑥节点的层次：从根节点开始，假设根节点为第1层，根节点的子节点为第2层，依此类推，如果某一个节点位于第L层，则其子节点位于第L+1层 。

⑦树的深度：也称为树的高度，树中所有节点的层次最大值称为树的深度  。

相关操作菜单

  1. //菜单
  2. void menu()
  3. {
  4. cout << "\t\t\t******************************************************************" << endl;
  5. cout << "\t\t\t****************  1.输入-1  退出程序           *******************" << endl;
  6. cout << "\t\t\t****************  2.输入1   初始化二叉树       *******************" << endl;
  7. cout << "\t\t\t****************  3.输入2   对二叉树先序遍历   *******************" << endl;
  8. cout << "\t\t\t****************  4.输入3   对二叉树中序遍历   *******************" << endl;
  9. cout << "\t\t\t****************  5.输入4   对二叉树后序遍历   *******************" << endl;
  10. cout << "\t\t\t****************  6.输入5   对二叉树层次遍历   *******************" << endl;
  11. cout << "\t\t\t****************  7.输入6   二叉树深度         *******************" << endl;
  12. cout << "\t\t\t****************  8.输入7   二叉树叶子结点数   *******************" << endl;
  13. cout << "\t\t\t****************  9.输入8   二叉树的结点数     *******************" << endl;
  14. cout << "\t\t\t******************************************************************" << endl;
  15. }

  二叉树的构造

  1. //构造二叉树
  2. typedef struct Binode
  3. {
  4. //数据域
  5. char data;
  6. //定义左孩子和右孩子
  7. struct Binode*lchid, *rchid;
  8. }Binode, *StrBinode;

 创建二叉树

  1. //先序遍历创建二叉树
  2. void creatBinode(StrBinode&T)
  3. {
  4. cin >> ch;
  5. if (ch == '#')
  6. {
  7. //如果输入是#的话就说明根结点就是叶子结点
  8. //就没必要再去进行开辟一个二叉树空间
  9. T = NULL;
  10. }
  11. else
  12. {
  13. T = new Binode;
  14. T->data = ch;
  15. creatBinode(T->lchid);
  16. creatBinode(T->rchid);
  17. }
  18. }

先序遍历二叉树  

  1. //先序遍历二叉树
  2. void visitBinode(StrBinode&T)
  3. {
  4. if (T!=NULL)
  5. {
  6. cout << T->data << " ";
  7. visitBinode(T->lchid);
  8. visitBinode(T->rchid);
  9. }
  10. if(T==NULL)
  11. {
  12. cout << "#" << " ";
  13. }
  14. }

 中序遍历二叉树

  1. //中序遍历二叉树
  2. void MidvisitBinode(StrBinode&T)
  3. {
  4. if (T != NULL)
  5. {
  6. visitBinode(T->lchid);
  7. cout << T->data << " ";
  8. visitBinode(T->rchid);
  9. }
  10. if (T == NULL)
  11. {
  12. cout << "#" << " ";
  13. }
  14. }

 后序遍历二叉树

  1. //后序遍历二叉树
  2. void BackvisitBinode(StrBinode&T)
  3. {
  4. if (T != NULL)
  5. {
  6. visitBinode(T->lchid);
  7. visitBinode(T->rchid);
  8. cout << T->data << " ";
  9. }
  10. if (T == NULL)
  11. {
  12. cout << "#" << " ";
  13. }
  14. }

 层次遍历二叉树

  1. //二叉树的层次遍历
  2. void Levelorder(StrBinode&HT)
  3. {
  4. StrBinode T;
  5. T = new Binode;
  6. //创建一个队列qu
  7. queue<StrBinode> qu;
  8. //将根结点的指针压入队列
  9. qu.push(HT);
  10. //当队列不为空的时候就继续进行循环
  11. while (!qu.empty())
  12. {
  13. //让T里面存放队列中第一个元素的值
  14. T = qu.front();
  15. //C++自带的队列出队的话是删除值不返回值
  16. qu.pop();
  17. //访问出队元素的值
  18. cout << T->data << " ";
  19. //当该节点左孩子不为空的时候就让左孩子入队
  20. if (T->lchid != NULL)
  21. {
  22. qu.push(T->lchid);
  23. }
  24. //当该节点右孩子不为空的时候就让左孩子入队
  25. if (T->rchid != NULL)
  26. {
  27. qu.push(T->rchid);
  28. }
  29. }
  31. }

 二叉树的深度

  1. //二叉树的深度
  2. int deep(StrBinode&T)
  3. {
  4. if (T == NULL)
  5. {
  6. return 0;
  7. }
  8. else
  9. {
  10. int m = deep(T->lchid);
  11. int n = deep(T->rchid);
  12. if (m > n)
  13. {
  14. return (m + 1);
  15. }
  16. else
  17. {
  18. return (n + 1);
  19. }
  20. }
  21. }

 二叉树的叶子结点数

  1. //求二叉树的叶子结点
  2. int leaf(StrBinode&T)
  3. {
  4. //如果是空树
  5. if (T == NULL)
  6. {
  7. //返回0
  8. return 0;
  9. }
  10. //如果是叶子结点
  11. if (T->lchid == NULL && T->rchid == NULL)
  12. {
  13. //返回1
  14. return 1;
  15. }
  16. return leaf(T->lchid) + leaf(T->rchid);
  17. }

 二叉树的结点数

  1. //求二叉树的结点数
  2. int Nodecount(StrBinode&T)
  3. {
  4. //如果是根结点没有数据
  5. if (T == NULL)
  6. {
  7. return 0;
  8. }
  9. else
  10. {
  11. return Nodecount(T->lchid) + Nodecount(T->rchid) + 1;
  12. }
  13. }

整体代码

  1. #include<iostream>
  2. #include<queue>
  3. using namespace std;
  4. char ch = 0;
  5.  
  6. //构造二叉树
  7. typedef struct Binode
  8. {
  9. //数据域
  10. char data;
  11. //定义左孩子和右孩子
  12. struct Binode*lchid, *rchid;
  13. }Binode, *StrBinode;
  14.  
  15. //先序遍历创建二叉树
  16. void creatBinode(StrBinode&T)
  17. {
  18. cin >> ch;
  19. if (ch == '#')
  20. {
  21. //如果输入是#的话就说明根结点就是叶子结点
  22. //就没必要再去进行开辟一个二叉树空间
  23. T = NULL;
  24. }
  25. else
  26. {
  27. T = new Binode;
  28. T->data = ch;
  29. creatBinode(T->lchid);
  30. creatBinode(T->rchid);
  31. }
  32. }
  33.  
  34. //先序遍历二叉树
  35. void visitBinode(StrBinode&T)
  36. {
  37. if (T!=NULL)
  38. {
  39. cout << T->data << " ";
  40. visitBinode(T->lchid);
  41. visitBinode(T->rchid);
  42. }
  43. if(T==NULL)
  44. {
  45. cout << "#" << " ";
  46. }
  47. }
  48.  
  49. //中序遍历二叉树
  50. void MidvisitBinode(StrBinode&T)
  51. {
  52. if (T != NULL)
  53. {
  54. visitBinode(T->lchid);
  55. cout << T->data << " ";
  56. visitBinode(T->rchid);
  57. }
  58. if (T == NULL)
  59. {
  60. cout << "#" << " ";
  61. }
  62. }
  63.  
  64. //后序遍历二叉树
  65. void BackvisitBinode(StrBinode&T)
  66. {
  67. if (T != NULL)
  68. {
  69. visitBinode(T->lchid);
  70. visitBinode(T->rchid);
  71. cout << T->data << " ";
  72. }
  73. if (T == NULL)
  74. {
  75. cout << "#" << " ";
  76. }
  77. }
  78.  
  79. //二叉树的层次遍历
  80. void Levelorder(StrBinode&HT)
  81. {
  82. StrBinode T;
  83. T = new Binode;
  84. //创建一个队列qu
  85. queue<StrBinode> qu;
  86. //将根结点的指针压入队列
  87. qu.push(HT);
  88. //当队列不为空的时候就继续进行循环
  89. while (!qu.empty())
  90. {
  91. //让T里面存放队列中第一个元素的值
  92. T = qu.front();
  93. //C++自带的队列出队的话是删除值不返回值
  94. qu.pop();
  95. //访问出队元素的值
  96. cout << T->data << " ";
  97. //当该节点左孩子不为空的时候就让左孩子入队
  98. if (T->lchid != NULL)
  99. {
  100. qu.push(T->lchid);
  101. }
  102. //当该节点右孩子不为空的时候就让左孩子入队
  103. if (T->rchid != NULL)
  104. {
  105. qu.push(T->rchid);
  106. }
  107. }
  109. }
  110.  
  111. //二叉树的深度
  112. int deep(StrBinode&T)
  113. {
  114. if (T == NULL)
  115. {
  116. return 0;
  117. }
  118. else
  119. {
  120. int m = deep(T->lchid);
  121. int n = deep(T->rchid);
  122. if (m > n)
  123. {
  124. return (m + 1);
  125. }
  126. else
  127. {
  128. return (n + 1);
  129. }
  130. }
  131. }
  132.  
  133. //求二叉树的叶子结点
  134. int leaf(StrBinode&T)
  135. {
  136. //如果是空树
  137. if (T == NULL)
  138. {
  139. //返回0
  140. return 0;
  141. }
  142. //如果是叶子结点
  143. if (T->lchid == NULL && T->rchid == NULL)
  144. {
  145. //返回1
  146. return 1;
  147. }
  148. return leaf(T->lchid) + leaf(T->rchid);
  149. }
  150.  
  151. //求二叉树的结点数
  152. int Nodecount(StrBinode&T)
  153. {
  154. //如果是根结点没有数据
  155. if (T == NULL)
  156. {
  157. return 0;
  158. }
  159. else
  160. {
  161. return Nodecount(T->lchid) + Nodecount(T->rchid) + 1;
  162. }
  163. }
  164.  
  165. //菜单
  166. void menu()
  167. {
  168. cout << "\t\t\t******************************************************************" << endl;
  169. cout << "\t\t\t****************  1.输入-1  退出程序           *******************" << endl;
  170. cout << "\t\t\t****************  2.输入1   初始化二叉树       *******************" << endl;
  171. cout << "\t\t\t****************  3.输入2   对二叉树先序遍历   *******************" << endl;
  172. cout << "\t\t\t****************  4.输入3   对二叉树中序遍历   *******************" << endl;
  173. cout << "\t\t\t****************  5.输入4   对二叉树后序遍历   *******************" << endl;
  174. cout << "\t\t\t****************  6.输入5   对二叉树层次遍历   *******************" << endl;
  175. cout << "\t\t\t****************  7.输入6   二叉树深度         *******************" << endl;
  176. cout << "\t\t\t****************  8.输入7   二叉树叶子结点数   *******************" << endl;
  177. cout << "\t\t\t****************  9.输入8   二叉树的结点数     *******************" << endl;
  178. cout << "\t\t\t******************************************************************" << endl;
  179. }
  180.  
  181. int main()
  182. {
  183. int n = 0;
  184. StrBinode T;
  185. menu();
  186. while (cin >> n)
  187. {
  188. if (n < 0)
  189. {
  190. break;
  191. }
  192. switch (n)
  193. {
  194. case 1:
  195. //初始化二叉树
  196. cout << "请输入值对二叉树进行初始化" << endl;
  197. creatBinode(T);
  198. cout << "初始化完成" << endl;
  199. break;
  200. case 2:
  201. //先序遍历
  202. cout << "先序遍历的结果为" << endl;
  203. visitBinode(T);
  204. cout << "先序遍历结束" << endl;
  205. break;
  206. case 3:
  207. //中序遍历
  208. cout << "中序遍历的结果为" << endl;
  209. MidvisitBinode(T);
  210. cout << "中序遍历结束" << endl;
  211. break;
  212. case 4:
  213. //后序遍历
  214. cout << "后序遍历的结果为" << endl;
  215. BackvisitBinode(T);
  216. cout << "后序遍历结束" << endl;
  217. break;
  218. case 5:
  219. //层次遍历
  220. cout << "层次遍历的结果为" << endl;
  221. Levelorder(T);
  222. cout << "层次遍历结束" << endl;
  223. break;
  224. case 6:
  225. cout << "二叉树的深度为：";
  226. cout << deep(T) << endl;
  227. break;
  228. case 7:
  229. cout << "二叉树的叶子结点数为：";
  230. cout << leaf(T) << endl;
  231. break;
  232. case 8:
  233. cout << "二叉树的结点数为；";
  234. cout << Nodecount(T) << endl;
  235. break;
  236. default:
  237. cout << "您的输入有误，请重新输入" << endl;
  238. break;
  239. }
  240. }
  241. return 0;
  242. }

结果展示

结束语

        到这里今天的内容就已经全部结束了，这里的代码是运用C++语言实现的，其他语言的话也大同小异，只要相关的思想掌握了，就能写出来相应的代码，最后小张在这里感谢大家的支持 ！

文章知识点与官方知识档案匹配，可进一步学习相关知识
算法技能树首页概览44032 人正在系统学习中
【算法系列篇】滑动窗口
走进人工智能|深度学习 算法的创世纪