二叉查找树之C++实现

---

---

个人笔记，如有描述不当，欢迎留言指出~

#include <iostream>
#include <string>
#include <sstream>
using namespace std;

template<class T>
struct BSTreeNode{
	T key;
	BSTreeNode *left;
	BSTreeNode *right;
	BSTreeNode *parent;
	BSTreeNode(T k ){
		key=k;
		left=NULL;
		right=NULL;
		parent=NULL;
	}
	BSTreeNode(){};
};
//错误信息
 struct ErrorMessage{
	bool flag;
	string message;
 };

 //生成节点并插入树中
template<class T>
ErrorMessage insert(BSTreeNode<T>* &root,T key){
	BSTreeNode<T>* node=NULL;
	ErrorMessage error;
	stringstream  s;
	if ((node=new BSTreeNode<T>(key)) == NULL)
	{
		s<<"值"<<key<<"分配节点内存失败";
		error.flag=false;
		error.message= s.str();
		return error;
	}
	BSTreeNode<T>* x= root;
	BSTreeNode<T>* y= NULL;
	while (x !=NULL)
	{
		y=x;
		if (node->key<x->key)
		{
			x=x->left;
		}
		else if(node->key>x->key){
			x=x->right;
		}
		else{
			s<<"值"<<key<<"重复,创建节点失败";
			error.flag=false;
			error.message=s.str();
			return error;
		}
	}
	node->parent=y;
	if (y==NULL)
	{
		root = node;
	}
	else if(node->key<y->key){
		y->left=node;
	}
	else{
		y->right=node;
	}
	s<<"值"<<key<<"创建节点成功";
	error.flag=true;
	error.message=s.str();
	return error;
}
//前序遍历
template<class T >
void preShow(BSTreeNode<T>* node){
	if (node != NULL)
	{
		cout<<node->key<<" ";
		preShow(node->left);
		preShow(node->right);
	}
}
//中序遍历
template<class T>
void midShow(BSTreeNode<T>* node){
	if (node !=NULL)
	{
		midShow(node->left);
		cout<<node->key<<" ";
		midShow(node->right);
	}
}

//后序遍历
template<class T >
void postShow(BSTreeNode<T>* node){
	if (node != NULL)
	{
		cout<<node->key<<" ";
		postShow(node->left);
		postShow(node->right);
	}
}

// 查找节点树下包含key的节点
template<class T >
BSTreeNode<T>* search(BSTreeNode<T>* node,T key){
	if (node == NULL || node->key == key)
	{
		return node;
	} 
	else
	{
		if (node->key>key)
		{
			search(node->left,key);
		}
		else if (node->key<key)
		{
			search(node->right,key);
		}
	}
}
// 返回节点树中最大值的节点
template<class T >
BSTreeNode<T>* maxNode(BSTreeNode<T>* node){
	if (node==NULL)
	{
		return NULL;
	}
	if (node->right==NULL)
	{
		return node;
	} 
	else
	{
		maxNode(node->right);
	}
}

// 返回节点树中最小值的节点
template<class T >
BSTreeNode<T>* minNode(BSTreeNode<T>* node){
	if (node==NULL)
	{
		return NULL;
	}
	if (node->left==NULL)
	{
		return node;
	} 
	else
	{
		minNode(node->left);
	}
}
//返回传入节点的后继节点
template<class T>
BSTreeNode<T>* successor(BSTreeNode<T>* node){
	if(node == NULL){
		return NULL;
	}
	if (node->right!=NULL)
	{
		return minNode(node->right);
	}
	BSTreeNode<T>* parent=node->parent;
	BSTreeNode<T>* child=node;
	while(parent!=NULL&&parent->left!=child){
		child=parent;
		parent=parent->parent;
	}
	return parent;
}

// 返回传入节点的前驱节点
template<class T>
BSTreeNode<T>* predecessor(BSTreeNode<T>* node){
	if (node == NULL)
	{
		return NULL;
	}
	if (node->left!=NULL)
	{
		return maxNode(node->left);
	}
	BSTreeNode<T>* parent=node->parent;
	BSTreeNode<T>* child=node;
	while(parent!=NULL&&parent->right!=child){
		child=parent;
		parent=parent->parent;
	}
	return parent;
}
//删除节点
template<class T>
void delete_node(BSTreeNode<T>* &root, BSTreeNode<T>* node){
	if (node->left==NULL&&node->right==NULL) //叶子节点
	{
		if (node == root)
		{
			root=NULL;
		} 
		else if (isLeft(node))
		{
			node->parent->left=NULL;
		}
		else{
			node->parent->right=NULL;
		}
	} 
	else if (node->left==NULL) //只有右子节点
	{
		if (node == root) //节点是根节点
		{
			root=node->right;
			node->right->parent=NULL;
		} 
		else if (isLeft(node)) //节点是左节点
		{
			node->parent->left=node->right;
			node->right->parent=node->parent;
		}
		else{ //节点是右节点
			node->parent->right=node->right;
			node->right->parent=node->parent;
		}
	}
	else if (node->right==NULL) //只有左节点
	{
		if (node == root) //节点是根节点
		{
			root=node->left;
			node->left->parent=NULL;
		} 
		else if (isLeft(node)) //节点是左节点
		{
			node->parent->left=node->left;
			node->left->parent=node->parent;
		}
		else{ //节点是右节点
			node->parent->right=node->left;
			node->left->parent=node->parent;
		}
	} 
	else //左右节点都有
	{
		BSTreeNode<T>* suc= successor(node); //node 的后继节点
		if (suc == node->right) //后继节点为右子节点
		{
			if (node == root)// 删除节点为根节点
			{
				root=suc;
				suc->left=node->left;
				node->left->parent=suc;
			}
			else{// 删除节点不为根节点
				if (isLeft(node)) //删除节点为左节点
				{ 
					node->parent->left= suc;
				}
				else{ // 删除节点为右节点
					node->parent->right=suc;
				}
				suc->parent=node->parent;
				suc->left=node->left;
				node->left->parent=suc;
			}
		}
		else //后继节点不为右子节点
		{ 
			suc->parent->left=suc->right;
			if (suc->right!=NULL) // 后继节点的右节点不空
			{
				suc->right->parent= suc->parent;
			}
			suc->left =node->left;
			node->left->parent =suc;
			suc->right=node->right;
			node->right->parent =suc;
			suc->parent=node->parent;
			if (node==root)
			{
				root=suc;
			}
		}	
	}
	delete node;
	node=NULL;
}
template<class T>
bool deleteByKey(BSTreeNode<T>* &root, T key){
	BSTreeNode<T>* node= search(root,key);
	if (node == NULL)
	{
		return false;
	}
	else{
		delete_node(root,node);
		return true;
	}
}
// 判断是否为左节点
template<class T>
bool isLeft(BSTreeNode<T>* node){
	if (node->parent!=NULL&&node->parent->left==node)
	{
		return true;
	}
	return false;
}
int main(){
 
	BSTreeNode<int>* root=NULL;
	cout<<insert(root,5).message<<endl;
	cout<<insert(root,3).message<<endl;
	cout<<insert(root,1).message<<endl;
	cout<<insert(root,2).message<<endl;
	cout<<"前序"<<endl;
	preShow(root);
	cout<<endl<<"中序"<<endl;
	midShow(root);
	cout<<endl<<"后序"<<endl;
	postShow(root);
	cout<<endl;
	if (search(root,4) != NULL)
	{
		cout<<"存在"<<4<<endl;
	}else{
		cout<<"不存在"<<4<<endl;
	}
	cout<<"最大值:"<<maxNode(root)->key<<endl;
	cout<<"最小值:"<<minNode(root)->key<<endl;
	cout<<"3的后继:"<<successor(search(root,3))->key<<endl;
	cout<<"3的前驱:"<<predecessor(search(root,3))->key<<endl;
	if (	deleteByKey(root,5))
	{
		cout<<"5删除成功"<<endl;
	} 
	else
	{
		cout<<"5删除成功"<<endl;
	}
	cout<<"中序"<<endl;
	midShow(root);

	return 0;
}