学步园

下面是树的实现，它的数据域只需要一个根节点

完成的主要工作是插入，删除和查找

BSTree.h 文件

//此类是二叉搜索树类的定义部分
#include "BinaryTreeNode.h"
class BSTree
{
private:
//根节点
BinaryTreeNode *root;

public:
BSTree();
public:
BinaryTreeNode *get(ObjectClass *theKey);//搜索
BinaryTreeNode *getRoot();//返回根节点

BinaryTreeNode *remove(ObjectClass *theKey);//删除
void insert(ObjectClass *theKey, ObjectClass *theValue);//插入
void ascend(BinaryTreeNode *);//遍历
int calWidth(BinaryTreeNode *);//计算各节点的长度
void outPut();//输出
BinaryTreeNode *tree_minimum(BinaryTreeNode *p);//最小节点
BinaryTreeNode *tree_maximum(BinaryTreeNode *p);//最大节点
BinaryTreeNode *tree_successor(BinaryTreeNode *p);//后继节点
};

BSTree.cpp 文件

//此文件是二叉搜索树的实现部分
#include "BSTree.h"
#include <iostream>
#include "queue.h"
using namespace std;
BSTree::BSTree()
{
	root = NULL;//根节点默认为NULL
}
//查找关键字为theKey的节点并返回指向节点的指针,找不到则返回空指针
BinaryTreeNode *BSTree::get(ObjectClass *theKey)
{
	BinaryTreeNode *p=root;
	while(p!=NULL)
	{
		//if(theKey < p->getKey())
		if(theKey->Compare(p->getKey()) == -1)
		p=p->getLeft();
		//if(theKey > p->getKey())
		else if(theKey->Compare(p->getKey()) == 1)
		p=p->getRight();
		else //如果找到了相同的关键字则成功返回
		return p;
	}
	return NULL;
}
//插入一个节点，如果节点关键字已经存在则覆盖，否则插入到叶子节点处
void BSTree::insert(ObjectClass *theKey,ObjectClass *theValue)
{
	BinaryTreeNode *p=root; //search pointer
	BinaryTreeNode *parent=NULL;//parent of p;
	while(p!=NULL)
	{
		parent=p;
		//if(theKey < p->getKey())
		if(theKey->Compare(p->getKey()) == -1)
		   p=p->getLeft();
		//if(theKey > p->getKey())
		else if(theKey->Compare(p->getKey()) == 1)
		   p=p->getRight();
		else
		{
		   p->setValue(theValue);
		   //如果找到相同的关键字则覆盖原有的
		   return;
		}
	}
	//等待插入的新节点
	BinaryTreeNode *newNode = new BinaryTreeNode(theKey,theValue);
	if(root == NULL)
	   root = newNode;
	else
	{
		//当p为空的时候parent最多只有一个儿子节点
	    //if(theKey < parent->getKey())
	    if(theKey->Compare(parent->getKey()) == -1)
	    {
	       parent->setLeft(newNode);
	       newNode->setParent(parent);
	    }
	    else
	    {
	       parent->setRight(newNode);
	       newNode->setParent(parent);
	    }
	}
	return;
}
//删除节点，如果这个节点含有少于两个儿子节点，则直接删除它，然后将它的儿子节点链接到它原来所在的位置
//如果这个节点含有两个儿子节点，则要先删除它的后继节点，然后将它的后继节点的值换给它
BinaryTreeNode *BSTree::remove(ObjectClass *theKey)
{
	//先查找到要删除的节点指针
	BinaryTreeNode *deletedNode=get(theKey);
	if(deletedNode==NULL) return NULL;
	//即将被删除的节点,注意这个节点最多只含有一个儿子节点
	BinaryTreeNode *todelete;
	//被删除节点的儿子节点
	BinaryTreeNode *nextNode;
	if(deletedNode->getLeft()==NULL || deletedNode->getRight()==NULL)
		//当要删除的节点只含有最多一个儿子节点时则即将被删除节点就是要删除的节点
		todelete = deletedNode;
	else
		todelete = tree_successor(deletedNode);//否则的话删除它的后继节点
	//获取唯一的儿子节点，准备当前即将删除节点的删除工作
	if(todelete->getLeft()!=NULL)
		nextNode=todelete->getLeft();
	else
		nextNode=todelete->getRight();
	//开始删除节点
	if(nextNode!=NULL)
		nextNode->setParent(todelete->getParent());
	if(todelete->getParent()==NULL)
		nextNode=root;
	else if(todelete->getParent()->getLeft()==todelete)
		todelete->getParent()->setLeft(nextNode);
	else
		todelete->getParent()->setRight(nextNode);
	//节点成功删除，删完后在考虑将原来节点的后续节点值的替换
	if(todelete!=deletedNode)
	{
		deletedNode->setKey(todelete->getKey());
		deletedNode->setValue(todelete->getValue());
	}
	//返回被删除的节点
	return todelete;
}

//计算左右的宽度，使用递归算法
int BSTree::calWidth(BinaryTreeNode *p)
{
	if(p!=NULL)
	{
		int leftWidth=0;//左宽度
		int rightWidth=0;//右宽度
		if(p->getLeft()!=NULL)
			leftWidth=calWidth(p->getLeft())+p->getKey()->getLength();
			//左宽度是左子树的总宽度加上本节点的长度
		if(p->getRight()!=NULL)
			rightWidth=calWidth(p->getRight())+p->getKey()->getLength();
			//右宽度是右子树的总宽度加上本节点的长度
		p->setWidth(leftWidth,rightWidth);//设置左右宽度
		//返回本节点为根的子树总宽度
		return leftWidth+rightWidth;
	}
}

//按照层次遍历子树并且打印出来
void BSTree::ascend(BinaryTreeNode *p)
{	
	
	calWidth(p);//计算左右子树的宽度

	p->setLeftOutPutLen(p->getLeftWidth());//设置最顶层的左边预留宽度

	//下面要用队列实现树的层次遍历
	Queue<BinaryTreeNode *> Q;
	Q.EnQueue(p);
	int number=0;//存储下一层的元素个数
	int numberLeave=1;//这一层还剩下多少元素
	BinaryTreeNode *dep;//保存当前从队列弹出的节点指针

	int preLeftWidth=0;
	//存储前一个节点的左宽度，以便后面一个节点的打印
	//如果当前节点在最开始，则前一节点左宽度为0

	bool firstIn=true;

	while(!Q.isEmpty())//打印所有节点
	{
		dep=Q.DeQueue();
		numberLeave--;
		if(dep!=NULL)
		{
			if(dep->getLeft()!=NULL)
			{
				Q.EnQueue(dep->getLeft());//左节点加入队列
				number++;//下层节点加一
			}
			
			if(dep->getRight()!=NULL)
			{
				Q.EnQueue(dep->getRight());//右节点加入队列
				number++;//下层节点加一
			}

			int leftOutPutLen=dep->getLeftWidth();
			//如果是第一次进入就左边预留宽度就是当前节点自己的宽度
			
			if(!firstIn)
			{
				if(dep==dep->getParent()->getLeft())
					leftOutPutLen = dep->getParent()->getLeftOutPutLen()-dep->getRightWidth()-dep->getParent()->getKey()->getLength();
				//如果当前节点是左儿子，则它的左预留宽度是父节点的预留宽度减去当前节点右宽度
				else
					leftOutPutLen = dep->getParent()->getLeftOutPutLen()+dep->getLeftWidth()+dep->getParent()->getKey()->getLength();
				//如果当前节点是右儿子，则它的左预留宽度是父节点的预留宽度加上当前节点的左宽度
				dep->setLeftOutPutLen(leftOutPutLen);//设置预留宽度
			}

			//根据当前节点左预留宽度和上一兄弟节点的结束宽度打印预留空格
			for(int i=0;i<leftOutPutLen-preLeftWidth;i++)
				cout<<" ";
			dep->getKey()->OutPut();//打印当前节点
			preLeftWidth=leftOutPutLen+dep->getKey()->getLength();
			//计算当前节点的结束宽度，以便下一兄弟节点的打印

			//如果当前节点在没有兄弟节点了就换行
			if(numberLeave == 0)
			{
				cout<<endl;
				preLeftWidth=0;
				numberLeave = number;
				number = 0;
			}
		}
		firstIn=false;
	}
}

//输出，这里是默认从根节点输出，如果直接调用ascend则可以输出任何子树
void BSTree::outPut()
{
	BinaryTreeNode *temp=root;
	ascend(temp);
}

BinaryTreeNode *BSTree::tree_minimum(BinaryTreeNode *p)
{
	if(p==NULL)
	return NULL;
	BinaryTreeNode *pp=p;
	while(pp->getLeft()!=NULL)
	   pp=pp->getLeft();
	return pp;
}

BinaryTreeNode *BSTree::tree_maximum(BinaryTreeNode *p)
{
	if(p==NULL)
	return NULL;
	BinaryTreeNode *pp=p;
	while(pp->getRight()!=NULL)
	   pp=pp->getRight();
	return pp;
}

//返回已知节点的后续节点
//如果这个节点有右子数，则返回右子树的最小节点
//否则向父节点寻找，找到第一个向右转的父节点为止
BinaryTreeNode *BSTree::tree_successor(BinaryTreeNode *p)
{
	if(p==NULL) return NULL;
	   BinaryTreeNode *pp=p;
	if(pp->getRight()!=NULL)
	   return tree_minimum(pp->getRight());
	BinaryTreeNode *y=p->getParent();
	while(y!=NULL && pp==y->getRight())
	{
	   pp=y;
	   y=y->getParent();
	}
	return y;
}

BinaryTreeNode *BSTree::getRoot()
{
	return root;
}