先写BST树的定义及特点,然后记录BST数的删除操作 。
1 BST定义及特点
BST数是一棵特殊的二叉树,如何能得到一颗二叉搜索树呢?下面一个有序序列,经过二分搜索,得到的就是一颗BST树 。根节点就是当前一轮要搜索的中间节点 。
BST树称作二叉搜索树(Tree)或者二叉排序树( Sort Tree),它或者是一颗空树;或者是具有下列性质的二叉树:
1 、若左子树不为空,则左子树上所有节点的值均小于它的根节点的值
2 、若右子树不为空,则右子树上所有节点的值均大于它的根节点的值
3 、左右子树也分别满足二叉搜索树性质
![数据结构与算法_BST树_BST树的定义及删除操作](http://img.gansulong.com/231010/06411S926-0.jpg)
文章插图
特点 :每一个节点都满足 左孩子的值(不为空) < 父节点的值 < 右孩子的值(不为空);比如上图中,24 < 58 < 67
二叉树层数和节点的个数的关系;
二分搜索就是从根搜到叶子节点,因此,BST的时间复杂度是O(logN)
2 BST数删除操作
删除节点时,有两个概念需要分清楚:
前驱节点:当前节点左子树中值最大的节点 。
后继节点:当前节点右子树中值最小的节点,就是右子树中最左边的值 。
假设要删除的节点就是当前遍历到的节点 。
1 如果当前节点没有孩子节点,父节点地址域置为;
2 如果当前节点只有一个孩子节点,让父节点指向当前节点 。
3 如果当前节点有两个孩子节点,找到当前节点的前驱节点,用前驱节点覆盖当前节点的值,然后直接删除前驱或者后继节点的值 。
代码实现时候,先实现情况3 。
【数据结构与算法_BST树_BST树的定义及删除操作】
/* 功能:删除二叉树中的val节点** 参数:*const T & val: 待删除的节点*/void n_remove(const T & val){if (root_ == nullptr){return;}// 搜索待删除的节点,cur指向当前搜索的节点,parent指向cur的父节点Node *parent = nullptr;Node *cur = root_;while (cur != nullptr){if (cur->data_ == val)// 如果当前是根节点,说明找到了,先break出来,在情况1和2时处理 。{break;}else if (comp_(cur->data_, val))// 用函数对象比较,如果当前节点值小于val,就从当前节点的右边找{parent = cur;cur = cur->right_;}else// 否则就从左边找{parent = cur;cur = cur->left_;}}// 如果找不到要删除的节点,返回 if (cur == nullptr){return;}// 走到这里说明已经找到了当前要删除的节点:比如上图中67的情况// 开始判断,先判断如果当前待删除节点有两个孩子,找孩子的前驱节点if (cur->left_ != nullptr && cur->right_ != nullptr){parent = cur;Node *pre = cur->left_;while (pre->right_ != nullptr)// 找前驱节点{parent = pre;pre = pre->right_;}cur->data_ = pre->data_;cur = pre;// cur指向当前要删除的节点,parent指向其父节点 。}// 找出parent最后指向的左孩子还是右孩子Node *child = cre->left_;if (child == nullptr){child = cur->right_;}// 表示删除的是根节点:根节点的parent是空间点if (parent == nullptr){root_ = child;}else {// 把待删除节点 写入父节点中if (parent->left_ == cur){parent->left_ = child;}else{parent->right_ = child;}}delete cur;// 删除当前节点}
- 疏干井与降水井的区别 降水疏干井什么意思
- 新荣耀疑似与高通和联发科达成合作,小米还要继续饥渴营销么?
- 甲钻胺分散片的功效与作用
- 如何将小米手环2与手机连接
- AC与AP的IPv6功能介绍和配置实例
- 进位制与整数表示
- 当归煮蛋的做法与功效是什么 当归煮蛋的做法与功效
- 算法训练——Hankson的趣味题
- 3 高等数学 映射与函数
- C课设—图书管理系统