算法学习笔记（2）：带头结点的BST树

BST树（二叉搜索树/二叉排序树）
特点：1.不允许搜索码重复2.根大于左小于右
与堆的区别：堆根大于左和右，左右怎么排无关，二叉排序树则左右有序，中序遍历是从小到大。

//插入节点
bool InsertItem(BsTree &bt,keyType kx)
{
	BstNode *pa=bt.head;
	BstNode *p=bt.head->parent;
	while(p!=NULL&&p->data!=kx)
	{
		pa=p;
		p=kx<p->data?p->leftchild:p->rightchild;//找到插入的合适位置p
	}
	if(p!=NULL)
	{
		return false;
	}
	p=BuyNode(pa);//不存在则购买结点
	p->data=kx;
	if(pa==bt.head)//树中的第一个节点
	{
		bt.head->parent=p;
		bt.head->leftchild=p;
		bt.head->rightchild=p;
	}
	else
	{
		if(p->data<pa->data)
		{
			pa->leftchild=p;
			if(p->data<bt.head->data)//修改头结点左孩子的指向，即修改树中最小值
			{
				bt.head->leftchild=p;
			}
		}
		else
		{
			pa->rightchild=p;
			if(p->data>bt.head->data)
			{
				bt.head->rightchild=p;
			}
		}
	}
	bt.cursize+=1;
	return true;
}

//删除结点
bool DeleteItem(BsTree &bt,keyType kx)
{
	BstNode *p=FindValue(bt,kx);
	BstNode *pa=p->parent;
	if(p->leftchild != NULL && p->rightchild != NULL)//删除的结点为双分支，找到该结点的直接后继结点，用直接后继结点覆盖它，删除直接后继结点，问题转化为删除叶子结点
	{
		BstNode *nt = Next(bt,p);
		p->data = nt->data;
		p = nt;
	}
	BstNode *child = p->leftchild != NULL? p->leftchild: p->rightchild;

	if(child != NULL) child->parent = pa;//如果只有一个孩子则用这个孩子结点覆盖它，然后删除它的孩子结点就可以，问题同样转化为删除叶子结点
	if( p == bt.head)//要删除结点是根结点
	{
		bt.head->parent = child;//把头结点的父亲域指向他的孩子域
	}
	else
	{
		if(pa->leftchild==p)//要删除结点是左孩子
		{
			pa->leftchild=NULL;
		}
		else//要删除结点是右孩子
		{
			pa->rightchild=NULL;
		}
	}
	
	free(p);
	p=NULL;
	return true;
}

完整代码如下：

# include<iostream>
# include <iostream>
typedef int keyType;
typedef struct BstNode
{
	BstNode* leftchild;
	BstNode* rightchild;
	BstNode* parent;
	keyType data;
}BstNode;

//构造一个带头结点的树，头结点的leftchild存放树的最小值，rightchild存放最大值parent存放根root结点
typedef struct BsTree
{
	BstNode *head;//头结点
	int cursize;
}BsTree;
//购买节点
BstNode* BuyNode(BstNode* pa=NULL,BstNode* left=NULL,BstNode* right=NULL)
{
	BstNode* p=(BstNode*)malloc(sizeof(BstNode));
	p->parent=pa;
	p->leftchild=left;
	p->rightchild=right;
	return p;
}
//初始化二叉搜索树
void InitBSTree(BsTree &bt)
{
	bt.head=BuyNode();
	bt.cursize=0;
}

//释放结点
void Freenode(BstNode *p)
{
	free(p);
}
//递归查询
BstNode * search(BstNode *p,keyType kx)
{
	if(kx<p->data)
	{
		p=search(p->leftchild,kx);
	}
	else if(kx>p->data)
	{
		p=search(p->rightchild,kx);
	}
	return p;
}
BstNode * searchValue(BsTree &bt,keyType kx)
{
	return search(bt.head->parent, kx);
}
//非递归查询
BstNode * FindValue(BsTree &bt,keyType kx)
{
	BstNode* p=bt.head->parent;
	while(p->data!=kx&&p!=NULL)
	{
		p=kx>p->data?p->rightchild:p->leftchild;
	}
	return p;
}
//插入
bool InsertItem(BsTree &bt,keyType kx)
{
	BstNode *pa=bt.head;
	BstNode *p=bt.head->parent;
	while(p!=NULL&&p->data!=kx)
	{
		pa=p;
		p=kx<p->data?p->leftchild:p->rightchild;//找到插入的合适位置p
	}
	if(p!=NULL)
	{
		return false;
	}
	p=BuyNode(pa);//不存在则购买结点
	p->data=kx;
	if(pa==bt.head)//树中的第一个节点
	{
		bt.head->parent=p;
		bt.head->leftchild=p;
		bt.head->rightchild=p;
	}
	else
	{
		if(p->data<pa->data)
		{
			pa->leftchild=p;
			if(p->data<bt.head->data)//修改头结点左孩子的指向，即修改树中最小值
			{
				bt.head->leftchild=p;
			}
		}
		else
		{
			pa->rightchild=p;
			if(p->data>bt.head->data)
			{
				bt.head->rightchild=p;
			}
		}
	}
	bt.cursize+=1;
	return true;
}
//中序遍历
void InOrder(BstNode* p)
{
	if(p!= NULL)
	{
		InOrder(p->leftchild);
		std::cout<<p->data<<" ";
		InOrder(p->rightchild);
	}
}
void InOrder(BsTree& bt)
{
	InOrder(bt.head->parent);//从根结点开始遍历
}
//找直接前驱，即左边的第一个节点
BstNode *First(BsTree &bt,BstNode *ptr)
{
	 while(ptr!=NULL&&ptr->leftchild!=NULL)
	 {
		 ptr=ptr->leftchild;
	 }
	 return ptr;
}
//找直接后继,即右边的最后一个节点
BstNode *Next(BsTree &bt,BstNode *ptr)
{
	if(ptr == NULL||ptr==bt.head) return NULL;
	if(ptr->rightchild!=NULL)
	{
		return First(bt,ptr->rightchild);
	}
	else
	{
		BstNode* pa=ptr->parent;
		while(pa!=bt.head&&pa->leftchild!=ptr)//如树中的23，它的直接后继为53
		{
			ptr=pa;
			pa=pa->parent;
		}
		if(pa==bt.head)
		{
			pa=NULL;
		}
		return pa;
	}
}

//删除元素
//分析：有三种情况1.删除的结点为叶子结点2.删除的结点为单分支结点3.删除的结点为双分支结点
bool DeleteItem(BsTree &bt,keyType kx)
{
	BstNode *p=FindValue(bt,kx);
	BstNode *pa=p->parent;
	if(p->leftchild != NULL && p->rightchild != NULL)//删除的结点为双分支，找到该结点的直接后继结点，用直接后继结点覆盖它，删除直接后继结点，问题转化为删除叶子结点
	{
		BstNode *nt = Next(bt,p);
		p->data = nt->data;
		p = nt;
	}
	BstNode *child = p->leftchild != NULL? p->leftchild: p->rightchild;

	if(child != NULL) child->parent = pa;//如果只有一个孩子则用这个孩子结点覆盖它，然后删除它的孩子结点就可以，问题同样转化为删除叶子结点
	if( p == bt.head)//要删除结点是根结点
	{
		bt.head->parent = child;//把头结点的父亲域指向他的孩子域
	}
	else
	{
		if(pa->leftchild==p)//要删除结点是左孩子
		{
			pa->leftchild=NULL;
		}
		else//要删除结点是右孩子
		{
			pa->rightchild=NULL;
		}
	}
	
	free(p);
	p=NULL;
	return true;
}
int main()
{
	int ar[]={53,17,78,9,45,65,87,23,81,94,88};
	int n = sizeof(ar)/sizeof(ar[0]);
	int x = 0;
	BsTree myt;
	InitBSTree(myt);
	for(int i = 0;i<n;++i)
	{
		InsertItem(myt,ar[i]);
	}

	InOrder(myt);
	std::cout<<std::endl;
	while(std::cin>>x , x != -1)
	{
		DeleteItem(myt,x);
		InOrder(myt);
		std::cout<<std::endl;
	}

	return 0;
}