devbox
小小林熬夜学编程
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

C++实现二叉树的创建及遍历_c++二叉树的建立与遍历

作者：小小林熬夜学编程 | 2024-05-12 05:20:58

赞

踩

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

二叉树的结点类

  1. class Node
  2. {
  3. public:
  4.     Node() = default;
  5.     Node(int data) : _data(data), _lchild(nullptr), _rchild(nullptr) {};                                                                                                                                                                 
  6. public:
  7.     char _data; // 数据域以 char 型为例，严谨点可写成模板
  8.     Node* _lchild; // 指向左孩的指针（左右孩也是一个Node）
  9.     Node* _rchild; // 指向右孩
  10. };

二叉树的建立

  1. // 递归建立二叉树,但是这个建完了 T 就不指向根节点了，暂未解决 // 已解决，void CreatBT(Node* T) ---> void CreatBT(Node* &t);   但是为什么这样可行还需要思考一下！！！
  2. // 这里用引用传递的方式，目的是保留原有的根节点指针指向不受影响
  3. void CreatBT(Node* &root)
  4. {
  5.     char ch;
  6.     cout << "请输入结点中存放的数据：";
  7.     cin >> ch;
  8.     if(ch == '#')
  9.     {
  10.         root = nullptr;
  11.     }
  12.     else
  13.     {
  14.         root = new(Node);
  15.         root->_data = ch;
  16.         CreatBT(root->_lchild);
  17.         CreatBT(root->_rchild);
  18.     }
  19. }

先序遍历二叉树

  1. // 先序遍历二叉树
  2. void preOrderTraverse(Node* root) 
  3. {
  4.     if(root == nullptr) {}
  5.     else 
  6.     {
  7.         cout << root->_data << "  ";
  8.         preOrderTraverse(root->_lchild); //递归
  9.         preOrderTraverse(root->_rchild);
  10.     }
  11. }

中序遍历二叉树

  1. // 中序遍历二叉树
  2. void inOrderTraverse(Node* root) 
  3. {
  4.     if(root == nullptr) {}
  5.     else 
  6.     {
  7.         inOrderTraverse(root->_lchild);
  8.         cout << root->_data << "  ";
  9.         inOrderTraverse(root->_rchild);
  10.     }
  11. }

后序遍历二叉树

  1. // 后序遍历二叉树
  2. void postOrderTraverse(Node* root) 
  3. {
  4.     if(root == nullptr) {}
  5.     else 
  6.     {
  7.         postOrderTraverse(root->_lchild);
  8.         postOrderTraverse(root->_rchild);
  9.         cout << root->_data << "  ";
  10.     }
  11. }

中序遍历的非递归算法

  1. // 中序遍历的非递归算法
  2. void inOrdrtTraverse_norecursion(Node* root)
  3. {
  4.     Node* p = root;
  5.     stack<Node*> s; // 使用一个栈，保存每个小二叉树的根节点
  6.     while(p != nullptr || !s.empty())
  7.     {
  8.         if(p != nullptr)
  9.         {
  10.             s.push(p);
  11.             p = p->_lchild;
  12.         }
  13.         else
  14.         {
  15.             Node* q = s.top();
  16.             s.pop();
  17.             cout << q->_data << "  ";
  18.             p = q->_rchild;
  19.         }
  20.     }
  21. }

二叉树的层次遍历

  1. // 二叉树的层次遍历
  2. void LevelOrder(Node* root)
  3. {
  4.     Node* p;
  5.     queue<Node*> q; // 使用一个队列，根节点入队
  6.     q.push(root);
  7.     while(!q.empty())
  8.     {
  9.         p = q.front();
  10.         cout << p->_data << "  ";
  11.         q.pop();
  12.         if(p->_lchild != nullptr)
  13.         {
  14.             q.push(p->_lchild);
  15.         }
  16.         if(p->_rchild != nullptr)
  17.         {
  18.             q.push(p->_rchild);
  19.         }
  20.     }
  21. }

计算二叉树的深度

  1. // 计算二叉树的深度
  2. int Depth(Node* T)
  3. {
  4.     if(T == nullptr)
  5.     {
  6.         return 0;
  7.     }
  8.     else
  9.     {
  10.         int m = Depth(T->_lchild);
  11.         int n = Depth(T->_rchild);
  12.         return (m > n) ? (m + 1) : (n + 1);
  13.     }
  14. }

计算二叉树的总结点数

  1. // 计算二叉树结点总数
  2. int NodeCount(Node* T)
  3. {
  4.     if(T == nullptr)
  5.     {
  6.         return 0;
  7.     }
  8.     else
  9.     {
  10.         return NodeCount(T->_lchild) + NodeCount(T->_rchild) + 1;
  11.     }
  12. }

计算二叉树叶子节点数

  1. // 计算二叉树叶子节点数
  2. int leafNodeCount(Node* T)
  3. {
  4.     if(T == nullptr)
  5.     {
  6.         return 0;
  7.     }
  8.     if(T->_lchild == nullptr && T->_rchild == nullptr)
  9.     {
  10.         return 1;
  11.     }
  12.     else
  13.     {
  14.         return leafNodeCount(T->_lchild) + leafNodeCount(T->_rchild);
  15.     }
  16. }

测试

构建如下测试用例二叉树，并依次测试所写的每一个函数。

按照二叉树的建立函数中的思路，将其以 ‘#’ 补齐为满二叉树，如下 ：

 

其先序遍历为：ABC##DE#G##F###，我们按照这个顺序建立二叉树，并进行测试，结果如下：

 完整代码

  1. #include <iostream>
  2. #include <stack>
  3. #include <queue>
  4. #include <string>
  5. using namespace std;
  6.  
  7. // 二叉链树的创建和遍历
  8.  
  9. class Node
  10. {
  11. public:
  12.     Node() = default;
  13.     Node(int data) : _data(data), _lchild(nullptr), _rchild(nullptr) {};                                                                                                                                                                 
  14. public:
  15.     char _data; // 数据域以 char 型为例，严谨点可写成模板
  16.     Node* _lchild; // 指向左孩的指针（左右孩也是一个Node）
  17.     Node* _rchild; // 指向右孩
  18. };
  19.  
  20. // 递归建立二叉树,但是这个建完了 T 就不指向根节点了，暂未解决 // 已解决，void CreatBT(Node* T) ---> void CreatBT(Node* &t);   但是为什么这样可行还需要思考一下！！！
  21. // 这里用引用传递的方式，目的是保留原有的根节点指针指向不受影响
  22. void CreatBT(Node* &root)
  23. {
  24.     char ch;
  25.     cout << "请输入结点中存放的数据：";
  26.     cin >> ch;
  27.     if(ch == '#')
  28.     {
  29.         root = nullptr;
  30.     }
  31.     else
  32.     {
  33.         root = new(Node);
  34.         root->_data = ch;
  35.         CreatBT(root->_lchild);
  36.         CreatBT(root->_rchild);
  37.     }
  38. }
  39.  
  40. // 先序遍历二叉树
  41. void preOrderTraverse(Node* root) 
  42. {
  43.     if(root == nullptr) {}
  44.     else 
  45.     {
  46.         cout << root->_data << "  ";
  47.         preOrderTraverse(root->_lchild); //递归
  48.         preOrderTraverse(root->_rchild);
  49.     }
  50. }
  51.  
  52. // 中序遍历二叉树
  53. void inOrderTraverse(Node* root) 
  54. {
  55.     if(root == nullptr) {}
  56.     else 
  57.     {
  58.         inOrderTraverse(root->_lchild);
  59.         cout << root->_data << "  ";
  60.         inOrderTraverse(root->_rchild);
  61.     }
  62. }
  63.  
  64. // 后序遍历二叉树
  65. void postOrderTraverse(Node* root) 
  66. {
  67.     if(root == nullptr) {}
  68.     else 
  69.     {
  70.         postOrderTraverse(root->_lchild);
  71.         postOrderTraverse(root->_rchild);
  72.         cout << root->_data << "  ";
  73.     }
  74. }
  75.  
  76. // 中序遍历的非递归算法
  77. void inOrdrtTraverse_norecursion(Node* root)
  78. {
  79.     Node* p = root;
  80.     stack<Node*> s; // 使用一个栈，保存每个小二叉树的根节点
  81.     while(p != nullptr || !s.empty())
  82.     {
  83.         if(p != nullptr)
  84.         {
  85.             s.push(p);
  86.             p = p->_lchild;
  87.         }
  88.         else
  89.         {
  90.             Node* q = s.top();
  91.             s.pop();
  92.             cout << q->_data << "  ";
  93.             p = q->_rchild;
  94.         }
  95.     }
  96. }
  97.  
  98. // 二叉树的层次遍历
  99. void LevelOrder(Node* root)
  100. {
  101.     Node* p;
  102.     queue<Node*> q; // 使用一个队列，根节点入队
  103.     q.push(root);
  104.     while(!q.empty())
  105.     {
  106.         p = q.front();
  107.         cout << p->_data << "  ";
  108.         q.pop();
  109.         if(p->_lchild != nullptr)
  110.         {
  111.             q.push(p->_lchild);
  112.         }
  113.         if(p->_rchild != nullptr)
  114.         {
  115.             q.push(p->_rchild);
  116.         }
  117.     }
  118. }
  119.  
  120. // 计算二叉树的深度
  121. int Depth(Node* T)
  122. {
  123.     if(T == nullptr)
  124.     {
  125.         return 0;
  126.     }
  127.     else
  128.     {
  129.         int m = Depth(T->_lchild);
  130.         int n = Depth(T->_rchild);
  131.         return (m > n) ? (m + 1) : (n + 1);
  132.     }
  133. }
  134.  
  135. // 计算二叉树结点总数
  136. int NodeCount(Node* T)
  137. {
  138.     if(T == nullptr)
  139.     {
  140.         return 0;
  141.     }
  142.     else
  143.     {
  144.         return NodeCount(T->_lchild) + NodeCount(T->_rchild) + 1;
  145.     }
  146. }
  147.  
  148. // 计算二叉树叶子节点数
  149. int leafNodeCount(Node* T)
  150. {
  151.     if(T == nullptr)
  152.     {
  153.         return 0;
  154.     }
  155.     if(T->_lchild == nullptr && T->_rchild == nullptr)
  156.     {
  157.         return 1;
  158.     }
  159.     else
  160.     {
  161.         return leafNodeCount(T->_lchild) + leafNodeCount(T->_rchild);
  162.     }
  163. }
  164.  
  165. void test01()
  166. {
  167.     Node* T = nullptr;
  168.     CreatBT(T);
  169.     cout << "该二叉树先序遍历结果为：";
  170.     preOrderTraverse(T);
  171.     cout << endl << endl;
  172.     cout << "该二叉树中序递归遍历结果为：";
  173.     inOrderTraverse(T);
  174.     cout << endl << endl;
  175.     cout << "该二叉树中序非递归遍历结果为：";
  176.     inOrdrtTraverse_norecursion(T);
  177.     cout << endl << endl;
  178.     cout << "该二叉树后序遍历结果为：";
  179.     postOrderTraverse(T);
  180.     cout << endl << endl;
  181.     cout << "该二叉树层次遍历结果为：";
  182.     LevelOrder(T);
  183.     cout << endl << endl;
  184.     cout << "该二叉树的深度为：" << Depth(T) << endl << endl;
  185.     cout << "该二叉树的结点数为：" << NodeCount(T) << endl << endl;
  186.     cout << "该二叉树的叶子结点数为：" << leafNodeCount(T) << endl << endl;
  187. }
  188.  
  189. int main()
  190. {
  191.     test01();
  192.  
  193.     system("pause");
  194.     return 0;
  195. }

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

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号