數據結構之二叉搜索樹-創新互聯
一。定義：二叉搜索樹（Binary Search Tree），也稱有序二叉樹（ordered binary tree）,排序二叉樹（sorted binary tree），是指一棵空樹或者具有下列性質的二叉樹：
1. 若任意節點的左子樹不空，則左子樹上所有結點的值均小于它的根結點的值；
2. 若任意節點的右子樹不空，則右子樹上所有結點的值均大于它的根結點的值；
3. 任意節點的左、右也分別為二叉查找樹。
4. 沒有鍵值相等的節點（no duplicate nodes）。
根據二叉搜索樹的特點知：對二叉搜索樹進行中序遍歷得到的結點序列必然是一個有序序列。
一棵二叉搜索樹：
根據樹的結構，我們可以封裝一個結點的結構BSNode：
template<class K,class V>
struct BSNode
{
BSNode<K, V>* _left;
BSNode<K, V>* _right;
K _key;
V _value;
BSNode(const K& key, const V& value)
:_left(NULL)
, _right(NULL)
,_key(key)
, _value(value)
{}
};在這里樹的結構封裝了key/value形式的鍵值對。
二叉搜索樹的結構我們更加關注的是它的增刪查改功能。而且在這過程中我們要保證整棵樹中沒有重復的key值（結點的值）
所以封裝一棵二叉搜索樹BSTree：
template<class K,class V>
class BSTree
{
public:
typedef BSNode<K, V> Node;<pre name="code" class="cpp">//增刪改查功能
protected:
Node* _root;
};二。實現
(一）插入新結點
bool Insert(const K& key, const V& value)//<span >非遞歸形式</span>
{
if (_root == NULL)
{
_root = new Node(key, value);
return true;
}
Node* parent = NULL;
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
return false;
}
if (parent->_left == NULL && parent->_key > key)
{
parent->_left = new Node(key, value);
}
else if (parent->_right == NULL && parent->_key < key)
{
parent->_right = new Node(key, value);
}
return true;
}bool Insert_R(const K& key, const V& value)//<span >插入的遞歸實現</span>
{
return _Insert_R(_root, key, value);
}</span><pre name="code" class="cpp">bool _Insert_R(Node*& root,const K& key, const V& value)
{
if (root == NULL)
{
root = new Node(key, value);
return true;
}
if (root->_key > key)
_Insert_R(root->_left, key, value);
else if (root->_key < key)
_Insert_R(root->_right, key, value);
else
return false;
return false;
}插入節點的思路就是遞歸的找要插入的位置，直到root為NULL，那么當前位置就是要插入的位置。
（二）查找結點，返回該結點
Node* Find(const K& key) //<span >非遞歸實現</span>
{
Node* cur = _root;
while (cur)
{
if (cur->_key > key)
{
cur = cur->_left;
}
else if (cur->_key < key)
{
cur = cur->_right;
}
else
return cur;
}
return NULL;
}Node* Find_R(const K& key)//<span >遞歸實現</span>
{
return _Find_R(_root, key);
}<pre name="code" class="cpp">Node* _Find_R(Node* root,const K& key)
{
if (root == NULL)
return NULL;
if (root->_key > key)
_Find_R(root->_left, key);
else if (root->_key < key)
_Find_R(root->_right, key);
else
return root;
}查找的實現就是分三種情況，當前結點key大于key，小于key，等于key。大于key遞歸的在當前結點的右子樹查找，小于在左子樹找，等于就返回結點。
（三）刪除結點，使剩下結點仍是一棵二叉搜索樹
bool Remove(const K& key)//非遞歸實現
{
return _Remove(_root, key);
}bool _Remove(Node* root, const K& key)
{
if (root == NULL)
return false;
Node* parent = NULL;
Node* cur = root;
Node* del = NULL;
while (cur)
{
if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else
{
del = cur;
//待刪除結點左為空
if (cur->_left == NULL)
{
if (parent && parent->_left == cur)
parent->_left = cur->_right;
else if (parent && parent->_right == cur)
parent->_right = cur->_right;
else
_root = cur->_right;
}
else if (cur->_right == NULL)//待刪除結點右為空
{
if (parent && parent->_left == cur)
parent->_left = cur->_left;
else if (parent &&parent->_right == cur)
parent->_right = cur->_left;
else
_root = cur->_left;
}
else if (cur->_left == NULL && cur->_right == NULL)//待刪除結點左右都為空
{
if (parent && parent->_left == cur)
parent->_left = NULL;
else if (parent && parent->_right == cur)
parent->_right = NULL;
else
_root = NULL;
}
else if (cur->_left && cur->_right)//待刪除結點左右都不為空
{
//找出右子樹的最左結點
Node* firstleft = cur->_right;
parent = cur;
while (firstleft->_left)
{
parent = firstleft;
firstleft = firstleft->_left;
}
del = firstleft;
swap(cur->_key, firstleft->_key);
swap(cur->_value, firstleft->_value);
//判斷最左結點是它父節點的左結點還是右結點
if (parent && parent->_left == firstleft)
{
parent->_left = firstleft->_right;
}
else if (parent && parent->_right == firstleft)
{
parent->_right = firstleft->_right;
}
else //parent==NULL。待刪除結點的右邊只有一個結點，則最左結點就是它
{
root->_right = NULL;
}
}
delete del;
return true;
}
}
return false;
}bool Remove_R(const K& key)//遞歸實現
{
return _Remove_R(_root, key);
}<pre name="code" class="cpp">bool _Remove_R(Node*& root, const K& key)
{
if (root == NULL)
return false;
if (root->_key > key)
{
_Remove_R(root->_left, key);
}
else if (root->_key < key)
{
_Remove_R(root->_right, key);
}
else
{
Node* del = root;
if (root->_left == NULL&&root->_right == NULL)
{
root = NULL;
}
else if (root->_left == NULL)
{
root = root->_right;
}
else if (root->_right == NULL)
{
root = root->_left;
}
else
{
Node* parent = NULL;
Node* firstleft = root->_right;
while (firstleft->_left)
{
parent = firstleft;
firstleft = firstleft->_left;
}
del = firstleft;
swap(root->_key, firstleft->_key);
swap(root->_value, firstleft->_value);
if (parent && parent->_left == firstleft)
{
parent->_left = firstleft->_right;
}
else if (parent && parent->_right == firstleft)
{
parent->_right = firstleft->_right;
}
else //parent==NULL。待刪除結點的右邊只有一個結點，則最左結點就是它
{
root->_right = NULL;
}
}
delete del;
return true;
}
return false;
}刪除節點要考慮到的因素就要多了。我們可以劃分子問題的方法來解決：
查找待刪除的結點，每次判斷：
當前結點key值大于key。遞歸進入左子樹，繼續查找。
當前結點key值小于key。遞歸進入右子樹，繼續查找。
當前結點key值等于key。在這又分為4種情況：
當前結點的左子樹為空。刪除當前結點，把右子樹給當前指針
當前結點的右子樹為空。刪除當前結點，把左子樹給當前指針
當前結點的左右子樹都為空。把根指針置空，刪除當前結點。
當前結點的左右子樹都不為空。找到右子樹的最左結點，和待刪除結點交換值，刪除最左結點。
把這些因素都考慮周全就可以準確的刪除二叉搜索樹的任何一個結點。
另外有需要云服務器可以了解下創新互聯scvps.cn，海內外云服務器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務器、裸金屬服務器、高防服務器、香港服務器、美國服務器、虛擬主機、免備案服務器”等云主機租用服務以及企業上云的綜合解決方案，具有“安全穩定、簡單易用、服務可用性高、性價比高”等特點與優勢，專為企業上云打造定制，能夠滿足用戶豐富、多元化的應用場景需求。
本文標題：數據結構之二叉搜索樹-創新互聯
分享地址：http://vcdvsql.cn/article4/csccie.html
成都網站建設公司_創新互聯，為您提供虛擬主機、微信小程序、電子商務、面包屑導航、品牌網站設計、服務器托管
聲明：本網站發布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創新互聯
- 關于外貿網站建設的一些常見問題和解決思路 2016-12-11
- 北京企業應該如何做好外貿網站建設工作 2023-03-16
- 讓外貿網站建設更有利于谷歌優化的6個技巧？ 2016-09-21
- 從電子商務看外貿網站建設競爭對手 2021-01-18
- 外貿網站建設如何讓你的英文網站在同行業中脫穎而出 2016-03-16
- 外貿網站建設的未來發展方向 2020-11-18
- 外貿網站建設六大要點分析 2016-11-08
- 外貿網站建設經驗分享：網頁這樣設計大幅提升網站轉化率！ 2022-11-16
- LED燈箱外貿網站建設推廣：常見的推廣方式有哪些？ 2016-02-29
- 普陀外貿網站建設的建站原則 2020-11-18
- 外貿網站建設有什么不同的地方 2016-10-29
- 英文外貿網站建設解決方案 2023-02-07