搜索二叉树是一种具有良好排序和查找性能的二叉树数据结构，包括多种操作，本篇只介绍插入，排序（遍历），和删除操作，重点是删除操作比较复杂，用到的例子也是本人亲自画的
用到的测试图数据例子
第一、构建节点
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 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
第五、测试程序
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
本文来自网络收集，不代表计算机技术网立场，如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址：https://www.ctvol.com/c-cdevelopment/605729.html