二叉排序树删除.cpp

来自「这里面包括数据结构多数的算法」· C++ 代码 · 共 107 行

#include <stdio.h>
#include <stdlib.h>
typedef int InfoType;

typedef int KeyType;			//假定关键字类型为整数
typedef struct node				//结点类型
{
	KeyType key;				//关键字项
	InfoType otherinfo;			//其它数据域，InfoType视应用情况而定 下面不处理它
	struct node *lchild,*rchild;//左右孩子指针
}BSTNode;
typedef BSTNode *BSTree;		//BSTree是二叉排序树的类型

void main()
{
	void InsertBST(BSTree *Tptr,KeyType key);
	BSTree CreateBST(void);
	void DelBSTNode(BSTree *Tptr,KeyType key);
	void ListBinTree(BSTree T);		//用广义表表示二叉树
	BSTree T;
	int key;
	printf("请输入关键字（输入0为结束标志）：\n");
	T=CreateBST();
	ListBinTree(T);
	printf("\n");
	printf("请输入欲删除关键字：");
	scanf("%d",&key);
	DelBSTNode(&T,key);
	ListBinTree(T);
	printf("\n");
}

void InsertBST(BSTree *Tptr,KeyType key)
{	//若二叉排序树*Tptr中没有关键字为key，则插入，否则直接返回
	BSTNode *f,*p=*Tptr;			//p的初值指向根结点
	while(p){						//查找插入位置
		if(p->key==key) return;		//树中已有key，无须插入
		f=p;						//f保存当前查找的结点
		p=(key<p->key)? p->lchild:p->rchild;
		//若key<p->key，则在左子树中查找，否则在右子树中查找
	}
	p=(BSTNode *)malloc(sizeof(BSTNode));
	p->key=key;p->lchild=p->rchild=NULL;	//生成新结点
	if(*Tptr==NULL)					//原树为空
		*Tptr=p;					//新插入的结点为新的根
	else//原树非空时将新结点*p作为*f的左孩子或右孩子插入
		if(key<f->key)
			f->lchild=p;
		else f->rchild=p;
}

BSTree CreateBST(void)
{	//输入一个结点序列，建立一棵二叉排序树，将根结点指针返回
	BSTree T=NULL;				//初始时T为空树
	KeyType key;
	scanf("%d",&key);			//读入一个关键字
	while(key){					//假设key=0是输入结束标志
		InsertBST(&T,key);		//将key插入二叉排序树T
		scanf("%d",&key);		//读入下一关键字
	}
	return T;					//返回建立的二叉排序树的根指针
}

void DelBSTNode(BSTree *Tptr,KeyType key)
{	//在二叉排序树*Tptr中删去关键字为key的结点
	BSTNode *parent=NULL,*p=*Tptr,*q,*child;
	while(p){					//从根开始查找关键字为key的待删结点
		if(p->key==key) break;	//已找到，跳出查找循环
		parent=p;				//parent指向*p的双亲
		p=(key<p->key)?p->lchild:p->rchild;//parent指向*p的左或右子树中继续找
	}
	if(!p) return;				//找不到被删结点则返回
	q=p;						//q记住被删结点*p
	if(q->lchild && q->rchild)	//*q的两个孩子均非空，故找*q的中序后继*p
		for(parent=q,p=q->rchild; p->lchild; parent=p,p=p->lchild);
		//现在情况(3)已被转换为情况(2)，而情况(1)相当于是情况(2)中child=NULL状况
		child=(p->lchild)? p->lchild:p->rchild;//若是情况(2)，则child非空；否则child为空
		if(!parent)				//*p的双亲为空，说明*p为根，删*p后应修改根指针
			*Tptr=child;		//若是情况(1)，则删去*p后，树为空；否则child变为根
		else {		//*p不是根，将*p的孩子和*p的双亲进行连接，*p从树上被摘下
			if(p==parent->lchild)		//*p是双亲的左孩子
				parent->lchild=child;	//*child作为*parent的左孩子
			else parent->rchild=child;	//*child作为*parent的右孩子
			if(p!=q)					//是情况(3)，需将*p的数据复制到*q
				q->key=p->key;			//若还有其它数据域亦需复制
	}
	free(p);							//释放*p占用的空间
}

//用广义表表示二叉树
void ListBinTree(BSTree T)
{
	if (T!=NULL)
	{
		printf("%d",T->key);
		if (T->lchild!=NULL||T->rchild!=NULL)
		{
			printf("(");
			ListBinTree(T->lchild);
			if (T->rchild!=NULL)
				printf(",");
			ListBinTree(T->rchild);
			printf(")");
		}
	}
}