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

創(chuàng)新互聯(lián)公司服務項目包括玉屏網(wǎng)站建設、玉屏網(wǎng)站制作、玉屏網(wǎng)頁制作以及玉屏網(wǎng)絡營銷策劃等。多年來，我們專注于互聯(lián)網(wǎng)行業(yè)，利用自身積累的技術優(yōu)勢、行業(yè)經(jīng)驗、深度合作伙伴關系等，向廣大中小型企業(yè)、政府機構等提供互聯(lián)網(wǎng)行業(yè)的解決方案，玉屏網(wǎng)站推廣取得了明顯的社會效益與經(jīng)濟效益。目前，我們服務的客戶以成都為中心已經(jīng)輻射到玉屏省份的部分城市，未來相信會繼續(xù)擴大服務區(qū)域并繼續(xù)獲得客戶的支持與信任！

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

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

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

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

#include 
using namespace std;

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


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

template
BStree::BStree(T *arr,size_t sz)
{
	_root = new TreeNode(arr[0]);
	for (int i = 1; i < sz; i++)
	{
		TreeNode *tmp = new TreeNode(arr[i]);
		InsertBStree(_root,tmp);
	}
}
template
void BStree::InsertBStree(TreeNode *root,TreeNode *Node)
{
	if(root==NULL)
		root=Node;
	else 
	{
		TreeNode *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
TreeNode* BStree::SearchBStree(TreeNode* Root,TreeNode *Node)
{
	TreeNode *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
TreeNode* BStree::MinBStree(TreeNode* Root)
{
	TreeNode* cur=Root;
	while(cur->left)
	{
		cur=cur->left;
	}
	return cur;
}

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


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


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


template 

TreeNode* BStree::prevBStree(TreeNode *Node)
{
	if (Node->left)
		return MaxLeftBStree(Node);
	TreeNode *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 
TreeNode* BStree::postBStree(TreeNode *Node)
{
	if (Node->right)
		return MinRightBStree(Node);
	TreeNode *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 
void BStree::DeleteBStree(TreeNode *Node)
{
	TreeNode *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 *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 *child = Node->left;
		if(Node == cur->left)
		{
			delete Node;
			cur->left = child;
		}
		else
		{
			delete Node;
			cur->right = child;
		}
	}
	else
	{
		TreeNode *tmp = postBStree(Node);
		Node->Data = tmp->Data;
		DeleteBStree(tmp);
	}
}

template 
void BStree::DestroyBStree(TreeNode *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 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;
}