目錄
1、二叉搜索樹
2、二叉搜索樹的相關(guān)操作。
1、查找
2、插入
3、刪除
3、代碼實(shí)現(xiàn)（非遞歸）
1、二叉搜索樹
二叉搜索樹（Binary Search Tree，簡稱BST）是一種特殊的二叉樹，其中每個(gè)節(jié)點(diǎn)的值大于其左子樹中所有節(jié)點(diǎn)的值，小于其右子樹中所有節(jié)點(diǎn)的值。這種特性使得二叉搜索樹具有快速的查找、插入和刪除操作。
二叉搜索樹的性質(zhì)包括：
- 左子樹中所有節(jié)點(diǎn)的值小于根節(jié)點(diǎn)的值；
- 右子樹中所有節(jié)點(diǎn)的值大于根節(jié)點(diǎn)的值；
- 左右子樹也分別為二叉搜索樹。
如下圖所示：
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
2、二叉搜索樹的相關(guān)操作。
1、查找
a、從根開始比較，查找，比根大則往右邊走查找，比根小則往左邊走查找。
b、最多查找高度次，走到到空，還沒找到，這個(gè)值不存在。
2、插入
a. 樹為空，則直接新增節(jié)點(diǎn)，賦值給root指針
b. 樹不空，按二叉搜索樹性質(zhì)查找插入位置，插入新節(jié)點(diǎn)
3、刪除
刪除操作也是最值得思考的操作，因?yàn)橛兴姆N情況
a. 要?jiǎng)h除的結(jié)點(diǎn)無孩子結(jié)點(diǎn)
這是最簡單的情況，直接刪除節(jié)點(diǎn)就好，并且將該節(jié)點(diǎn)的父節(jié)點(diǎn)對應(yīng)的指針置為nullptr
b. 要?jiǎng)h除的結(jié)點(diǎn)只有左孩子結(jié)點(diǎn)
如果為根節(jié)點(diǎn)，那么直接讓該節(jié)點(diǎn)的左孩子變?yōu)楦?jié)點(diǎn)即可。
如果不為根節(jié)點(diǎn)，那么需要判斷該節(jié)點(diǎn)是prev(該節(jié)點(diǎn)的父節(jié)點(diǎn)）的左孩子還是右孩子，讓對應(yīng)的指針指向該節(jié)點(diǎn)的左孩子即可。
c.
要?jiǎng)h除的結(jié)點(diǎn)只有右孩子結(jié)點(diǎn)
如果為根節(jié)點(diǎn)，同上操作，只是變?yōu)閷υ摴?jié)點(diǎn)右孩子的操作不為根節(jié)點(diǎn)，判斷該節(jié)點(diǎn)是prev(該節(jié)點(diǎn)的父節(jié)點(diǎn)）的左孩子還是右孩子，讓對應(yīng)的指針指向該節(jié)點(diǎn)的右孩子即可。
d.
要?jiǎng)h除的結(jié)點(diǎn)有左、右孩子結(jié)點(diǎn)
如果該節(jié)點(diǎn)有左孩子和右孩子，那么如何操作才能在不破壞二叉搜索樹結(jié)構(gòu)的情況下完成刪除呢？我們需要找到該節(jié)點(diǎn)的 最小右孩子來替換該節(jié)點(diǎn)，這樣就可以解決問題。最小右孩子：最小右孩子分為兩種情況：1.當(dāng)前節(jié)點(diǎn)的右孩子節(jié)點(diǎn)的最小左孩子。2.若是當(dāng)前節(jié)點(diǎn)的右孩子節(jié)點(diǎn)沒有最小左孩子，那么當(dāng)前節(jié)點(diǎn)的右孩子節(jié)點(diǎn)就是最小右孩子。下面是一段代碼 實(shí)現(xiàn)，cur就是 當(dāng)前要?jiǎng)h除的節(jié)點(diǎn)，我們將它設(shè)為初始的最小右孩子的父節(jié)點(diǎn)，然后while循環(huán)查找最小左孩子，最后判斷最小右孩子是該父節(jié)點(diǎn)的左右指針，將對應(yīng)指針指向RightMin->_right;
Node* RightMinParent = cur;
Node* RightMin = cur->_right;
while (RightMin->_left)
{
RightMinParent = RightMin;
RightMin = RightMin->_left;
}
cur->_key = RightMin->_key;
if (RightMin == RightMinParent->_left)
{
RightMinParent->_left = RightMin->_right;
}
else
{
RightMinParent->_right = RightMin->_right;
}
delete RightMin;
return true;3、代碼實(shí)現(xiàn)（非遞歸）
二叉搜索樹的實(shí)現(xiàn)：
1.?
K
模型：
K
模型即只有
key
作為關(guān)鍵碼，結(jié)構(gòu)中只需要存儲(chǔ)
Key
即可，關(guān)鍵碼即為需要搜索到
的值
。
比如：
給一個(gè)單詞
word
，判斷該單詞是否拼寫正確
，具體方式如下：
以詞庫中所有單詞集合中的每個(gè)單詞作為
key
，構(gòu)建一棵二叉搜索樹
在二叉搜索樹中檢索該單詞是否存在，存在則拼寫正確，不存在則拼寫錯(cuò)誤。
2.
KV
模型：每一個(gè)關(guān)鍵碼
key
，都有與之對應(yīng)的值
Value
，即
<Key, Value>
的鍵值對
。該種方
式在現(xiàn)實(shí)生活中非常常見：
比如
英漢詞典就是英文與中文的對應(yīng)關(guān)系
，通過英文可以快速找到與其對應(yīng)的中文，英文單詞與其對應(yīng)的中文<word, chinese>
就構(gòu)成一種鍵值對；
再比如
統(tǒng)計(jì)單詞次數(shù)
，統(tǒng)計(jì)成功后，給定單詞就可快速找到其出現(xiàn)的次數(shù)，
單詞與其出
現(xiàn)次數(shù)就是
<word, count>
就構(gòu)成一種鍵值對
#pragma once
namespace key_value
{
template<class K, class V>
struct BSTreeNode
{
typedef BSTreeNode<K, V> Node;
Node* _left;
Node* _right;
K _key;
V _value;
BSTreeNode(const K& key, const V& value)
:_left(nullptr)
,_right(nullptr)
,_key(key)
,_value(value)
{
}
};
template<class K,class V>
class BSTree
{
typedef BSTreeNode<K, V> Node;
public:
bool Insert(const K& key, const V& value)
{
if (_root == nullptr)
{
_root = new Node(key, value);
return true;
}
Node* prev = nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_key > key)
{
prev = cur;
cur = cur->_left;
}
else if (cur->_key < key)
{
prev = cur;
cur = cur->_right;
}
else
{
return false;
}
}
Node* newnode = new Node(key,value);
if (prev->_key > key)
{
prev->_left = newnode;
}
else if (prev->_key < key)
{
prev->_right = newnode;
}
return true;
}
Node* Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (cur->_key > key)
{
cur = cur->_left;
}
else if (cur->_key < key)
{
cur = cur->_right;
}
else
{
return cur;
}
}
}
bool Erase(const K& key)
{
Node* prev = nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_key > key)
{
prev = cur;
cur = cur->_left;
}
else if(cur->_key<key)
{
prev = cur;
cur = cur->_right;
}
else
{
if (cur->_left == nullptr)
{
if (cur == _root)
{
cur = cur->_right;
}
else
{
if (cur == prev->_left)
{
prev->_left = cur->_right;
}
else
{
prev->_right = cur->_right;
}
}
delete cur;
return true;
}
else if (cur->_right == nullptr)
{
if (cur == _root)
{
cur = cur->_left;
}
else
{
if (cur == prev->_left)
{
prev->_left = cur->_left;
}
else
{
prev->_right = cur->_left;
}
}
delete cur;
return true;
}
else
{
Node* RightMinParent = cur;
Node* RightMin = cur->_right;
while (RightMin->_left)
{
RightMinParent = RightMin;
RightMin = RightMin->_left;
}
cur->_key = RightMin->_key;
if (RightMin == RightMinParent->_left)
{
RightMinParent->_left = RightMin->_right;
}
else
{
RightMinParent->_right = RightMin->_right;
}
delete RightMin;
return true;
}
}
}
return false;
}
void Inoder()
{
inoderprint(_root);
cout << endl;
}
void inoderprint( Node* root)
{
if (root == nullptr)
{
return;
}
inoderprint(root->_left);
cout << root->_key << " " << root->_value << endl;
inoderprint(root->_right);
}
private:
Node* _root = nullptr;
};
}以上實(shí)現(xiàn)是 KV模型：文章來源：http://www.zghlxwxcb.cn/news/detail-837332.html
可以使用以下代碼測試功能：文章來源地址http://www.zghlxwxcb.cn/news/detail-837332.html
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
#include"BSTree.h"
int main()
{
key_value::BSTree<string, int> BST;
BST.Insert("蘋果",12);
BST.Insert("梨",10);
BST.Insert("草莓",9);
BST.Insert("橘子",11);
BST.Inoder();
BST.Erase("梨");
BST.Inoder();
key_value::BSTreeNode<string,int> *node=BST.Find("蘋果");
cout << node->_key << " " << node->_value << endl;
return 0;
}
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)：二叉搜索樹（非遞歸實(shí)現(xiàn)）的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
