当前位置:   article > 正文

C++版二叉树的创建与遍历_c++二叉树的建立与遍历

c++二叉树的建立与遍历

使用补空法创建了一棵二叉树,并且实现了先序遍历、中序遍历、后序遍历、层次遍历功能。

1、定义结点类:

要创建二叉树首先要定义二叉树的结点类,二叉树上每一个结点有3个成员变量,一个存放当前结点的值,其余两个是指针类型,分别指向此节点的左孩子和右孩子;

  1. class Node
  2. {
  3. public:
  4. char data;
  5. Node* lchild; //指向左孩子
  6. Node* rchild; //指向右孩子
  7. };
  8. using Tree = Node*;

2、使用补空法创建二叉树

补空法是指:如果结点没有孩子,在写遍历序列时,在其孩子的位置补‘#’(也可是别的有特殊定义的字符)。

使用先序序列创建二叉树时,先判断字符是否为'#':如果是,说明此处没有结点,指针空指;如果不是,说明有结点,先动态创建一个新结点,给数据域赋值,然后递归创建左子树、递归创建右子树。

  1. void CreateTree(Tree& t)
  2. {
  3. char c;
  4. cin >> c;
  5. if (c == '#')
  6. {
  7. t = nullptr; //没有结点就空指
  8. }
  9. else //创建新结点
  10. {
  11. t = new Node;
  12. t->data = c;
  13. CreateTree(t->lchild);
  14. CreateTree(t->rchild);
  15. }
  16. }

3、先序遍历

非常简单,分为三步:打印当前结点数据、递归左孩子、递归右孩子(根左右)

递归前要确保左|右孩子存在(左|右孩子的指针不空)

  1. void DLR(const Tree& t)
  2. {
  3. cout << t->data << " ";
  4. if (t->lchild)
  5. {
  6. DLR(t->lchild);
  7. }
  8. if (t->rchild)
  9. {
  10. DLR(t->rchild);
  11. }
  12. }

4、中序遍历

(左根右)

  1. void LDR(const Tree& t)
  2. {
  3. if (t->lchild)
  4. {
  5. LDR(t->lchild);
  6. }
  7. cout << t->data << " ";
  8. if (t->rchild)
  9. {
  10. LDR(t->rchild);
  11. }
  12. }

5、后序遍历

(左右根)

  1. void LRD(const Tree& t)
  2. {
  3. if (t->lchild)
  4. {
  5. LRD(t->lchild);
  6. }
  7. if (t->rchild)
  8. {
  9. LRD(t->rchild);
  10. }
  11. cout << t->data << " ";
  12. }

6、层次遍历

层次遍历是从根开始按照辈分大小向下逐层输出,具有先来先服务特性,适合用队列

队列里存的是指向各个结点的指针,先把根节点的指针放进队列;若队列不空,取走并打印队头结点,然后此结点的左右孩子入队,循环遍历即可。

  1. void Gradation(const Tree& t)
  2. {
  3. queue<Node*> q; //存的是指针不是结点
  4. q.push(t); //先把树根的指针入队
  5. Node* temp = nullptr;
  6. while (!q.empty())
  7. {
  8. temp = q.front();
  9. q.pop();
  10. cout << temp->data << " ";
  11. if (temp->lchild)
  12. {
  13. q.push(temp->lchild);
  14. }
  15. if (temp->rchild)
  16. {
  17. q.push(temp->rchild);
  18. }
  19. }
  20. }

总体代码实现:

  1. #include <iostream>
  2. using namespace std;
  3. #include <queue>
  4. class Node
  5. {
  6. public:
  7. char data;
  8. Node* lchild; //指向左孩子
  9. Node* rchild; //指向右孩子
  10. };
  11. using Tree = Node*;
  12. void CreateTree(Tree& t)
  13. {
  14. char c;
  15. cin >> c;
  16. if (c == '#')
  17. {
  18. t = nullptr; //没有结点就空指
  19. }
  20. else //创建新结点
  21. {
  22. t = new Node;
  23. t->data = c;
  24. CreateTree(t->lchild);
  25. CreateTree(t->rchild);
  26. }
  27. }
  28. //先序遍历
  29. void DLR(const Tree& t)
  30. {
  31. cout << t->data << " ";
  32. if (t->lchild)
  33. {
  34. DLR(t->lchild);
  35. }
  36. if (t->rchild)
  37. {
  38. DLR(t->rchild);
  39. }
  40. }
  41. //中序遍历
  42. void LDR(const Tree& t)
  43. {
  44. if (t->lchild)
  45. {
  46. LDR(t->lchild);
  47. }
  48. cout << t->data << " ";
  49. if (t->rchild)
  50. {
  51. LDR(t->rchild);
  52. }
  53. }
  54. //后序遍历
  55. void LRD(const Tree& t)
  56. {
  57. if (t->lchild)
  58. {
  59. LRD(t->lchild);
  60. }
  61. if (t->rchild)
  62. {
  63. LRD(t->rchild);
  64. }
  65. cout << t->data << " ";
  66. }
  67. //层次遍历
  68. void Gradation(const Tree& t)
  69. {
  70. queue<Node*> q; //存的是指针不是结点
  71. q.push(t); //先把树根的指针入队
  72. Node* temp = nullptr;
  73. while (!q.empty())
  74. {
  75. temp = q.front();
  76. q.pop();
  77. cout << temp->data << " ";
  78. if (temp->lchild)
  79. {
  80. q.push(temp->lchild);
  81. }
  82. if (temp->rchild)
  83. {
  84. q.push(temp->rchild);
  85. }
  86. }
  87. }
  88. int main()
  89. {
  90. Tree my_tree;
  91. int choose = 0;
  92. cout << "请选择要执行的操作" << endl;
  93. cout << "1、创建二叉树" << endl;
  94. cout << "2、先序遍历" << endl;
  95. cout << "3、中序遍历" << endl;
  96. cout << "4、后序遍历" << endl;
  97. cout << "5、层次遍历" << endl;
  98. cout << "0、退出" << endl;
  99. while (cin >> choose)
  100. {
  101. switch (choose)
  102. {
  103. case 1:
  104. cout << "请输入要创建树的先序序列,结点没有孩子的位置用#代替:" << endl;
  105. CreateTree(my_tree);
  106. cout << endl;
  107. break;
  108. case 2:
  109. cout << "先序遍历:" << endl;
  110. DLR(my_tree);
  111. cout << endl;
  112. break;
  113. case 3:
  114. cout << "中序遍历:" << endl;
  115. LDR(my_tree);
  116. cout << endl;
  117. break;
  118. case 4:
  119. cout << "后序遍历:" << endl;
  120. LRD(my_tree);
  121. cout << endl;
  122. break;
  123. case 5:
  124. cout << "层次遍历:" << endl;
  125. Gradation(my_tree);
  126. cout << endl;
  127. break;
  128. case 0:
  129. cout << "Bye-Bye" << endl;
  130. return 0;
  131. default:
  132. break;
  133. }
  134. cout << "请输入下一个指令" << endl;
  135. }
  136. return 0;
  137. }

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/Cpp五条/article/detail/557774
推荐阅读
相关标签
  

闽ICP备14008679号