删除二叉排序树中的一个节点

删除二叉排序树中的一个节点

假设被删结点是p,其双亲是f,设p是f的左孩子,三种情况

  1. 若结点p是叶子结点,则只需修改其双亲结点f的指针即可。
  2. 若结点*p只有左子树PL或者只有右子树PR,则只要使PL或PR 成为其双亲结点的左子树即可。
  3. 若结点p的左、右子树均非空,先找到p的中序前趋结点s【s是p的左子树中的最右下的结点,它的右链域为空】
    ① 以
    p的中序前趋结点s代替p【s的数据复制到p中】,将s的左子树链到s的双亲结点q的左/右链上
    ② 令
    p的左子树直接链到p的双亲结点f的左链上,而p的右子树链到p的中序前趋结点*s的右链上。
void DelBST(BTree *T,int key){
	BTree *p=T,*f,*q,*s,*root=T;
	while(p){
	if(p->data==key) break; //找到关键字为key的结点
		f=p;//记下关键字key节点的父节点
	p=(key<p->data)?p->lchild:p->rchild;//分别在*p的左、右子树中查找
 }
	if(!p) return;//二叉排序树中无关键字为key的结点
	if(p->lchild==NULL&&p->rchild==NULL){//p没有左右子树
	if(p==T) T=NULL;//删除的是根节点
	else if(p==f->lchild)
		f->lchild=NULL;
	else
		f->rchild=NULL;
 	free(p);
 }
 else if(p->lchild==NULL&&p->rchild!=NULL)//p无左子树有右子树
 { 
	if(f->lchild==p)
		f->lchild=p->rchild; //将p的右子树链接到其父结点的左链上
	else
		f->rchild=p->rchild; //将p的右子树链接到其父结点的右链上
	free(p);
 }
    else if(p->rchild==NULL&&p->lchild!=NULL)//p有左子树无右子树
 { 
	if (f->lchild==p)               
		f->lchild=p->lchild; //将p的左子树链接到其父结点的左链上
	else
		f->rchild=p->lchild; //将p的左子树链接到其父结点的右链上
	free(p);
 }
	else if(p->lchild!=NULL&&p->rchild!=NULL)//p既有左子树又有右子树
 {
	q=p;
	s=p->lchild;//转左
	while(s->rchild){//然后向右到尽头
		q=s;
		s=s->rchild;//s指向被删节点的“前驱”(中序前驱)
  }
	p->data=s->data;//以p的中序前趋结点s代替p(即把s的数据复制到p中)
	if(q!=p) q->rchild=s->lchild;//重接q的右子树
	else q->lchild=s->lchild;//重接q的左子树。
	free(s);
    }
}

相关刷题笔记博客
竞赛常用模板整理(ACM/ICPC/CCSP)
Leetcode算法刷题笔记1-链表
Leetcode算法刷题笔记2-栈、队、堆
Leetcode算法刷题笔记3-递归与回溯
Leetcode算法刷题笔记4-贪心
Leetcode算法刷题笔记5-二叉树
Leetcode算法刷题笔记6-图
Leetcode算法刷题笔记7-动态规划
Leetcode算法刷题笔记8-二分查找

上一篇:数据结构(C语言)-二叉树子系统(实验)


下一篇:二叉树创建、前中后序遍历、节点数、叶子节点数、深度、交换左右子树代码实现