溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
一。定義：二叉搜索樹（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種情況：
當前結點的左子樹為空。刪除當前結點，把右子樹給當前指針
當前結點的右子樹為空。刪除當前結點，把左子樹給當前指針
當前結點的左右子樹都為空。把根指針置空，刪除當前結點。
當前結點的左右子樹都不為空。找到右子樹的最左結點，和待刪除結點交換值，刪除最左結點。
把這些因素都考慮周全就可以準確的刪除二叉搜索樹的任何一個結點。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
