c++ 搜索二叉树 插入，删除，遍历操作
程序员文章站
2022-04-13 14:41:00
搜索二叉树是一种具有良好排序和查找性能的二叉树数据结构，包括多种操作，本篇只介绍插入，排序（遍历），和删除操作，重点是删除操作比较复杂，用到的例子也是本人亲自画的 用到的测试图数据例子 第一、构建节点 1 template class BST; 2 template
view code
view code
view code
view code
view code
bstree.h
搜索二叉树是一种具有良好排序和查找性能的二叉树数据结构，包括多种操作，本篇只介绍插入，排序（遍历），和删除操作，重点是删除操作比较复杂，用到的例子也是本人亲自画的
用到的测试图数据例子
第一、构建节点
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 };
第二、二叉树头文件定义
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 };
第三、搜索二叉树的插入
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 }
第四、搜索二叉树的删除
删除包含多种情况，
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 }
第五、测试程序
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 }
测试结果
第六、所有程序代码
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 }
上一篇： 人生苦短，你用什么？
下一篇： PyCharm学习笔记(二) 调试配置