c/c++语言开发共享c++ 搜索二叉树 插入,删除,遍历操作

搜索二叉树是一种具有良好排序和查找性能的二叉树数据结构,包括多种操作,本篇只介绍插入,排序(遍历),和删除操作,重点是删除操作比较复杂,用到的例子也是本人亲自画的 用到的测试图数据例子 第一、构建节点 1 template <typename T> class BST; 2 template <ty …

搜索二叉树是一种具有良好排序和查找性能的二叉树数据结构,包括多种操作,本篇只介绍插入,排序(遍历),和删除操作,重点是删除操作比较复杂,用到的例子也是本人亲自画的

用到的测试图数据例子

c++ 搜索二叉树 插入,删除,遍历操作

第一、构建节点

c++ 搜索二叉树 插入,删除,遍历操作

 1 template <typename t> class bst;   2 template <typename t> class bstnode {   3 public:   4     friend class bst<t>;   5     bstnode() {   6         lchild = rchild = parent = null;   7         data = null;   8     }   9     bstnode(t d) {  10         lchild = rchild = parent = null;  11         data = d;  12     }  13 private:  14     bstnode<t> *lchild, *rchild, *parent;  15     t data;  16 };

view code

第二、二叉树头文件定义

c++ 搜索二叉树 插入,删除,遍历操作

 1 template<typename t> class bst {   2 public:       3     bst() { }    4    5     //插入操作   6     void insert(bstnode<t>*node);   7    8     //二叉查找树的中序遍历,就相当于排序了   9     void insort(bstnode<t>*node);  10   11     //按节点删除  12     void deletenode(bstnode<t>* node);  13   14     //按数值删除  15     void deletenode(const t& t);  16   17     bstnode<t>* search(t key);  18     bstnode<t>* root=null;  19   20 private:      21     int count;  22 };

view code

第三、搜索二叉树的插入

c++ 搜索二叉树 插入,删除,遍历操作

 1 template<typename t>   2 void bst<t>::insert(bstnode<t>* node)   3 {   4     bstnode<t>* curr, *temp = null;   5     curr = root;   6     while (null!= curr) //遍历二叉树,找到应该插入的父节点   7     {   8         temp = curr;   9         if (node->data>curr->data)  10         {  11             curr = curr->rchild;  12         }  13         else {  14             curr = curr->lchild;  15         }  16     }  17     node->parent = temp;//temp 代码当前最后遍历的node,设置node->parent为该节点  18     if (temp==null)  19     {  20         root = node;  21         count++;  22     }  23     else {  24         if (node->data<temp->data)  25         {  26             temp->lchild = node;  27             count++;  28         }  29         else {  30             temp->rchild = node;  31             count++;  32         }  33     }  34 }

view code

第四、搜索二叉树的删除

 删除包含多种情况,

1. 如果节点没有子女,修改其父节点指针为null,删除即可

2. 如果该节点有左孩子情况,修改其父亲节点的指针和其左孩子的parent指针即可

3. 如果该节点有右孩子情况,修改其父亲节点的指针和其右孩子的parent指针即可

4.如果同时有左右孩子的情况,情况比较复杂,一般有2种方法处理

    1) 用节点右边孩子的最小值替换该节点,其他节点位置保持不变(本篇用这种方法)

    2)用节点左边孩子的最大值替换该节点,其他节点位置保持不变

c++ 搜索二叉树 插入,删除,遍历操作

后面测试例子是删除18 node,通过程序找到右边最小值20,用20 替换18,其他节点位置保持不动。

 

c++ 搜索二叉树 插入,删除,遍历操作

  1 template<typename t>    2 inline void bst<t>::deletenode(bstnode<t>* node)    3 {    4     bstnode<t>*p = node->parent;//获取node的父节点,这里很重要    5     if (node->lchild==null && node->rchild==null) //叶子节点直接删除    6     {    7         if (node==node->parent->lchild)    8         {    9             node->parent->lchild = null;   10         }   11         else {   12             node->parent->rchild = null;   13         }   14         delete node;   15         count--;   16     }   17     else if (node->rchild != null && node->lchild == null) {//存在右孩子   18         if (p==null)//说明节点为根节点   19         {   20             root = node->rchild;   21             count--;   22         }   23         else {   24             node->rchild->parent = p;   25             if (p->lchild==node) //判断是父节点的左孩子还是右孩子   26             {   27                 p->lchild = node->rchild;   28             }   29             else {   30                 p->rchild = node->rchild;   31             }   32             delete node;   33             count--;   34         }           35     }   36     else if (node->lchild!=null && node->rchild==null)//存在左孩子   37     {   38         if (p==null)   39         {   40             root = root->lchild;   41             count--;   42         }   43         else {   44             node->lchild->parent = p;   45             if (p->lchild==node)   46             {   47                 p->lchild = node->lchild;   48             }   49             else {   50                 p->rchild = node->lchild;   51             }   52             delete node;   53             count--;   54         }   55     }   56     else {   57         bstnode<t>*left, *curp=null;   58         left = node->rchild; //本方案是找右侧最小值,替换node节点,其他节点保持不动即可   59         while (left!=null)   60         {   61             curp = left;   62             left = left->lchild;   63         }   64    65         if (curp->rchild!=null)   66         {   67             if (curp->lchild==curp)   68             {   69                 curp->parent->lchild = curp->rchild;   70             }   71             else {   72                 curp->parent->rchild = curp->rchild;   73             }   74         }   75         else {   76             if (curp->parent->lchild==curp)   77             {   78                 curp->parent->lchild = null;   79             }   80             else {   81                 curp->parent->rchild = null;   82             }   83             //curp->parent->lchild = null;   84         }   85         //替curp 替换 node   86         curp->parent = p;   87         curp->lchild = node->lchild;   88         curp->rchild = node->rchild;   89    90         if (p->lchild==node)//判断node 是p 的左孩子还是右孩   91         {   92             p->lchild = curp;   93         }   94         else {   95             p->rchild = curp;   96         }   97         delete node;   98         count--;   99     }  100 }

view code

第五、测试程序

c++ 搜索二叉树 插入,删除,遍历操作

 1 #include "pch.h"   2 #include <iostream>   3 #include "bstree.h"   4 using namespace std;   5    6 int main()   7 {     8     // 树结构示意   9     //     30  10     //    /    11     //  15   25  12     // /    13     //9    18  14     //   /     15     //  16   25  16     //      /    17     //    20    26    18     bst<int> sbt;  19     sbt.insert(new bstnode<int>(30));  20     sbt.insert(new bstnode<int>(15));  21     sbt.insert(new bstnode<int>(9));  22     sbt.insert(new bstnode<int>(18));  23     sbt.insert(new bstnode<int>(16));  24     sbt.insert(new bstnode<int>(25));  25     sbt.insert(new bstnode<int>(20));  26     sbt.insert(new bstnode<int>(26));  27     sbt.insert(new bstnode<int>(35));  28   29     cout << "搜索树排序后:";  30     sbt.insort(sbt.root);  31   32     sbt.deletenode(18);  33   34     cout << endl << "删除18 后排序:";  35   36     sbt.insort(sbt.root);  37 }

view code

测试结果

c++ 搜索二叉树 插入,删除,遍历操作

 第六、所有程序代码

c++ 搜索二叉树 插入,删除,遍历操作

  1 #pragma once    2 template <typename t> class bst;    3 template <typename t> class bstnode {    4 public:    5     friend class bst<t>;    6     bstnode() {    7         lchild = rchild = parent = null;    8         data = null;    9     }   10     bstnode(t d) {   11         lchild = rchild = parent = null;   12         data = d;   13     }   14 private:   15     bstnode<t> *lchild, *rchild, *parent;   16     t data;   17 };   18    19 template<typename t> class bst {   20 public:       21     bst() { }    22    23     //插入操作   24     void insert(bstnode<t>*node);   25    26     //二叉查找树的中序遍历,就相当于排序了   27     void insort(bstnode<t>*node);   28    29     //按节点删除   30     void deletenode(bstnode<t>* node);   31    32     //按数值删除   33     void deletenode(const t& t);   34    35     bstnode<t>* search(t key);   36     bstnode<t>* root=null;   37    38 private:       39     int count;   40 };   41    42 template<typename t>   43 void bst<t>::insert(bstnode<t>* node)   44 {   45     bstnode<t>* curr, *temp = null;   46     curr = root;   47     while (null!= curr) //遍历二叉树,找到应该插入的父节点   48     {   49         temp = curr;   50         if (node->data>curr->data)   51         {   52             curr = curr->rchild;   53         }   54         else {   55             curr = curr->lchild;   56         }   57     }   58     node->parent = temp;//temp 代码当前最后遍历的node,设置node->parent为该节点   59     if (temp==null)   60     {   61         root = node;   62         count++;   63     }   64     else {   65         if (node->data<temp->data)   66         {   67             temp->lchild = node;   68             count++;   69         }   70         else {   71             temp->rchild = node;   72             count++;   73         }   74     }   75 }   76    77 template<typename t>   78 void bst<t>::insort(bstnode<t>* node)   79 {   80     if (node!=null)   81     {   82         insort(node->lchild);   83         std::cout << node->data<<",";   84         insort(node->rchild);   85     }   86 }   87    88 template<typename t>   89 inline void bst<t>::deletenode(bstnode<t>* node)   90 {   91     bstnode<t>*p = node->parent;//获取node的父节点,这里很重要   92     if (node->lchild==null && node->rchild==null) //叶子节点直接删除   93     {   94         if (node==node->parent->lchild)   95         {   96             node->parent->lchild = null;   97         }   98         else {   99             node->parent->rchild = null;  100         }  101         delete node;  102         count--;  103     }  104     else if (node->rchild != null && node->lchild == null) {//存在右孩子  105         if (p==null)//说明节点为根节点  106         {  107             root = node->rchild;  108             count--;  109         }  110         else {  111             node->rchild->parent = p;  112             if (p->lchild==node) //判断是父节点的左孩子还是右孩子  113             {  114                 p->lchild = node->rchild;  115             }  116             else {  117                 p->rchild = node->rchild;  118             }  119             delete node;  120             count--;  121         }          122     }  123     else if (node->lchild!=null && node->rchild==null)//存在左孩子  124     {  125         if (p==null)  126         {  127             root = root->lchild;  128             count--;  129         }  130         else {  131             node->lchild->parent = p;  132             if (p->lchild==node)  133             {  134                 p->lchild = node->lchild;  135             }  136             else {  137                 p->rchild = node->lchild;  138             }  139             delete node;  140             count--;  141         }  142     }  143     else {  144         bstnode<t>*left, *curp=null;  145         left = node->rchild; //本方案是找右侧最小值,替换node节点,其他节点保持不动即可  146         while (left!=null)  147         {  148             curp = left;  149             left = left->lchild;  150         }  151   152         if (curp->rchild!=null)  153         {  154             if (curp->lchild==curp)  155             {  156                 curp->parent->lchild = curp->rchild;  157             }  158             else {  159                 curp->parent->rchild = curp->rchild;  160             }  161         }  162         else {  163             if (curp->parent->lchild==curp)  164             {  165                 curp->parent->lchild = null;  166             }  167             else {  168                 curp->parent->rchild = null;  169             }  170             //curp->parent->lchild = null;  171         }  172         //替curp 替换 node  173         curp->parent = p;  174         curp->lchild = node->lchild;  175         curp->rchild = node->rchild;  176   177         if (p->lchild==node)//判断node 是p 的左孩子还是右孩  178         {  179             p->lchild = curp;  180         }  181         else {  182             p->rchild = curp;  183         }  184         delete node;  185         count--;  186     }  187 }  188   189 template<typename t>  190 inline void bst<t>::deletenode(const t & k)  191 {  192     bstnode<t>*node = search(k);  193     if (node!=null)  194     {  195         deletenode(node);  196     }  197 }  198   199   200 template<typename t>  201 inline bstnode<t>* bst<t>::search(t k)  202 {  203     bstnode<t>*node = root;  204     while (node!=null)  205     {  206         if (k<node->data)  207         {  208             node = node->lchild;  209         }  210         else if (k> node->data)  211         {  212             node = node->rchild;  213         }  214         else {  215             break;  216         }  217     }  218     return node;  219 }

bstree.h

 

本文来自网络收集,不代表计算机技术网立场,如涉及侵权请点击右边联系管理员删除。

如若转载,请注明出处:https://www.ctvol.com/c-cdevelopment/605729.html

(0)
上一篇 2021年5月13日
下一篇 2021年5月13日

精彩推荐