【二叉樹】二叉搜索樹

二叉搜索樹：

創(chuàng)新互聯(lián)是一家專業(yè)提供興海企業(yè)網(wǎng)站建設(shè),專注與網(wǎng)站設(shè)計制作、做網(wǎng)站、html5、小程序制作等業(yè)務(wù)。10年已為興海眾多企業(yè)、政府機(jī)構(gòu)等服務(wù)。創(chuàng)新互聯(lián)專業(yè)的建站公司優(yōu)惠進(jìn)行中。

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

2.左子樹的所有關(guān)鍵碼都小于根節(jié)點的關(guān)鍵碼。

3.右子樹的所有關(guān)鍵碼都大于根節(jié)點的關(guān)鍵碼。

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

刪除key：左為空，右為空，左右都不空

1）左為空：cur的右樹鏈到父節(jié)點

2）右為空：cur的左樹鏈到父節(jié)點

3）左右都不空：找右樹最左節(jié)點或左樹最右節(jié)點，將找到的節(jié)點與cur交換后刪除它。

二叉搜索樹的增、刪、查（非遞歸及遞歸）程序代碼如下：

#pragma once

#include<string>
////注意：考慮邊界問題_root 、左右子樹問題（非遞歸、遞歸）、記住判空處理
template<class K,class V>
struct BSTNode
{
	BSTNode<K, V>* _left;   //左子數(shù)
	BSTNode<K, V>* _right;  //右子樹
	K _key;
	V _value;
	//構(gòu)造函數(shù)
	BSTNode(const K& key, const V& value)
		:_left(NULL)
		, _right(NULL)
		, _key(key)
		, _value(value)
	{}
};

template<class K, class V>
class BSTree
{
	typedef BSTNode<K, V> Node;
public:
	BSTree()
		:_root(NULL)
	{}

public:
	//bool Insert(const K& key, const V& value);
	//bool Remove(const K& key);
	//Node* Find(const K& key);
	//bool Insert_R(const K& key, const V& value);
	//bool Remove_R(const K& key, const V& value);
	//Node* Find_R(const K& key);

	bool Insert(const K& key, const V& value)
	{
		if(_root == NULL)
			_root = new Node(key, value);
		Node* cur = _root;
		while(cur)
		{
			if(key < cur->_key)   //key小，插入左子樹
			{
				if(cur->_left == NULL)
					cur->_left = new Node(key, value);
				else
					cur = cur->_left;
			}
			else if(key > cur->_key)   //key大，插入右子樹
			{
				if(cur->_right == NULL)
					cur->_right = new Node(key, value);
				else
					cur = cur->_right;
			}
			else                       //key關(guān)鍵碼互不相同
				return false;
		}
		return true;
	}
	////////////////刪除//////////////
	////邊界條件判斷（無節(jié)點，一個節(jié)點）
	////找key值，記錄parent。
	////刪除key，分三種情況(左為空，右為空，左右都不為空)
	////左右節(jié)點都存在，找到右樹的最左節(jié)點或者左樹的最右節(jié)點，
	////將找到的節(jié)點與cur交換后再刪除找到的節(jié)點

	bool Remove(const K& key) 
	{
		//無節(jié)點
		if(_root == NULL)
			return false;
		//一個節(jié)點 _root
		if(_root->_left == NULL&&_root->_right == NULL)
		{
			if(key == _root->_key)
			{
				delete _root;
				_root = NULL;
				return true;
			}
			else
				return false;
		}

		Node* cur = _root;
		Node* parent = NULL;
		while(cur)
		{   //找key值，記錄parent
			if(key < cur->_key)  
			{
				parent = cur;
				cur = cur->_left;
			}
			else if(key > cur->_key)
			{
				parent = cur;
				cur = cur->_right;
			}
			////刪除key，分三種情況(左為空，右為空，左右都不為空)
			else  
			{
				Node*del=cur;
				if(cur->_left == NULL)   //將cur的右子樹鏈到父節(jié)點
				{
					//注意parent可能為空
					if(parent == NULL)  
					{
						_root = cur->_right;
					}
					else
					{
						if(cur = parent->_left)
							parent->_left = cur->_right;
						else
							parent->_right = cur->_right;
					}
		
				}
				else if(cur->_right == NULL)  //將cur的左子樹鏈到父節(jié)點
				{
					if(parent == NULL)
					{
						_root = cur->_left;
					}
					else
					{
						if(cur = parent->_left)
							parent->_left = cur->_left;
						else
							parent->_right = cur->_left;
					}
					
				}
				////左右節(jié)點都存在，找到右樹的最左節(jié)點或者左樹的最右節(jié)點
				////將找到的節(jié)點與cur交換后再刪除找到的節(jié)點
				else
				{
					parent = cur;
					//右樹的最左節(jié)點firstLeft
					Node* firstLeft = cur->_right;
					while(firstLeft->_left)
					{
						parent = firstLeft;
						firstLeft = firstLeft->_left;
					}
					
					swap(firstLeft->_key, cur->_key);
					swap(firstLeft->_value, cur->_value);
					del = firstLeft;

					//因為左右節(jié)點都存在，所以parent不為空
					//firstLeft 左節(jié)點為空，右節(jié)點可能存在
					if(firstLeft == parent->_left)
						parent->_left = firstLeft->_right;
					else
						parent->_right = firstLeft->_right;

				} /*找到firstLeft代替del*/
				
				delete del;
				return true;
			}
		}//while end
		
		return false;
	}

//查找
	Node* Find(const K& key)
	{
		if(_root == NULL)
			return NULL;
		Node* cur = _root;
		while(cur)
		{
			if(key < cur->_key)   //在左子樹查找
		    {
				cur = cur->_left;

		    }
			else if(key>cur->_key)  //在右子樹查找
			{
				cur = cur->_right;
			}
			else
			{
				return cur;
			}
		}
		return NULL;
	}

	/////////////////////遞歸實現(xiàn)增刪查
	bool Insert_R(const K& key, const V& value)
	{
		return _Insert_R(_root, key, value);
	}
	bool Remove_R(const K& key)
	{
		return _Remove_R(_root, key);
	}
	Node* Find_R(const K& key)
	{
		return _Find_R(_root, key);
	}

	//中序遍歷
	void InOrder()
	{
		return _InOrder(_root);
	}

	bool Empty()
	{
		if(_root == NULL)
		{
			return true;
		}
		return false;
	}
protected:
	void _InOrder(Node* root)
	{
		if(root == NULL)
			return;
		_InOrder(root->_left);
		//cout << root->_key << " " << endl;
		cout << "key:" << root->_key << " ,value:" << root->_value<< endl;
		_InOrder(root->_right);
	}
	////注意：root參數(shù)應(yīng)為引用&  每次遞歸的root即為上一次的root->_left或者root->_right
	bool _Insert_R(Node*& root, const K& key, const V& value)
	{
		if(root == NULL)
		{
			root = new Node(key, value);
			return true;
		}

		if(key < root->_key)
		{
			return _Insert_R(root->_left, key, value);
		}
		else if(key>root->_key)
		{
			return _Insert_R(root->_right, key, value);
		}
		else
		{
			return false;
		}
	}
//查找
	Node* _Find_R(Node*& root, const K& key)
	{
		if(root == NULL)
			return NULL;

		if(key < root->_key)
		{
			return _Find_R(root->_left, key);
		}
		else if(key>root->_key)
		{
			return _Find_R(root->_right, key);

		}
		else
		{
			return root;
		}
	}
//刪除
	bool _Remove_R(Node*& root, const K& key)
	{
		if(root == NULL)
			return false;

		if(key < root->_key)
		{
			return _Remove_R(root->_left, key);
		}
		else if(key > root->_key)
		{
			return _Remove_R(root->_right, key);
		}
		///刪除key
		////以引用root作參數(shù)，root相當(dāng)于上一層的root->_left或者root->_right
		else   
		{
			Node*del = root;
			if(root->_left == NULL)
			{
				root = root->_right;
				delete del;
				return true;
			}
			else if(root->_right == NULL)
			{
				root = root->_left;
				delete del;
				return true;
			}
			///左右節(jié)點都不為空
			else
			{
				//右子樹的最左節(jié)點
				Node* firstLeft = root->_right;
				while(firstLeft->_left)
				{
					firstLeft = firstLeft->_left;
				}

				swap(firstLeft->_key, root->_key);
				swap(firstLeft->_value, root->_value);

				//_Remove_R(firstLeft, key);//錯誤，firstLeft是臨時變量不能作為遞歸的參數(shù)
				_Remove_R(root->_right, key);
			}

		}///刪除key end
		return false;
	}

protected:
	Node* _root;
};

測試代碼：

void TestBSTree()
{
	BSTree<int, int> bst;
	bst.Insert(5, 1);
	bst.Insert(3, 1);
	bst.Insert(4, 1);
	bst.Insert(1, 1);
	bst.Insert(7, 1);
	bst.Insert(8, 1);
	bst.Insert(2, 1);
	bst.Insert(6, 1);
	bst.Insert(0, 1);
	bst.Insert(9, 1);

	bst.InOrder();

	cout << "? " << bst.Find(1)->_key<< endl;
	cout << "? " << bst.Find(8)->_key<< endl;
	cout << "? " << bst.Find(22)<< endl;


	bst.Remove(1);
	bst.Remove(2);
	bst.Remove(3);
	bst.Remove(4);
	bst.Remove(5);
	bst.Remove(6);
	bst.Remove(7);
	bst.Remove(8);
	bst.Remove(9);
	bst.Remove(0);

	if(bst.Empty())
		cout << "此二叉搜索樹為空" << endl;
	bst.InOrder();
}

void TestBSTree_R()  //遞歸
{
	BSTree<int, int> bst;

	bst.Insert_R(5, 1);
	bst.Insert_R(3, 1);
	bst.Insert_R(4, 1);
	bst.Insert_R(1, 1);
	bst.Insert_R(7, 1);
	bst.Insert_R(8, 1);
	bst.Insert_R(2, 1);
	bst.Insert_R(6, 1);
	bst.Insert_R(0, 1);
	bst.Insert_R(9, 1);

	bst.InOrder();

	cout << "? " << bst.Find(1)->_key << endl;
	cout << "? " << bst.Find(8)->_key << endl;
	cout << "? " << bst.Find(22) << endl;

	/*
	bst.Remove_R(1);
	bst.Remove_R(2);
	bst.Remove_R(3);
	bst.Remove_R(4);
	*/
	bst.Remove_R(5);
	bst.Remove_R(6);
	bst.Remove_R(7);
	bst.Remove_R(8);
	bst.Remove_R(9);
	bst.Remove_R(0);

	if(bst.Empty())
		cout << "此二叉搜索樹為空" << endl;
	bst.InOrder();
}


void TestBSTree_string()  // int string
{
	BSTree<int, string> bst;
	bst.Insert(5, "zhou");
	bst.Insert(3, "sun");
	bst.Insert(4, "li");
	bst.Insert(1, "zhao");
	bst.Insert(7, "zheng");
	bst.Insert(8, "wang");
	bst.Insert(2, "qian");
	bst.Insert(6, "wu");
	bst.Insert(0, "baijiaxing");
	bst.Insert(9, "feng");

	bst.InOrder();

	cout << "? " << bst.Find(1)->_key << endl;
	cout << "? " << bst.Find(8)->_key << endl;
	cout << "? " << bst.Find(22) << endl;

	//bst.Remove(0);
	//bst.Remove(1);
	//bst.Remove(2);
	//bst.Remove(3);
	//bst.Remove(4);
	bst.Remove(5);
	bst.Remove(6);
	bst.Remove(7);
	bst.Remove(8);
	bst.Remove(9);


	if(bst.Empty())
		cout << "此二叉搜索樹為空" << endl;
	bst.InOrder();
}

文章標(biāo)題：【二叉樹】二叉搜索樹
網(wǎng)頁網(wǎng)址：http://jinyejixie.com/article8/ijciop.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供動態(tài)網(wǎng)站、網(wǎng)站設(shè)計公司、定制網(wǎng)站、網(wǎng)站排名、微信公眾號、商城網(wǎng)站

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

猜你還喜歡下面的內(nèi)容

成人午夜视频全免费观看高清-秋霞福利视频一区二区三区-国产精品久久久久电影小说-亚洲不卡区三一区三区一区

【二叉樹】二叉搜索樹