目錄

成都創新互聯專注于馬尾網站建設服務及定制，我們擁有豐富的企業做網站經驗。 熱誠為您提供馬尾營銷型網站建設，馬尾網站制作、馬尾網頁設計、馬尾網站官網定制、小程序制作服務，打造馬尾網絡公司原創品牌,更為您提供馬尾網站排名全網營銷落地服務。

二叉搜索樹

二叉搜索樹實現?

非遞歸插入|非遞歸查找

刪除?

推導階段?

非遞歸刪除代碼?

遞歸查找?

遞歸插入

遞歸刪除?

析構函數?

拷貝構造?

賦值重載

完整代碼?

二叉搜索樹的應用

Key/Value模型?

---

二叉搜索樹

二叉搜索樹又稱二叉排序樹，它或者是一棵空樹，或者是具有以下性質的二叉樹:
? 若它的左子樹不為空，則左子樹上所有節點的值都小于根節點的值
? 若它的右子樹不為空，則右子樹上所有節點的值都大于根節點的值
? 它的左右子樹也分別為二叉搜索樹

二叉搜索樹實現? 非遞歸插入|非遞歸查找

#includeusing namespace std;
templateclass BStreeNode
{
public:
	BStreeNode(const K& key)
		:_left(nullptr),
		_right(nullptr),
		_key(key)
	{}
	BStreeNode* _left;
	BStreeNode* _right;
	K _key;
};
templateclass BStree
{
	typedef BStreeNodeNode;
public:
	bool Insert(const K& key)
	{
		if (_root == nullptr)
		{
			_root = new Node(key);
			return true;
		}

		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_key< key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_key >key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}

		cur = new Node(key);
		if (parent->_key< key)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}

		return true;
	}
bool Find(const K& key)//查找
	{
		Node* cur = _root;
		while (cur)
		{
			if (cur->_key< key)
			{
				cur = cur->_right;
			}
			else if (cur->_key >key)
			{
				cur = cur->_left;
			}
			else
			{
				return true;
			}
		}

		return true;
	}
	void InOrder()
	{
		_InOrder(_root);
	}
private:
	void _InOrder(Node *root)
	{
		if (root == nullptr)
			return;
		_InOrder(root->_left);
		cout<< root->_key<< " ";
		_InOrder(root->_right);
	}
private:
	Node* _root = nullptr;
};
int main()
{
	BStreet;
	int a[] = { 1,1,2,2,3,6,165,132,4185,123 };
	for (auto e : a)
	{
		t.Insert(e);
	}
	t.InOrder();
	return 0;
}

可去重?

刪除? 推導階段?

1.若要刪除的節點是葉子節點，直接刪除即可

2.刪除節點只有一個孩子

若左為空，則讓父親節點指向該節點的右子樹以刪除3為例

若果要刪除跟節點，而且左為空，若要刪除8，我們更新根節點即可，讓根節點指向10

若右為空，則讓父親指向左子樹，以刪除14為例

若果要刪除跟節點，而且右為空，若要刪除8，讓根節點指向3即可

3.要刪除的節點其左右節點都不為空

我們可以采用替換法刪除節點

用左子樹的大節1點或右子樹的最小節點4，若采用右樹的最小節點，交換3和4刪除4之后，刪除3，但還有一個子節點5，我們讓5成為6的左節點

若要刪除8，這里采用右樹最左節點的替換法，右樹的最左節點就是10自己，如果這樣寫會有錯誤，while循環都不會進去，minparent就是空，而后面minParent->_left = min->_right;這個語句會出錯，修正方法，讓minparent一開始就是cur，并且加個判斷。

這樣寫即可

非遞歸刪除代碼?

bool Erase(const K& key)//刪除
	{
		//若有一個子節點，刪除父節點后，讓子節點填充
		//若有倆個子節點，父節點刪除后
		//1.用左子樹的大節點替換父節點
		//2.或右子樹的最小節點替換父節點
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_key >key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (cur->_key< key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else//找到了
			{
				if (cur->_left == nullptr)//如果要刪除的節點左為空
				{
					if (cur == _root)//如果要刪除的是根節點(這種情況根節點只有右子樹，因為左為空)
					{
						_root = cur->_right;
					}
					else
					{
						if (cur == parent->_left)//判斷要刪除的節點是父親的左節點還是右節點
						{
							parent->_left = cur->_right;
						}
						else
						{
							parent->_right = cur->_right;
						}
					}
					delete cur;
					cur = nullptr;
				}
				else if (cur->_right == nullptr)//如果要刪除的節點右為空
				{
					if (cur == _root)
					{
						_root = cur->_left;
					}
					else
					{
						if (cur == parent->_left)//判斷要刪除的節點是父親的左節點還是右節點
						{
							parent->_left = cur->_left;
						}
						else
						{
							parent->_right = cur->_left;
						}
					}
					delete cur;
					cur = nullptr;
				}
				else//左右都為空，葉子節點,這里采用用右樹的最小節點進行刪除
				{
					Node* minParent = cur;
					Node*min = cur->_right;//cur是要刪除的節點
					while (min->_left)//尋找最小節點
					{
						minParent = min;
						min = min->_left;
					}
					swap(cur->_key, min->_key);
					if (minParent->_left == min)
					{
						minParent->_left = min->_right;
					}
					else
					minParent->_right = min->_right;
					delete min;
				}
				return true;
			}
		}
		return false;
	}

遞歸查找?

bool _FindR(Node *root,const K& key)
	{
		if (root == nullptr)
			return false;
		if (root->_key< key)
		{
			return _FindR(root->right, key);
		}
		else if (root->_key >key)
		{
			return _FindR(root->left, key);
		}
		else
		{
			return true;
		}
	}

遞歸插入

這種插入寫法會導致二叉樹斷開

這里的Node沒有跟父節點連接上，而是創建了一個空間單獨在那里

加上引用即可

bool _InsertR(Node*& root, const K& key)
	{
		if (root == nullptr)//根為空，直接插入
		{
			root = new Node(key);
			return true;
		}
		if (root->_key< key)
		{
			return _InsertR(root->_right, key);
		}
		else if (root->_key >key)
		{
			return _InsertR(root->_left, key);
		}
		else
		{
			return false;
		}
	}

遞歸刪除?

bool _Eraser(Node*& root, const K& key)
	{
		if (root == nullptr)
			return false;
		if (root->_key< key)
		{
			return _Eraser(root->_right, key);
		}
		else if (root->_key >key)
		{
			return _Eraser(root->_left, key);
		}
		else
		{
			Node* del = root;
			if (root->_left == nullptr)
			{
				root = root->_right;
			}
			else if (root->_right == nullptr)
			{
				root = root->_left;//由于是引用，可直接這樣將二叉樹連接起來
			}
			else
			{
				//找右樹的最左節點
				Node* min = root->_right;
				while (min->_left)
				{
					min = min->_left;
				}
				swap(root->_key, min->_key);
				return _Eraser(root->_right, key);
			}
			delete del;
			return true;
		}
	}

析構函數?

~BStree()
	{
Destory(_root);
	}
private:
	void Destory(Node*& root)//采用引用可讓root置空起作用
	{
		if (root ==nullptr)
			return;
		Destory(root->_left);
		Destory(root->right);
		delete root;
		root=nullptr
	}

拷貝構造?

注：拷貝構造也是構造，如果寫了構造，編譯器不會生成默認構造，會報錯沒有合適的默認構造

BStree(const BStree& t)
	{
		_root = _Copy(t._root);
	}
Node* _Copy(Node* root)
	{
		if (root == nullptr)
		{
			return nullptr;
		}
		Node* copyRoot = new Node(root->_key);
		copyRoot->_left = _Copy(root->_left);
		copyRoot->_right = _Copy(root->_right);
		return copyRoot;
	}

我們需加默認構造?

默認構造也可寫為BSTree()=default;

這是強制編譯器生成默認構造，是C++11的用法

賦值重載

BStree& operator=(BStreet)
	{
		swap(_root, t._root);
		return *this;
	}

搜索二叉樹增刪查的時間復雜度是：O（h），h代表高度?

完整代碼?

#includeusing namespace std;
templateclass BStreeNode
{
public:
	BStreeNode(const K& key)
		:_left(nullptr),
		_right(nullptr),
		_key(key)
	{}
	BStreeNode* _left;
	BStreeNode* _right;
	K _key;
};
templateclass BStree
{
	typedef BStreeNodeNode;
public:
	bool Insert(const K& key)
	{
		if (_root == nullptr)
		{
			_root = new Node(key);
			return true;
		}

		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_key< key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_key >key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}

		cur = new Node(key);
		if (parent->_key< key)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}

		return true;
	}
	void InOrder()//排序
	{
		_InOrder(_root);
	}
	bool Find(const K& key)//查找
	{
		Node* cur = _root;
		while (cur)
		{
			if (cur->_key< key)
			{
				cur = cur->_right;
			}
			else if (cur->_key >key)
			{
				cur = cur->_left;
			}
			else
			{
				return true;
			}
		}

		return true;
	}
	bool Erase(const K& key)//刪除
	{
		//若有一個子節點，刪除父節點后，讓子節點填充
		//若有倆個子節點，父節點刪除后
		//1.用左子樹的大節點替換父節點
		//2.或右子樹的最小節點替換父節點
		Node* parent = nullptr;
		Node* cur = _root;

		while (cur)
		{
			if (cur->_key >key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (cur->_key< key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else//找到了
			{
				if (cur->_left == nullptr)//如果要刪除的節點左為空
				{
					if (cur == _root)//如果要刪除的是根節點(這種情況根節點只有右子樹，因為左為空)
					{
						_root = cur->_right;
					}
					else
					{
						if (cur == parent->_left)//判斷要刪除的節點是父親的左節點還是右節點
						{
							parent->_left = cur->_right;
						}
						else
						{
							parent->_right = cur->_right;
						}
					}
					delete cur;
					cur = nullptr;
				}
				else if (cur->_right == nullptr)//如果要刪除的節點右為空
				{
					if (cur == _root)
					{
						_root = cur->_left;
					}
					else
					{
						if (cur == parent->_left)//判斷要刪除的節點是父親的左節點還是右節點
						{
							parent->_left = cur->_left;
						}
						else
						{
							parent->_right = cur->_left;
						}
					}
					delete cur;
					cur = nullptr;
				}
				else//左右都為空，葉子節點,這里采用用右樹的最小節點進行刪除
				{
					Node* minParent = cur;
					Node* min = cur->_right;//cur是要刪除的節點
					while (min->_left)//尋找最小節點
					{
						minParent = min;
						min = min->_left;
					}
					swap(cur->_key, min->_key);
					if (minParent->_left == min)
					{
						minParent->_left = min->_right;
					}
					else
						minParent->_right = min->_right;
					delete min;
				}
				return true;
			}
		}
		return false;
	}
	bool FindR(const K& key)
	{
		return _FindR(_root, key);
	}
	bool InsertR(const K& key)
	{
		return _InsertR(_root, key);
	}
	bool EraseR(const K& key)
	{
		return _Eraser(_root, key);
	}
	~BStree()
	{
		Destory(_root);
	}
	BStree()
	{}
	BStree(const BStree& t)
	{
		_root = _Copy(t._root);
	}
	BStree& operator=(BStreet)
	{
		swap(_root, t._root);
		return *this;
	}
private:
	Node* _Copy(Node* root)
	{
		if (root == nullptr)
		{
			return nullptr;
		}
		Node* copyRoot = new Node(root->_key);
		copyRoot->_left = _Copy(root->_left);
		copyRoot->_right = _Copy(root->_right);
		return copyRoot;
	}
	void Destory(Node*& root)//采用引用可讓root置空起作用
	{
		if (root == nullptr)
			return;
		Destory(root->_left);
		Destory(root->_right);
		delete root;
		root = nullptr;
	}
	bool _Eraser(Node*& root, const K& key)
	{
		if (root == nullptr)
			return false;
		if (root->_key< key)
		{
			return _Eraser(root->_right, key);
		}
		else if (root->_key >key)
		{
			return _Eraser(root->_left, key);
		}
		else
		{
			Node* del = root;
			if (root->_left == nullptr)
			{
				root = root->_right;
			}
			else if (root->_right == nullptr)
			{
				root = root->_left;//由于是引用，可直接這樣將二叉樹連接起來
			}
			else
			{
				//找右樹的最左節點
				Node* min = root->_right;
				while (min->_left)
				{
					min = min->_left;
				}
				swap(root->_key, min->_key);
				return _Eraser(root->_right, key);
			}
			delete del;
			return true;
		}
	}
	bool _InsertR(Node*& root, const K& key)
	{
		if (root == nullptr)//根為空，直接插入
		{
			root = new Node(key);
			return true;
		}
		if (root->_key< key)
		{
			return _InsertR(root->_right, key);
		}
		else if (root->_key >key)
		{
			return _InsertR(root->_left, key);
		}
		else
		{
			return false;
		}
	}
	bool _FindR(Node *root,const K& key)
	{
		if (root == nullptr)
			return false;
		if (root->_key< key)
		{
			return _FindR(root->right, key);
		}
		else if (root->_key >key)
		{
			return _FindR(root->left, key);
		}
		else
		{
			return true;
		}
	}
	void _InOrder(Node *root)
	{
		if (root == nullptr)
			return;
		_InOrder(root->_left);
		cout<< root->_key<< " ";
		_InOrder(root->_right);
	}
private:
	Node* _root = nullptr;
};
int main()
{
	BStreet;
	int a[] = { 1,1,2,2,3,6,165,132,4185,123 };
	for (auto e : a)
	{
		t.Insert(e);
	}
	BStreecopy = t;
	copy.InOrder();
	t.InOrder();
	BStreet1;
	t1.Insert(2);
	t1.Insert(1);
	t1.Insert(3);
	copy = t1;
	copy.InOrder();
	cout<< endl;
	t1.InOrder();
	cout<< endl;
	return 0;
}

二叉搜索樹的應用

.K模型：K模型即只有key作為關鍵碼，結構中只需要存儲Key即可，關鍵碼即為需要搜索到
的值。
比如：給一個單詞word，判斷該單詞是否拼寫正確，具體方式如下：
以詞庫中所有單詞集合中的每個單詞作為key，構建一棵二叉搜索樹

在二叉搜索樹中檢索該單詞是否存在，存在則拼寫正確，不存在則拼寫錯誤

KV模型：每一個關鍵碼key，都有與之對應的值Value，即的鍵值對。該種方
式在現實生活中非常常見：
比如英漢詞典就是英文與中文的對應關系，通過英文可以快速找到與其對應的中文，英
文單詞與其對應的中文就構成一種鍵值對；

再比如統計單詞次數，統計成功后，給定單詞就可快速找到其出現的次數，單詞與其出
現次數就是就構成一種鍵值對
KV模型通過K去找V

Key/Value模型?

namespace KeyValue
{
	templatestruct BSTreeNode
	{
		BSTreeNode* _left;//Key和Value綁到一起
		BSTreeNode* _right;
		K _key;
		V _value;

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

	templateclass BSTree
	{
		typedef BSTreeNodeNode;
	public:
		bool Insert(const K& key, const V& value)
		{
			if (_root == nullptr)
			{
				_root = new Node(key, value);
				return true;
			}

			Node* parent = nullptr;
			Node* cur = _root;
			while (cur)
			{
				if (cur->_key< key)
				{
					parent = cur;
					cur = cur->_right;
				}
				else if (cur->_key >key)
				{
					parent = cur;
					cur = cur->_left;
				}
				else
				{
					return false;
				}
			}

			cur = new Node(key, value);
			if (parent->_key< key)
			{
				parent->_right = cur;
			}
			else
			{
				parent->_left = cur;
			}

			return true;
		}

		Node* Find(const K& key)//查找的時候以K去查找，返回的時候返回節點指針，以便于修改
		{
			Node* cur = _root;
			while (cur)
			{
				if (cur->_key< key)
				{
					cur = cur->_right;
				}
				else if (cur->_key >key)
				{
					cur = cur->_left;
				}
				else
				{
					return cur;
				}
			}

			return nullptr;
		}

		bool Erase(const K& key)//用K刪除
		{
			//...

			return true;
		}

		void InOrder()
		{
			_InOrder(_root);
			cout<< endl;
		}
	private:

		void _InOrder(Node* root)
		{
			if (root == nullptr)
			{
				return;
			}

			_InOrder(root->_left);
			cout<< root->_key<< ":"<< root->_value<< endl;
			_InOrder(root->_right);
		}
	private:
		Node* _root = nullptr;
	};

英譯漢

統計水果出現的次數

鏈表相交和復雜鏈表的賦值可用kv模型。

你是否還在尋找穩定的海外服務器提供商？創新互聯www.cdcxhl.cn海外機房具備T級流量清洗系統配攻擊溯源，準確流量調度確保服務器高可用性，企業級服務器適合批量采購，新人活動首月15元起，快前往官網查看詳情吧

分享名稱：C++——二叉搜索樹-創新互聯
分享URL：http://m.newbst.com/article26/dsojjg.html

成都網站建設公司_創新互聯，為您提供網站內鏈、營銷型網站建設、服務器托管、小程序開發、品牌網站建設、自適應網站

廣告

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