二叉搜索樹(shù)

     二叉查找樹(shù)（Binary Search Tree），也稱(chēng)有序二叉樹(shù)（ordered binary tree）,排序二叉樹(shù)（sorted binary tree），是指一棵空樹(shù)或者具有下列性質(zhì)的二叉樹(shù)：

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

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

2、左子樹(shù)上所有節(jié)點(diǎn)的關(guān)鍵碼都小于跟節(jié)點(diǎn)的關(guān)鍵碼。

3、右子樹(shù)上所有節(jié)點(diǎn)的關(guān)鍵碼都大于跟節(jié)點(diǎn)的關(guān)鍵碼。

4、左右子樹(shù)都是二叉樹(shù)搜索樹(shù)。

#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;
}

網(wǎng)頁(yè)題目：二叉搜索樹(shù)
分享URL：http://muchs.cn/article48/gjchhp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供響應(yīng)式網(wǎng)站、網(wǎng)站設(shè)計(jì)公司、品牌網(wǎng)站制作、服務(wù)器托管、小程序開(kāi)發(fā)、標(biāo)簽優(yōu)化

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶(hù)投稿、用戶(hù)轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話(huà)：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)

商城網(wǎng)站建設(shè)