二叉查找树（二叉排序树、有序二叉树）算法分析及实现

二叉查找树一般采用二叉链表作为其存储结构，我们这次也采用这样的实现。二叉查找树一般有查找、插入和删除等操作，其中查找是基础，没有查找，插入和删除则无从谈起；而删除算是难点，需处理四种不同的情况，分别是：

无左右孩子，（采取直接删除，须处理其父节点指针）

只有左孩子，（采取其父节点指针指向其左孩子）

只有右孩子、（采取其父节点指针指向其右孩子）

左右孩子都存在，（采取以直接前驱或直接后继代替，实现中我们采用直接前驱代替）。

查找的过程比较简单，如果该节点不为空，若其值大于key（要查找的值），则继续查找其左孩子；若其值小于key（要查找的值），则继续查找其右孩子；如果是等于，那么就找到了！

需要特别注意的一点是，查找是不会修改数的结构的，而插入和删除都会改变树的结构，所以在查找中我们传入的参数只是指向根节点的指针，而在插入和删除中我们传入的参数是指针引用，因为插入和删除有可能会改变根节点。举个例子，如果在删除函数中我们传入的只是指向根节点的指针，我们在删除最后一个元素后会得到一颗空树，我们当然可以在删除函数中设置T=NULL（注意是大写的），但是在主函数中呢？会出现什么情况呢？出现的情况是原来指向这棵树的根节点指向了一个无效地址，以后的操作就会出错。总而言之，要注意空树的处理。

二叉查找树的时间性能是其树的高度，平均为O（logn），最坏为O（n）。

实现如下：

#include<iostream>

using namespace std;

typedef int KeyType;

typedef struct BiTree
{
	KeyType data;
	struct BiTree *lchild;
	struct BiTree *rchild;
}BiTree;

bool SearchBST( BiTree *T,KeyType key,BiTree *&f,BiTree *&p); // f为p的父节点，f==p其实是表示f与p都指向了根节点,查找成功时p指向目标节点，失败时p指向最后查找到的节点
bool InsertBST(BiTree *&T,KeyType key);						  // 
bool DeleteBST(BiTree *&T,KeyType key);						  //
void DeleteNode(BiTree *&T,BiTree *f,BiTree *p);			  //
void MidOrderTraverse(BiTree *T);							  //

bool SearchBST( BiTree *T,KeyType key,BiTree *&f,BiTree *&p) // BiTree *&p,p为指针的引用;f为p的父节点
{
	f=T;
	p=T;
	while(T!=NULL&&T->data!=key)
	{
		if(key<T->data)
		{
			f=p;
			p=T;
			T=T->lchild;
		}
		else
		{
			f=p;
			p=T;
			T=T->rchild;
		}
	}
	if(T!=NULL) //T->data==key
	{
		f=p;
		p=T;
		return true; //找到了
	}
	else
	{
		return false; //未找到
	}
}

bool InsertBST(BiTree *&T,KeyType key)
{
	BiTree *p=NULL;
	BiTree *f=NULL;
	if(!SearchBST(T,key,f,p)) //未找到
	{
		BiTree *s=new BiTree();
		s->data=key;
		s->lchild=s->rchild=NULL;
		if(T!=NULL) //由原来的p!=NULL换成了T！=NULL
		{
			if(key<p->data)
			{
				p->lchild=s;
			}
			else
			{
				p->rchild=s;
			}
		}
		else //原来的是空树
		{
			T=s;
		}
		return true;
	}
	else // 有相同数据，则不再插入
	{
		return false;
	}
}

void MidOrderTraverse(BiTree *T)
{
	if(T!=NULL)
	{
		MidOrderTraverse(T->lchild);
		cout<<T->data<<"	";
		MidOrderTraverse(T->rchild);
	}
}



bool DeleteBST(BiTree *&T,KeyType key)
{
	BiTree *p=NULL;
	BiTree *f=NULL;
	if(SearchBST(T,key,f,p)) // 找到了该节点
	{
		DeleteNode(T,f,p);
		return true;
	}
	else
	{
		return false;
	}
}


void DeleteNode(BiTree *&T,BiTree *f,BiTree *p)
{
	if(p->lchild==NULL&&p->rchild==NULL)
	{
		if(p==T) //由原来的p==f换成了p==T，p==T表示要删除的就是根节点，如果是下面的三种情况，因为有其他的节点替代也没什么
		{		 //关键出现在这里，该树就只有一个节点，删除了其为空树。
			T=NULL;

		}
		else if(f->lchild==p)
		{
			f->lchild=NULL;
		}
		else
		{
			f->rchild=NULL;
		}
		delete p;

	}
	else if(p->lchild==NULL)
	{
		BiTree *q=p->rchild;
		p->data=q->data;
		p->lchild=q->lchild;
		p->rchild=q->rchild;
		delete q;
	}
	else if(p->rchild==NULL)
	{
		BiTree *q=p->lchild;
		p->data=q->data;
		p->lchild=q->lchild;
		p->rchild=q->rchild;
		delete q;
	}
	else
	{
		BiTree *q=p;
		BiTree *s=p->lchild;
		while(s->rchild!=NULL)
		{
			q=s;
			s=s->rchild;
		}
		p->data=s->data;
		if(p==q)
		{
			p->lchild=s->lchild;
		}
		else
		{
			q->rchild=s->lchild;
		}
		delete s;
	}
}



int main()
{
	BiTree *T=NULL;
	InsertBST(T,1);

	DeleteBST(T,1);
	MidOrderTraverse(T);
	
	InsertBST(T,3);
	InsertBST(T,4);	
	InsertBST(T,2);
	InsertBST(T,8);
	InsertBST(T,5);
	InsertBST(T,6);
	InsertBST(T,7);

	DeleteBST(T,3);
	DeleteBST(T,2);
	DeleteBST(T,8);
	DeleteBST(T,7);
	DeleteBST(T,5);
	DeleteBST(T,6);
	DeleteBST(T,1);
	MidOrderTraverse(T);

}

二叉查找树（二叉排序树、有序二叉树）算法分析及实现,布布扣,bubuko.com

二叉查找树（二叉排序树、有序二叉树）算法分析及实现

原文：http://blog.csdn.net/a0agd1x50/article/details/27692461