二叉搜索樹

     二叉查找樹（Binary Search Tree），也稱有序二叉樹（ordered binary tree）,排序二叉樹（sorted binary tree），是指一棵空樹或者具有下列性質的二叉樹：

1、每一個節點都有一個作為搜索依據的關鍵碼，所有節點的關鍵碼互不相同。

2、左子樹上所有節點的關鍵碼都小于跟節點的關鍵碼。

3、右子樹上所有節點的關鍵碼都大于跟節點的關鍵碼。

4、左右子樹都是二叉樹搜索樹。

#include <iostream>
using namespace std;

template <typename T>
struct TreeNode
{
	T Data;
	TreeNode<T> *left;
	TreeNode<T> *right;
	TreeNode<T> *parent;
	TreeNode(T data)
		:left(NULL)
		,right(NULL)
		,Data(data)
		,parent(NULL)
	{}
};


template <typename T>
class BStree
{
public:
	BStree()
	{}
	~BStree()
	{}
	BStree(T *arr,size_t sz);
	void Insert(T data)
	{
		TreeNode<T> *tmp = new TreeNode<T>(data);
		InsertBStree(_root,tmp);
	}
	void Search(T data)
	{
		TreeNode<T> *tmp = new TreeNode<T>(data);
		tmp = SearchBStree(_root,tmp);
		if(tmp)
			cout<<'Y'<<endl;
		else
			cout<<'N'<<endl;
	}
	void Min()
	{
		TreeNode<T>* node = MinBStree(_root);
		cout<<node->Data<<endl;
	}
	void Max()
	{
		TreeNode<T>* node = MaxBStree(_root);
		cout<<node->Data<<endl;
	}
	void MaxLeft()
	{
		TreeNode<T>* node = MaxLeftBStree(_root);
		cout<<node->Data<<endl;
	}
	void MinRight()
	{
		TreeNode<T>* node = MinRightBStree(_root);
		cout<<node->Data<<endl;
	}
	void PrevNode(T data)
	{
		TreeNode<T> *tmp = new TreeNode<T>(data);
		tmp = SearchBStree(_root,tmp);
		if (tmp)
			tmp = prevBStree(tmp);
		cout<<tmp->Data<<endl;
	}
	void PostNode(T data)
	{
		TreeNode<T> *tmp = new TreeNode<T>(data);
		tmp = SearchBStree(_root,tmp);
		if (tmp)
			tmp = postBStree(tmp);
		cout<<tmp->Data<<endl;
	}
	void DeleteNode(T data)
	{
		TreeNode<T> *tmp = new TreeNode<T>(data);
		tmp = SearchBStree(_root,tmp);
		if (tmp)
			DeleteBStree(tmp);
	}
	void Destroy()
	{
		DestroyBStree(_root);
	}
	void Mid()
	{
		MidOrder(_root);
	}
	void MidOrder(TreeNode<T> *Root)
	{
		if(Root==NULL)
			return;
		MidOrder(Root->left);
		cout<<Root->Data<<" ";
		MidOrder(Root->right);
	}
protected:
	void InsertBStree(TreeNode<T> *root,TreeNode<T> *Node);
	TreeNode<T>* SearchBStree(TreeNode<T> *Root,TreeNode<T> *Node);
	TreeNode<T>* MinBStree(TreeNode<T>* Root);
	TreeNode<T>* MaxBStree(TreeNode<T>* Root);
	TreeNode<T>* MaxLeftBStree(TreeNode<T> *Root);
	TreeNode<T>* MinRightBStree(TreeNode<T> *Root);
	TreeNode<T>* prevBStree(TreeNode<T> *Node);
	TreeNode<T>* postBStree(TreeNode<T> *Node);
	void DeleteBStree(TreeNode<T> *Node);
	void DestroyBStree(TreeNode<T> *Root);
private:
	TreeNode<T> * _root;
};

template<typename T>
BStree<T>::BStree(T *arr,size_t sz)
{
	_root = new TreeNode<T>(arr[0]);
	for (int i = 1; i < sz; i++)
	{
		TreeNode<T> *tmp = new TreeNode<T>(arr[i]);
		InsertBStree(_root,tmp);
	}
}
template<typename T>
void BStree<T>::InsertBStree(TreeNode<T> *root,TreeNode<T> *Node)
{
	if(root==NULL)
		root=Node;
	else 
	{
		TreeNode<T> *cur=NULL;
		while(root)
		{
			cur=root;
			if(root->Data > Node->Data)
			{
				root=root->left;
			}
			else
			{
				root=root->right;
			}
		}
		if(Node->Data > cur->Data)
		{
			cur->right=Node;
			Node->parent = cur;
		}
		else
		{
			cur->left=Node;
			Node->parent = cur;
		}
	}
}
template<typename T>
TreeNode<T>* BStree<T>::SearchBStree(TreeNode<T>* Root,TreeNode<T> *Node)
{
	TreeNode<T> *cur=Root;
	while(cur&&cur->Data!=Node->Data)
	{
		if(cur->Data>Node->Data)
		{
			cur=cur->left;
		}
		else 
		{
			cur=cur->right;
		}
	}
	if(cur)
		return cur;
	else 
		return NULL;
}

template<typename T>
TreeNode<T>* BStree<T>::MinBStree(TreeNode<T>* Root)
{
	TreeNode<T>* cur=Root;
	while(cur->left)
	{
		cur=cur->left;
	}
	return cur;
}

template<typename T>
TreeNode<T>* BStree<T>::MaxBStree(TreeNode<T>* Root)
{
	TreeNode<T>* cur=Root;
	while(cur->right)
	{
		cur=cur->right;
	}
	return cur;
}


template<typename T>
TreeNode<T>* BStree<T>::MaxLeftBStree(TreeNode<T> *Root)
{
	if (Root->left == NULL)
		return NULL;
	TreeNode<T>* cur = Root->left;
	while(cur->right)
	{
		cur = cur->right;
	}
	return cur;
}


template<typename T>
TreeNode<T>* BStree<T>::MinRightBStree(TreeNode<T> *Root)
{
	if (Root->right == NULL)
		return NULL;
	TreeNode<T>* cur = Root->right;
	while(cur->left)
	{
		cur = cur->left;
	}
	return cur;
}


template <typename T>

TreeNode<T>* BStree<T>::prevBStree(TreeNode<T> *Node)
{
	if (Node->left)
		return MaxLeftBStree(Node);
	TreeNode<T> *P = Node->parent;
	if (Node->left == NULL && Node == P->right)
	{
		return Node->parent;
	}
	while (P && Node == P->left)
	{
		Node = P;
		P = P->parent;
	}
	return P;
}


template <typename T>
TreeNode<T>* BStree<T>::postBStree(TreeNode<T> *Node)
{
	if (Node->right)
		return MinRightBStree(Node);
	TreeNode<T> *P = Node->parent;
	if (Node->right == NULL && Node == P->left)
	{
		return Node->parent;
	}
	while (P && Node == P->right)
	{
		Node = P;
		P = P->parent;
	}
	return P;
}


template <typename T>
void BStree<T>::DeleteBStree(TreeNode<T> *Node)
{
	TreeNode<T> *cur = Node->parent;
	if (Node->left == NULL && Node->right == NULL)
	{
		if(Node == cur->left)
		{
			delete Node;
			cur->left = NULL;
		}
		else
		{
			delete Node;
			cur->right = NULL;
		}
	}
	else if(Node->left == NULL && Node->right)
	{
		TreeNode<T> *child = Node->right;
		if(Node == cur->left)
		{
			delete Node;
			cur->left = child;
		}
		else
		{
			delete Node;
			cur->right = child;
		}
	}
	else if(Node->right == NULL && Node->left)
	{
		TreeNode<T> *child = Node->left;
		if(Node == cur->left)
		{
			delete Node;
			cur->left = child;
		}
		else
		{
			delete Node;
			cur->right = child;
		}
	}
	else
	{
		TreeNode<T> *tmp = postBStree(Node);
		Node->Data = tmp->Data;
		DeleteBStree(tmp);
	}
}

template <typename T>
void BStree<T>::DestroyBStree(TreeNode<T> *Root)
{
	if(Root==NULL)
		return;
	if(Root->left)
		DestroyBStree(Root->left);
	if(Root->right)
		DestroyBStree(Root->right);
	delete Root;
	Root = NULL;
}


void Test()
{
	int arr[] = {5,3,4,1,7,8,2,6,0,9};
	int sz = sizeof(arr)/sizeof(arr[0]);
	BStree<int> BS(arr,sz);
	/*BS.Mid();
	BS.Insert(10);
	BS.Mid();*/
	/*BS.Max();
	BS.Min();
	BS.MaxLeft();
	BS.MinRight();
	BS.Search(6);*/
	//BS.PrevNode(9);
	//BS.PostNode(4);
	BS.DeleteNode(5);
	BS.Mid();
	//BS.Destroy();
	//BS.Mid();
}

int main()
{
	Test();
	return 0;
}