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

2019-09-06| 发布者: admin| 查看: |

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

用到的测试图数据例子

第一、构建节点

 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;
 9 bstnode {
10 lchild = rchild = parent = null;
11 data = d;
13 private:
14 bstnode t *lchild, *rchild, *parent;
15 t data;
16 };

第二、二叉树头文件定义

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

第三、搜索二叉树的插入

 1 template typename t 
 2 void bst t ::insert
 4 bstnode t * curr, *temp = null;
 5 curr = root;
 6 while  //遍历二叉树,找到应该插入的父节点
 8 temp = curr;
 9 if 
11 curr = curr- rchild;
13 else {
14 curr = curr- lchild;
17 node- parent = temp;//temp 代码当前最后遍历的node,设置node- parent为该节点
18 if 
20 root = node;
21 count++;
23 else {
24 if 
26 temp- lchild = node;
27 count++;
29 else {
30 temp- rchild = node;
31 count++;
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
 4 bstnode t *p = node- parent;//获取node的父节点,这里很重要
 5 if  //叶子节点直接删除
 7 if 
 9 node- parent- lchild = null;
 10 }
 11 else {
 12 node- parent- rchild = null;
 13 }
 14 delete node;
 15 count--;
 16 }
 17 else if  {//存在右孩子
 18 if //说明节点为根节点
 19 {
 20 root = node- rchild;
 21 count--;
 22 }
 23 else {
 24 node- rchild- parent = p;
 25 if  //判断是父节点的左孩子还是右孩子
 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 //存在左孩子
 37 {
 38 if 
 39 {
 40 root = root- lchild;
 41 count--;
 42 }
 43 else {
 44 node- lchild- parent = p;
 45 if 
 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 
 60 {
 61 curp = left;
 62 left = left- lchild;
 63 }
 65 if 
 66 {
 67 if 
 68 {
 69 curp- parent- lchild = curp- rchild;
 70 }
 71 else {
 72 curp- parent- rchild = curp- rchild;
 73 }
 74 }
 75 else {
 76 if 
 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;
 90 if //判断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;
 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);
20 sbt.insert);
21 sbt.insert);
22 sbt.insert);
23 sbt.insert);
24 sbt.insert);
25 sbt.insert);
26 sbt.insert);
27 sbt.insert);
29 cout "搜索树排序后:";
30 sbt.insort;
32 sbt.deletenode;
34 cout endl "删除18 后排序:";
36 sbt.insort;
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;
 10 bstnode {
 11 lchild = rchild = parent = null;
 12 data = d;
 13 }
 14 private:
 15 bstnode t *lchild, *rchild, *parent;
 16 t data;
 17 };
 19 template typename t class bst {
 20 public: 
 21 bst { } 
 23 //插入操作
 24 void insert;
 26 //二叉查找树的中序遍历,就相当于排序了
 27 void insort;
 29 //按节点删除
 30 void deletenode;
 32 //按数值删除
 33 void deletenode;
 35 bstnode t * search;
 36 bstnode t * root=null;
 38 private: 
 39 int count;
 40 };
 42 template typename t 
 43 void bst t ::insert
 44 {
 45 bstnode t * curr, *temp = null;
 46 curr = root;
 47 while  //遍历二叉树,找到应该插入的父节点
 48 {
 49 temp = curr;
 50 if 
 51 {
 52 curr = curr- rchild;
 53 }
 54 else {
 55 curr = curr- lchild;
 56 }
 57 }
 58 node- parent = temp;//temp 代码当前最后遍历的node,设置node- parent为该节点
 59 if 
 60 {
 61 root = node;
 62 count++;
 63 }
 64 else {
 65 if 
 66 {
 67 temp- lchild = node;
 68 count++;
 69 }
 70 else {
 71 temp- rchild = node;
 72 count++;
 73 }
 74 }
 75 }
 77 template typename t 
 78 void bst t ::insort
 79 {
 80 if 
 81 {
 82 insort;
 83 std::cout node- data ",";
 84 insort;
 85 }
 86 }
 88 template typename t 
 89 inline void bst t ::deletenode
 90 {
 91 bstnode t *p = node- parent;//获取node的父节点,这里很重要
 92 if  //叶子节点直接删除
 93 {
 94 if 
 95 {
 96 node- parent- lchild = null;
 97 }
 98 else {
 99 node- parent- rchild = null;
100 }
101 delete node;
102 count--;
103 }
104 else if  {//存在右孩子
105 if //说明节点为根节点
106 {
107 root = node- rchild;
108 count--;
109 }
110 else {
111 node- rchild- parent = p;
112 if  //判断是父节点的左孩子还是右孩子
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 //存在左孩子
124 {
125 if 
126 {
127 root = root- lchild;
128 count--;
129 }
130 else {
131 node- lchild- parent = p;
132 if 
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 
147 {
148 curp = left;
149 left = left- lchild;
150 }
152 if 
153 {
154 if 
155 {
156 curp- parent- lchild = curp- rchild;
157 }
158 else {
159 curp- parent- rchild = curp- rchild;
160 }
161 }
162 else {
163 if 
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;
177 if //判断node 是p 的左孩子还是右孩
178 {
179 p- lchild = curp;
180 }
181 else {
182 p- rchild = curp;
183 }
184 delete node;
185 count--;
186 }
187 }
189 template typename t 
190 inline void bst t ::deletenode
191 {
192 bstnode t *node = search;
193 if 
194 {
195 deletenode;
196 }
197 }
200 template typename t 
201 inline bstnode t * bst t ::search
202 {
203 bstnode t *node = root;
204 while 
205 {
206 if 
207 {
208 node = node- lchild;
209 }
210 else if 
211 {
212 node = node- rchild;
213 }
214 else {
215 break;
216 }
217 }
218 return node;
219 }