二叉排序树(BST)删除节点

定义:

空树或满足下列性质的二叉树:

1)若它的左子树不空,则左子树所有的关键字的值均小于根关键字的值

2)若它的右子树不空,则右子树所有的关键字的值均大于根关键字的值

3) 左右子树又各是一颗二叉排序树

中序遍历结果是一个增序序列

比较难搞的是BST删除节点

分析如下:

1)首先找到那个节点获取节点的指针位置和父节点指针位置

2)通过这两个指针进行判断获取删除的方案

设目标节点为P

(1)P无子树=>P是叶子节点

         如果父节点是空节点那么这个棵树只有一个节点直接root为空

         如果父节点不是空节点那么判断出P在父节点的位置并将这个位置设为                     空即可

(2)P有单子树

       将P的子树代替父节点的子树即可

(3)P有双子树

         找到P右子树A的最左边的节点B(找到比P值邻大值),交换P和B的值,然后把B节点按照(1)或(2)删除,这里有特殊情况

          1.A没有左子树,那么P与A交换值,然后用(1)或(2)删除A

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容