如何進行搜索二叉樹分析，相信很多沒有經(jīng)驗的人對此束手無策，為此本文總結(jié)了問題出現(xiàn)的原因和解決方法，通過這篇文章希望你能解決這個問題。

創(chuàng)新互聯(lián)公司是一家以成都網(wǎng)站建設(shè)、網(wǎng)頁設(shè)計、品牌設(shè)計、軟件運維、網(wǎng)站推廣、小程序App開發(fā)等移動開發(fā)為一體互聯(lián)網(wǎng)公司。已累計為成都地磅秤等眾行業(yè)中小客戶提供優(yōu)質(zhì)的互聯(lián)網(wǎng)建站和軟件開發(fā)服務(wù)。

一、搜索二叉樹

1、定義：它是一棵排序二叉樹，可為空樹。

2、性質(zhì)：

• 每個節(jié)點都有一個作為搜索依據(jù)的關(guān)鍵碼（key），所有節(jié)點的關(guān)鍵碼互不相同；

• 左子樹上所有節(jié)點的關(guān)鍵碼（key）都小于根節(jié)點的關(guān)鍵碼（key）；

• 右子樹上所有節(jié)點的關(guān)鍵碼（key）都大于根節(jié)點的關(guān)鍵碼（key）；

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

二、源代碼

1、定義節(jié)點

template
struct BSTreeNode
{
	BSTreeNode *_left;//左節(jié)點
	BSTreeNode *_right;//右節(jié)點
	K _key;//節(jié)點權(quán)值
	V _value;

	BSTreeNode(const K& key,const V& value)
		:_key(key)
		,_value(value)
		,_left(NULL)
		,_right(NULL)
	{}
};

2、搜索二叉樹及其相關(guān)實現(xiàn)

template
class BSTree
{
	typedef BSTreeNode Node;
public:
	BSTree()
		:_root(NULL)
	{}
	
	//非遞歸
	Node* Find(const K& key)
	{
		return _Find(_root,key);
	}
	bool Insert(const K& key,const V& value)
	{
		return _Insert(_root,key,value);
	}
	bool Remove(const K& key)
	{
		return _Remove(_root,key);
	}

	//遞歸
	bool InOrder() //中序遍歷 --> 有序序列
	{
		return _InOrder(_root);
		cout<_key > key)
		{
			cur=cur->_right;
		}
		else if(cur->_key < key)
		{
			cur=cur->_left;
		}
		else 
		{
			return cur;
		}
		return NULL;
	}	
	bool _Insert(Node *&root,const K& key,const V& value)
	{
		if(root == NULL)
		{
			root=new Node(key,value);
			return true;
		}
		Node *cur=root;
		Node *parent=NULL;
		while(cur)
		{
			if(cur->_key < key)
			{
				parent=cur;
				cur=cur->_right;
			}
			else if(cur->_key > key)
			{
				parent=cur;
				cur=cur->_left;
			}
			else
				return false;
		}
		if(parent->_key < key)
		{
			parent->_right=new Node(key,value);
			parent->_right=parent;
		}
		else
		{
			parent->_left=new Node(key,value);
			parent->_left=parent;
		}
		return true;
	}
	bool _Remove(Node*& root,const K& key )
	{
		if(root == NULL) return false;
		Node *cur=root;
		Node *parent=NULL;
		while(cur) //找節(jié)點
		{
			if(cur->_key > key)
			{
				parent=cur;
				cur=cur->_left;
			}
			else if(cur->_key < key)
			{
				parent=cur;
				cur=cur->_right;
			}
			else //找到節(jié)點
			{
				if(cur->_left == NULL)//左為空
				{
					if(parent == NULL)
						root=cur->_right;
					else if(parent->_left == cur)
						parent->_left=cur->_right;
					else
						parent->_right=cur->_right;
				}
				else if(cur->_right == NULL)//右為空
				{
					if(parent == NULL)
						root=cur->_left;
					else if(parent->_left == cur)
						parent->_left=cur->_left;
					else
						parent->_right=cur->_left;
				}
				else //左右都不為空
				{
					Node *parent=cur;
					Node *left=cur->_right;//右子樹的最左節(jié)點
					while(left->_left)
					{
						left=left->_left;
					}
					cur->_key=left->_key;//替換結(jié)點
					cur->_value=left->_value;
					if(parent->_left == left)
						parent->_left=left->_left;
					else
						parent->_right=left->_right;
					delete left;
				}
			}
			return true;
		}
		return false;
	}

	//遞歸
	bool _InOrder(Node *root)
	{
		if(root == NULL) return false;
		_InOrder(root->_left);
		cout<_left<<" ";
		_InOrder(root->_right);
		return true;
	}
	Node* _FindR(Node *root,const K& key)
	{
		if(root == NULL) return NULL;
		if(root->_key == key)
			return root;
		else if(root->_key > key)
			return _FindR(root->_left,key);
		else
			return _FindR(root->_right,key);
	}
	bool _InsertR(Node *root,const K& key,const V& value)
	{
		if(root == NULL) 
		{
			root=new Node(key,value);
			return true;
		}
		if(root->_key > key)
			return _InsertR(root->_left,key,value);
		else if(root->_key < key)
			return _InsertR(root->_right,key,value);
		else
			return false;
	}
	bool _RemoveR(Node *root,const K& key)
	{
		if(root == NULL) return false;
		if(root->_key > key)
			return _RemoveR(root->_left,key); 
		else if(root->_key < key)
			return _RemoveR(root->_right,key);
		else  //找到節(jié)點
		{
			Node *del=NULL;
			if(root->_left == NULL) 
				root=root->_right;
			else if(root->_right == NULL)
				root=root->_left;
			else 
			{
				Node *parent=NULL;
				Node *left=root;
				while(left->_left)
				{
					parent=left;
					left=left->_left;
				}
				root->_key=left->_key;
				root->_value=left->_value;
				del=left;
				if(parent->_left == left)
					parent->_left=left->_left;
				else
					parent->_right=left->_right;
				delete del;
				return true;
			}
		}
		return false;
	}
protected:
	Node *_root;
};

3、總結(jié)：

    搜索二叉樹是一棵排序二叉樹，可為空樹。它的每一個節(jié)點都遵從搜索二叉樹的性質(zhì)。

    搜索二叉樹的中序遍歷后為升序序列；其查找根據(jù)key值以及性質(zhì)進行；其插入需先根據(jù)其key值找到插入的節(jié)點，隨后添加節(jié)點，另外其key值唯一；

    其刪除節(jié)點時，需分3種情況：

   （1）僅左為空；

  （2）僅右為空；

  （3）該節(jié)點左右皆不為空。

        刪除該節(jié)點，即需 找到 右子樹的最左節(jié)點 或 左子樹的最右節(jié)點，作為替換結(jié)點。

看完上述內(nèi)容，你們掌握如何進行搜索二叉樹分析的方法了嗎？如果還想學(xué)到更多技能或想了解更多相關(guān)內(nèi)容，歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道，感謝各位的閱讀！

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機、免備案服務(wù)器”等云主機租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價比高”等特點與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場景需求。

分享題目：如何進行搜索二叉樹分析-創(chuàng)新互聯(lián)
分享URL：http://weahome.cn/article/eeopg.html