bintree.h

二叉排序树的建立

#include<iostream.h>
typedef struct TreeNode
{
	int key;
	struct TreeNode *left;
	struct TreeNode *right;
}treeNode;

class BiSortTree
{
public:
    BiSortTree(void);
	void displayTree(void);//显示这棵树的中序遍历
	treeNode* searchTree(int key);//在树中查找一个值
	void insertTree(int key);//在树中插入一个值
  	void deleteTree(int key);//在树中删除一个值
	~BiSortTree();
private:
	treeNode* buildTree(treeNode* head,int number);//建立一个树
	treeNode* search(treeNode* head ,int key);//查找
	treeNode* BiSortTree::searchParent(treeNode* head,treeNode* p);//查找出p的父亲节点的指针
	treeNode* BiSortTree::searchMinRight(treeNode* head);//找到右子树中最小的节点
	void inOrderTree(treeNode* head);//中序遍历
    void destroyTree(treeNode* head);//删除
	treeNode *Head;
};

BiSortTree::BiSortTree()//建立一个二叉排序树
{
   cout<<"请输入你要建树的所有数(以-1结束): "<<endl;
   Head=NULL;
   int number;
   cin>>number;
   while(number!=-1)
   {
	   Head=buildTree(Head,number);
       cin>>number;
   }
}
treeNode* BiSortTree::buildTree(treeNode* head,int number)
{
	treeNode *p;
	p=new treeNode;
    p->key=number;
	p->left=p->right=NULL;
	if(head==NULL)
	{
		return p;
	}
else
{
	if(p->key <head->key)
		head->left=buildTree(head->left,number);
	else
		head->right=buildTree(head->right,number);
	return head;
}
}

void BiSortTree::insertTree(int key)//插入一个数
{
	Head=buildTree(Head,key);
}
treeNode*  BiSortTree::searchTree(int key)//在一个二叉树中查找关键字
{
	return search(Head,key);
}
treeNode* BiSortTree::search(treeNode* head,int key)//搜索对比
{
	if(head==NULL)
	return NULL;
	if(head->key==key)
	return head;
	else
	{
		if(key<head->key )return search(head->left,key);
		else return search(head->right,key);
	}
}

void BiSortTree::deleteTree(int key)//删除一个给定的值
{
	treeNode *p;
	treeNode* parent;
	p=NULL;
	p=search(Head,key);
	if(p==NULL)
	{
		p=Head;
		cout<<"无法找到关键字,删除失败."<<endl;
	}
	else cout<<"删除成功."<<endl;
    if(p==Head)
	{
		parent=searchParent(Head,p);
		p=Head;
		p=parent;
	}
	else
	{
		treeNode* parent;
		parent=searchParent(Head,p);
		if(p->left==NULL&&p->right==NULL)//叶子节点
		{
			if(parent->left==p)
			{
				parent->left=NULL;
			}
			else
			{
				parent->right=NULL;
			}
		}
		else//非叶子节点
		{
			if(p->right==NULL)//该节点没有右孩子
			{
				if(parent->left==p)
				{
					parent->left=p->left ;
				}
				else
				{
					parent->right=p->left;
				}
			}
			else//该点有左右孩子
			{
				treeNode * rightMinSon,* secondParent;//secondParent为右子树中的最小节点的父亲
				rightMinSon=searchMinRight(p->right);
				secondParent=searchParent(p->right,rightMinSon);
				secondParent->left=rightMinSon->right;
				if(p->right==rightMinSon)//右子树中的最小节点的父亲为p
				{
					p->right=rightMinSon->right ;
				}
				p->key=rightMinSon->key ;
			}
		}
	}
}
treeNode* BiSortTree::searchParent(treeNode* head,treeNode* p)
{
	if(head->left==p||head->right==p||head==p||head==NULL)
		return head;
	else
	{
		if(p->key<head->key)return searchParent(head->left ,p);
		else
			return searchParent(head->right ,p);
	}
}
	
treeNode* BiSortTree::searchMinRight(treeNode* head)//找到右子树中最小的节点
{
	if(head->left ==NULL||head==NULL)
	{
		return head;
	}
	else
	{
		return searchMinRight(head->left);
	}
}
void BiSortTree::displayTree(void)//显示中序遍历二叉树
{
	cout<<"中序遍历当前树为:";
	inOrderTree(Head);
	cout<<endl;
}
void BiSortTree::inOrderTree(treeNode* Head)
{
	if(Head!=NULL)
	{
		inOrderTree(Head->left);
		cout<<Head->key<<' ';
		inOrderTree(Head->right);
	}
}
BiSortTree::~BiSortTree()//删除一棵整二叉排序树
{
	cout<<"树已经成功删除!可安全离开.谢谢!"<<endl;
	destroyTree(Head);
}
void BiSortTree::destroyTree(treeNode* head)
{
	if(head!=NULL)
	{
		destroyTree(head->left);
		destroyTree(head->right);
		delete head;
	}
}