首页 > > 程序设计 > C/C++ >

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

2019-01-01 23:15:53来源：博客园 阅读 ()

新老客户大回馈,云服务器低至5折

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

用到的测试图数据例子

第一、构建节点

 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

 

第二、二叉树头文件定义

 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

 

第三、搜索二叉树的插入

1）如果二叉树查找树为空节点，则插入节点就为根节点

2）如果二叉查找树为非空节点，就需要先找到待插入节点，查找原则就是从根节点开始，如果大于根就右边走，小于根就左边走，直到找到合适节点，

下面代码中的最终找到的temp 就是待插入节点.

 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）用节点左边孩子的最大值替换该节点，其他节点位置保持不变

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

 

  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

 

第五、二叉树的搜索查找

由于搜索二叉树本身是已经排序好的，查找过程相对简单，从根节点，逐个排查，大于根向右，小于根向左，直到叶子节点. 

template<typename T>
inline BSTNode<T>* BST<T>::search(T k)
{
    BSTNode<T>*node = root;
    while (node!=NULL)
    {
        if (k<node->data)
        {
            node = node->lChild;
        }
        else if (k> node->data)
        {
            node = node->rChild;
        }
        else {
            break;
        }
    }
    return node;
}
View Code

 

第六、二叉搜索树的排序

根据二叉所有树的特性，这里所谓排序，其实就是二叉树的中序遍历，其他的几种遍历不在这里赘述，知识调整下结构即可

template<typename T>
void BST<T>::inSort(BSTNode<T>* node)
{
    if (node!=NULL)
    {
        inSort(node->lChild);
        std::cout << node->data<<",";
        inSort(node->rChild);
    }
}
View Code

 

第七、测试程序

 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

测试结果

 所有完整程序代码

  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

 

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有

上一篇：PE 学习之路 —— DOS 头、NT 头

下一篇：Parallel Pattern Library(PPL)学习笔记

相关文章

IDC资讯： 主机资讯 注册资讯 托管资讯 vps资讯 网站建设

网站运营： 建站经验 策划盈利 搜索优化 网站推广 免费资源

网站联盟： 联盟新闻 联盟介绍 联盟点评 网赚技巧

行业资讯： 搜索引擎 网络游戏 电子商务 广告传媒

网络编程： Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它

服务器技术： Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护

软件技巧： 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷

网页制作： FrontPages Dreamweaver Javascript css photoshop fireworks Flash

程序设计： Java技术 C/C++ VB delphi

网络知识： 网络协议 网络安全 网络管理 组网方案 Cisco技术

操作系统： Win2000 WinXP Win2003 Mac OS Linux FreeBSD

热门词条
最新资讯
热门关注
热门标签