devbox
小丑西瓜9
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

c++数据结构-树（详细总结附代码，一看就懂）_c++树

作者：小丑西瓜9 | 2024-03-16 02:09:33

赞

踩

c++树

树的定义

一棵树是由n（n>0）个元素组成的有限集合，其中：

（1）每个元素称为结点（node）

（2）有一个特定的结点，称为根结点或树根（root）

（3）除根节点外，其余节点能分成m（m>=0）个互不相交的有限集合 T(0)-T(m-1)。其中的每一个子集都是一个树，这些集合被称为这棵树的子树。

如下图是一棵树：

树的基本概念

A. 树是由递归定义的

B. 一棵树中至少有1个结点。这个节点就是根节点，他没有前驱，其余每个节点都有且只有一个前驱节点。每个节点可以有任意个后继结点。因此，树是非线性结构，但也是有序结构。

C. 一个节点的子树个数称为这个结点的度，例如上图根节点的度为2。度为0的结点被称为叶结点；度不为0的结点被称为分支结点，根以外的分支节点称为内部结点，树中各节点的度的最大值称为这棵树的度。

D. 在用图形表示的树形结构中，对两个用线段（我们称为树枝）连接的相关联的结点，称上端结点为下端节点的父节点，反之为子节点。

E. 定义一棵树的根的层次为1，其他结点的层次等于他的父节点的层次加一。一棵树中所有节点的层次的最大值称为这棵树的深度。

F. 对于树中任意两个不同的结点，从一个结点出发一定能到达另一个结点。

G.m（m>=0）棵树的结合称为森林。

树的遍历

在解决问题时，常常要按照某种次序来获取树中全部节点的信息，这种操作叫做树的遍历。

A. 先序遍历 先访问根节点，然后按照左右先后顺序遍历各子树（根左右）

B. 中序遍历 先访问左子树，然后访问根，最后访问右子树（左根右）

C. 层次遍历 按层次的大笑从小到大遍历，同一层次按照从左到右的顺序。

二叉树基本概念

二叉树（binary tree，简称BT），是一种特殊的树，它的度是2。一个节点有两个子节点，其中左边的是左子节点，右边的是右子节点。左边的叫左子树，右边的叫右子树。

二叉树的性质

（1）在二叉树的第 i 层上最多有 个结点（i>=1）

（2）深度为 k 的二叉树至多有 个结点（k>=1）

特别的，深度为 k ，且有 个结点的二叉树称为满二叉树。

（3）对于任意一棵二叉树，如果其叶子结点数为 ，度为 2 的结点数为 ，那么 。

（4）具有 n 个结点的完全二叉树的深度为 。

二叉树的实现

上面我们介绍了树和二叉树，那么我们现在研究一下二叉树的实现，注意，这里默认你有一些 C++ 基础。

首先我们来创建一个二叉树结点类 BSTNode，然后在类中创建几个 BSTNode 类型的变量，值，左子节点，右子节点，父节点。

  1. int _key;  
  2. BSTNode *_left;  //左子节点
  3. BSTNode *_right; //右子节点
  4. BSTNode *_parent;  //父节点

然后我们初始化，这里使用列表初始化。

BSTNode(int k = 0, BSTNode *l = NULL, BSTNode *r = NULL, BSTNode *p = NULL) : _key(k), _left(l), _right(r), _parent(p) {};

接下来，我们来创建一个二叉树类 BinaryTree ，来写二叉树的各种操作函数。

我们先声明函数

  1. void insert(int _key);  //将_key节点插入到二叉树中
  2. void PreOrder();  //前序二叉树遍历
  3. void InOrder();  //中序二叉树遍历
  4. void PostOrder();  //后序二叉树遍历
  5.  
  6. BSTNode *search(int _key);  //递归实现，在二叉树中查找_key节点
  7. BSTNode *IteratorSearch(int _key);  //迭代实现，在二叉树中查找_key节点
  8.  
  9. BSTNode *successor(BSTNode *x);  //找节点(x)的后继节点。即，查找"二叉树中数据值大于该节点"的"最小节点"
  10. BSTNode *predecessor(BSTNode *x);  //找节点(x)的前驱节点。即，查找"二叉树中数据值小于该节点"的"最大节点"
  11.  
  12. void remove(int _key);  //删除_key节点
  13.  
  14. void destroy();  //销毁二叉树

这里包括了二叉树的基本操作。

类的private部分：

  1. BSTNode *_root;  //根节点
  2. void PreOrder(BSTNode *tree); //前序二叉树遍历
  3. void InOrder(BSTNode *tree);  //中序二叉树遍历
  4. void PostOrder(BSTNode *tree);  //后序二叉树遍历
  5.  
  6. BSTNode *search(BSTNode *x, int _key);  //递归实现，在”二叉树x“中查找_key节点
  7. BSTNode *IteratorSearch(BSTNode *x, int _key);  //迭代实现，在“二叉树x”中查找_key节点
  8.  
  9. BSTNode *minimum(BSTNode *tree);  //查找最小节点：返回tree为根节点的二叉树的最小节点
  10. BSTNode *maximum(BSTNode *tree);  //查找最大节点：返回tree为根节点的二叉树的最大节点
  11.  
  12. void insert(BSTNode *&tree, BSTNode *z);  // 将节点(z)插入到二叉树(tree)中
  13.  
  14. BSTNode *remove(BSTNode *tree, BSTNode *z);  // 删除二叉树(tree)中的节点(z)，并返回被删除的节点
  15.  
  16. void destroy(BSTNode *&tree);  //销毁二叉树

也是声明了一些函数。

插入元素

  1. void BinaryTree::insert(int _key)  //将_key节点插入到二叉树中
  2. {
  3.     BSTNode *z = new BSTNode(_key, NULL, NULL, NULL);
  4.     if (z == NULL)
  5.     {
  6.         return;  
  7.     }
  8.     insert(_root, z); 
  9. }
  1. void BinaryTree::insert(BSTNode *&tree, BSTNode *z)  // 将节点(z)插入到二叉树(tree)中
  2. {
  3.     BSTNode *y = NULL;
  4.     BSTNode *x = tree;
  5.  
  6.     while (x != NULL) 
  7.     {
  8.         y = x;
  9.         if (z->_key < x->_key)
  10.         {
  11.             x = x->_left;
  12.         }
  13.         else
  14.         {
  15.             x = x->_right;
  16.         }
  17.     }
  18.  
  19.     z->_parent = y;
  20.     if (y == NULL)
  21.     {
  22.         tree = z;
  23.     }
  24.     else
  25.         if (z->_key < y->_key)
  26.         {
  27.             y->_left = z;
  28.         }
  29.         else
  30.         {
  31.             y->_right = z;
  32.         }
  33. }

首先创建一个结点，如果节点的值（key）是空（NULL）的话就结束函数，如果不为空的话就执行insert函数。insert函数的内容是循环树只要不为空，按照树的顺序找到合适的位置插入元素。

删除结点

  1. BSTNode *BinaryTree::remove(BSTNode *tree, BSTNode *z)  // 删除二叉树(tree)中的节点(z)，并返回被删除的节点
  2. {
  3.     BSTNode *x = NULL;
  4.     BSTNode *y = NULL;
  5.  
  6.     if (z->_left == NULL || z->_right == NULL)
  7.     {
  8.         y = z;
  9.     }
  10.     else
  11.     {
  12.         y = successor(z);
  13.     }
  14.  
  15.     if (y->_left != NULL)
  16.     {
  17.         x = y->_left;
  18.     }
  19.     else
  20.     {
  21.         x = y->_right;
  22.     }
  23.  
  24.     if (x != NULL)
  25.     {
  26.         x->_parent = y->_parent;
  27.     }
  28.  
  29.     if (y->_parent == NULL)
  30.     {
  31.         tree = x;
  32.     }
  33.     else
  34.         if (y == y->_parent->_left)
  35.         {
  36.             y->_parent->_left = x;
  37.         }
  38.         else
  39.         {
  40.             y->_parent->_right = x;
  41.         }
  42.  
  43.     if (y != z)
  44.     {
  45.         z->_key = y->_key;
  46.     }
  47.     return y;
  48. }
  1. void BinaryTree::remove(int _key)  // 删除二叉树(tree)中的节点(z)，并返回被删除的节点
  2. {
  3.     BSTNode *z, *node;
  4.     z = IteratorSearch(_root, _key); 
  5.     if (z == _root){
  6.         cout<<"Root can't be delete!"<<endl;
  7.     }
  8.     if (z != NULL && z->_parent != NULL && z != _root)
  9.     {
  10.         node = remove(_root, z);  
  11.         if (node != NULL)
  12.         {
  13.             delete node;
  14.         }
  15.     }
  16. }

销毁二叉树

  1. void BinaryTree::destroy(BSTNode *&tree)  //销毁二叉树
  2. {
  3.     if (tree == NULL)
  4.     {
  5.         return; 
  6.     }
  7.     if (tree->_left != NULL)
  8.     {
  9.         return destroy(tree->_left);
  10.     }
  11.     if (tree->_right != NULL)
  12.     {
  13.         return destroy(tree->_right);
  14.     }
  15.     delete tree;
  16.     tree = NULL;
  17. }
  18.  
  19.  
  20. void BinaryTree::destroy()  //销毁二叉树
  21. {
  22.     destroy(_root);
  23. }

完整代码

  1. /*
  2.     文件创建者: 112233-星澜-imimbert
  3.     创建日期: 2023.1.12 12:33
  4.     功能: 二叉树
  5. */
  6. #include <iostream>
  7. using namespace std;
  8.  
  9. class BSTNode
  10. {
  11. public:
  12.     int _key;  
  13.     BSTNode *_left;  //左子节点
  14.     BSTNode *_right; //右子节点
  15.     BSTNode *_parent;  //父节点
  16.      
  17.     BSTNode(int k = 0, BSTNode *l = NULL, BSTNode *r = NULL, BSTNode *p = NULL) : _key(k), _left(l), _right(r), _parent(p) {};  //初始化列表
  18. };
  19.  
  20.  
  21. class BinaryTree
  22. {
  23. /****
  24.     * @author 112233-imimbert-星澜
  25.     * @since -verson: 1.0.0
  26.     * @date 2021-01-12
  27.     * @pre 二叉树已经创建
  28.     * @include iostream
  29. ****/
  30. public:
  31.     BinaryTree();  
  32.     ~BinaryTree();  
  33.  
  34.     void insert(int _key);  //将_key节点插入到二叉树中
  35.     void PreOrder();  //前序二叉树遍历
  36.     void InOrder();  //中序二叉树遍历
  37.     void PostOrder();  //后序二叉树遍历
  38.  
  39.     BSTNode *search(int _key);  //递归实现，在二叉树中查找_key节点
  40.     BSTNode *IteratorSearch(int _key);  //迭代实现，在二叉树中查找_key节点
  41.  
  42.     BSTNode *successor(BSTNode *x);  //找节点(x)的后继节点。即，查找"二叉树中数据值大于该节点"的"最小节点"
  43.     BSTNode *predecessor(BSTNode *x);  //找节点(x)的前驱节点。即，查找"二叉树中数据值小于该节点"的"最大节点"
  44.  
  45.     void remove(int _key);  //删除_key节点
  46.  
  47.     void destroy();  //销毁二叉树
  48.  
  49.  
  50. private:
  51.     BSTNode *_root;  //根节点
  52.     void PreOrder(BSTNode *tree);  //前序二叉树遍历
  53.     void InOrder(BSTNode *tree);  //中序二叉树遍历
  54.     void PostOrder(BSTNode *tree);  //后序二叉树遍历
  55.  
  56.     BSTNode *search(BSTNode *x, int _key);  //递归实现，在”二叉树x“中查找_key节点
  57.     BSTNode *IteratorSearch(BSTNode *x, int _key);  //迭代实现，在“二叉树x”中查找_key节点
  58.  
  59.     BSTNode *minimum(BSTNode *tree);  //查找最小节点：返回tree为根节点的二叉树的最小节点
  60.     BSTNode *maximum(BSTNode *tree);  //查找最大节点：返回tree为根节点的二叉树的最大节点
  61.  
  62.     void insert(BSTNode *&tree, BSTNode *z);  // 将节点(z)插入到二叉树(tree)中
  63.  
  64.     BSTNode *remove(BSTNode *tree, BSTNode *z);  // 删除二叉树(tree)中的节点(z)，并返回被删除的节点
  65.  
  66.     void destroy(BSTNode *&tree);  //销毁二叉树
  67. };
  68.  
  69.  
  70. BinaryTree::BinaryTree() :_root(NULL) {}; 
  71.  
  72. BinaryTree::~BinaryTree() 
  73. {
  74.     destroy();
  75. }
  76.  
  77.  
  78. void BinaryTree::insert(int _key)  //将_key节点插入到二叉树中
  79. {
  80.     BSTNode *z = new BSTNode(_key, NULL, NULL, NULL);
  81.     if (z == NULL)
  82.     {
  83.         return;  
  84.     }
  85.     insert(_root, z); 
  86. }
  87.  
  88.  
  89. void BinaryTree::PreOrder(BSTNode *tree)  //前序二叉树遍历
  90. {
  91.     if (tree != NULL)
  92.     {
  93.         cout << tree->_key << " ";
  94.         PreOrder(tree->_left);
  95.         PreOrder(tree->_right);
  96.     }
  97. }
  98. void BinaryTree::PreOrder()
  99. {
  100.     PreOrder(_root); 
  101. }
  102.  
  103.  
  104. void BinaryTree::InOrder(BSTNode *tree)  //中序二叉树遍历
  105. {
  106.     if (tree != NULL)
  107.     {
  108.         InOrder(tree->_left);
  109.         cout << tree->_key << " ";
  110.         InOrder(tree->_right);
  111.     }
  112. }
  113. void BinaryTree::InOrder()
  114. {
  115.     InOrder(_root);  
  116. }
  117. void BinaryTree::PostOrder(BSTNode *tree)  //后序二叉树遍历
  118. {
  119.     if (tree != NULL)
  120.     {
  121.         PostOrder(tree->_left);
  122.         PostOrder(tree->_right);
  123.         cout << tree->_key << " ";
  124.     }
  125. }
  126. void BinaryTree::PostOrder()
  127. {
  128.     PostOrder(_root);  
  129. }
  130. BSTNode *BinaryTree::search(BSTNode *x, int _key)  //递归实现，在”二叉树x“中查找_key节点
  131. {
  132.     if (x == NULL || _key == x->_key)
  133.     {
  134.         return x;
  135.     }
  136.     if (_key < x->_key)
  137.     {
  138.         return search(x->_left, _key);
  139.     }
  140.     else
  141.     {
  142.         return search(x->_right, _key);
  143.     }
  144. }
  145. BSTNode *BinaryTree::search(int _key)
  146. {
  147.     return search(_root, _key);  
  148. }
  149. BSTNode *BinaryTree::IteratorSearch(BSTNode *x, int _key)  //迭代实现，在“二叉树x”中查找_key节点
  150. {
  151.     while (x != NULL && _key != x->_key)
  152.     {
  153.         if (_key < x->_key)
  154.         {
  155.             x = x->_left;
  156.         }
  157.         else
  158.         {
  159.             x = x->_right;
  160.         }
  161.     }
  162.     return x;
  163. }
  164. BSTNode *BinaryTree::IteratorSearch(int _key)
  165. {
  166.     return IteratorSearch(_root, _key);  //传入根节点和待查找的关键字_key
  167. }
  168. BSTNode *BinaryTree::minimum(BSTNode *tree)  //查找最小节点：返回tree为根节点的二叉树的最小节点。
  169. {
  170.     if (tree == NULL)
  171.     {
  172.         return NULL;
  173.     }
  174.     while (tree->_left != NULL)
  175.     {
  176.         tree = tree->_left;
  177.     }
  178.     return tree;
  179. }
  180.  
  181. BSTNode *BinaryTree::maximum(BSTNode *tree)  //查找最大节点：返回tree为根节点的二叉树的最大节点。
  182. {
  183.     while (tree->_right != NULL)
  184.     {
  185.         tree = tree->_right;
  186.     }
  187.     return tree;
  188. }
  189. BSTNode *BinaryTree::successor(BSTNode *x)  //找节点(x)的后继节点，也就是该节点的右子树中的最小节点
  190. {
  191.     BSTNode *y = NULL;
  192.     if (x->_right != NULL)
  193.     {
  194.         return minimum(x->_right);  
  195.     }
  196.     y  = x->_parent;
  197.     while (y != NULL && x == y->_right)
  198.     {
  199.         x = y;
  200.         y = y->_parent;
  201.     }
  202.     return y;
  203. }
  204.  
  205.  
  206. BSTNode *BinaryTree::predecessor(BSTNode *x)  //找节点(x)的前驱节点是该节点的左子树中的最大节点。
  207. {
  208.     BSTNode *y = NULL;
  209.     if (x->_left != NULL)
  210.     {
  211.         return maximum(x->_left);
  212.     }
  213.     y = x->_parent;
  214.     while (y != NULL && x == y->_left)
  215.     {
  216.         x = y;
  217.         y = y->_parent;
  218.     }
  219.     return y;
  220. }
  221.  
  222.  
  223. void BinaryTree::insert(BSTNode *&tree, BSTNode *z)  // 将节点(z)插入到二叉树(tree)中
  224. {
  225.     BSTNode *y = NULL;
  226.     BSTNode *x = tree;
  227.  
  228.     while (x != NULL) 
  229.     {
  230.         y = x;
  231.         if (z->_key < x->_key)
  232.         {
  233.             x = x->_left;
  234.         }
  235.         else
  236.         {
  237.             x = x->_right;
  238.         }
  239.     }
  240.  
  241.     z->_parent = y;
  242.     if (y == NULL)
  243.     {
  244.         tree = z;
  245.     }
  246.     else
  247.         if (z->_key < y->_key)
  248.         {
  249.             y->_left = z;
  250.         }
  251.         else
  252.         {
  253.             y->_right = z;
  254.         }
  255. }
  256.  
  257.  
  258. BSTNode *BinaryTree::remove(BSTNode *tree, BSTNode *z)  // 删除二叉树(tree)中的节点(z)，并返回被删除的节点
  259. {
  260.     BSTNode *x = NULL;
  261.     BSTNode *y = NULL;
  262.  
  263.     if (z->_left == NULL || z->_right == NULL)
  264.     {
  265.         y = z;
  266.     }
  267.     else
  268.     {
  269.         y = successor(z);
  270.     }
  271.  
  272.     if (y->_left != NULL)
  273.     {
  274.         x = y->_left;
  275.     }
  276.     else
  277.     {
  278.         x = y->_right;
  279.     }
  280.  
  281.     if (x != NULL)
  282.     {
  283.         x->_parent = y->_parent;
  284.     }
  285.  
  286.     if (y->_parent == NULL)
  287.     {
  288.         tree = x;
  289.     }
  290.     else
  291.         if (y == y->_parent->_left)
  292.         {
  293.             y->_parent->_left = x;
  294.         }
  295.         else
  296.         {
  297.             y->_parent->_right = x;
  298.         }
  299.  
  300.     if (y != z)
  301.     {
  302.         z->_key = y->_key;
  303.     }
  304.     return y;
  305. }
  306.  
  307.  
  308. void BinaryTree::remove(int _key)  // 删除二叉树(tree)中的节点(z)，并返回被删除的节点
  309. {
  310.     BSTNode *z, *node;
  311.     z = IteratorSearch(_root, _key); 
  312.     if (z == _root){
  313.         cout<<"Root can't be delete!"<<endl;
  314.     }
  315.     if (z != NULL && z->_parent != NULL && z != _root)
  316.     {
  317.         node = remove(_root, z);  
  318.         if (node != NULL)
  319.         {
  320.             delete node;
  321.         }
  322.     }
  323. }
  324.  
  325.  
  326. void BinaryTree::destroy(BSTNode *&tree)  //销毁二叉树
  327. {
  328.     if (tree == NULL)
  329.     {
  330.         return; 
  331.     }
  332.     if (tree->_left != NULL)
  333.     {
  334.         return destroy(tree->_left);
  335.     }
  336.     if (tree->_right != NULL)
  337.     {
  338.         return destroy(tree->_right);
  339.     }
  340.     delete tree;
  341.     tree = NULL;
  342. }
  343.  
  344.  
  345. void BinaryTree::destroy()  //销毁二叉树
  346. {
  347.     destroy(_root);
  348. }
  349.  
  350.  
  351. int main()
  352. {
  353.     /************************/
  354.     /*          插入
  355.     /************************/
  356.     BinaryTree *tree = new BinaryTree();
  357.     int array[6] = {12, 33, 18, 24, 44, 66};
  358.     cout << "二叉树数值：" << endl;
  359.     for (int i = 0; i < 6; i++)
  360.     {
  361.         cout << array[i] << " ";
  362.         tree->insert(array[i]);  //调用插入函数，生成二叉查找树
  363.     }
  364.  
  365.     cout << endl << endl;
  366.  
  367.  
  368.     /************************/
  369.     /*          遍历           
  370.     /************************/
  371.     cout << "前序遍历：";
  372.     tree->PreOrder();
  373.     cout << endl;
  374.  
  375.     cout << "中序遍历：";
  376.     tree->InOrder();
  377.     cout << endl;
  378.  
  379.     cout << "后序遍历：";
  380.     tree->PostOrder();
  381.     cout << endl << endl;
  382.  
  383.  
  384.     /************************/
  385.     /*          查找           
  386.     /************************/
  387.     int _keyword;  //查找节点的关键字
  388.     cout << "请输入要查找的节点：";
  389.     cin >> _keyword;
  390.     cout << endl;
  391.     BSTNode *node = tree->IteratorSearch(_keyword);  //获取数值的地址
  392.     if (node)  //判断有没有地址
  393.     {
  394.         cout << "关键字为“" << _keyword << "”的节点，存在。" << endl ;
  395.     }
  396.     else
  397.     {
  398.         cout << "关键字为“" << _keyword << "”的节点，不存在。" << endl;
  399.     }
  400.     cout << endl << endl;
  401.  
  402.  
  403.     /************************/
  404.     /*          删除
  405.     /************************/
  406.     int DelNode;  //要删除的节点
  407.     cout << "请输入要删除的节点：";
  408.     cin >> DelNode;
  409.     tree->remove(DelNode);
  410.     cout << endl;
  411.  
  412.     cout << "删除操作后，(前序)遍历：";
  413.     tree->PreOrder();
  414.     cout << endl;
  415.     cout << "删除操作后，(中序)遍历：";
  416.     tree->InOrder();
  417.     cout << endl;
  418.     cout << "删除操作后，(后序)遍历：";
  419.     tree->PostOrder();
  420.     cout << endl << endl;
  421.     
  422.  
  423.     /************************/
  424.     /*          销毁
  425.     /************************/
  426.     tree->destroy();
  427.     system("pause");
  428.     return 0;
  429. }
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小丑西瓜9/article/detail/246271
推荐阅读
相关标签

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

  

闽ICP备14008679号