在前兩篇文章中我們詳細介紹了使用智能指針建構二叉樹并進行了層序周遊。
現在我們已經掌握了足夠的前置知識，可以深入了解二叉搜尋樹的查找和删除了。
本文索引
- 二叉搜尋樹的查找
- 查找最小值和最大值
- 查找特定值
- 删除節點
- 測試
查找将分為兩部分，最值查找和特定值查找。
本章中使用的二叉搜尋樹的結構和上一篇文章中的相同。
下面我們先來看看最值查找。
這是最簡單的一種查找。
根據二叉搜尋樹的性質，左子樹的值都比根節點小，右子樹的值都比根節點大，且這一性質對根節點下任意的左子樹或右子樹都适用。
根據以上的性質，對于一棵二叉搜尋樹來說，最小的值的節點一定在左子樹上，且是最左邊的一個節點；同理最大值一定是右子樹上最右邊的那個節點，如圖所示：
查找的算法也極為簡單，隻要不停遞歸搜尋左子樹/右子樹，然後将左邊或右邊的葉子節點傳回，這就是最小值/最大值：
NodeType BinaryTreeNode::max()
{
// 沒有右子樹時根節點就是最大的
if (!right) {
return shared_from_this();
}
auto child = right;
while (child) {
if (child->right) {
child = child->right;
} else {
return child;
}
}
return nullptr;
}
NodeType BinaryTreeNode::min()
{
// 沒有左子樹時根節點就是最小的
if (!left) {
return shared_from_this();
}
auto child = left;
while (child) {
if (child->left) {
child = child->left;
} else {
return child;
}
}
return nullptr;
}
這裡我們用循環替代了遞歸，使用遞歸的實作将會更簡潔，讀者可以自己留作聯系。
查找特定值的情況較最值要複雜一些，因為需要判斷如下幾種情況，假設我們查找的值是
value
：
- value和目前節點的值相等，查找完成傳回目前節點
- value小于目前節點的值，繼續所搜左子樹，左子樹的值都比目前節點小
- value大于目前節點的值，繼續所搜右子樹，右子樹的值都比目前節點大
- 目前節點沒有左/右子樹而需要繼續搜尋子樹時，查找失敗value在樹中不存在，傳回
nullptr
這次我們決定采用遞歸實作，基于上述描述使用遞歸實作更簡單，如果有興趣的話也可以用循環實作，雖然兩者在性能上的表現并不會相差太多（因為遞歸查找的次數隻有log2(N)+1次，次數較少無法充分展現循環帶來的性能優勢）：
NodeType BinaryTreeNode::search(int value)
{
if (value == value_) {
return shared_from_this();
}
// 繼續向下搜尋
if (value < value_ && left) {
return left->search(value);
} else if (value > value_ && right) {
return right->search(value);
}
// 未找到value
return nullptr;
}
查找算法雖然分了兩部分，但和删除節點相比還是比較簡單的。
通常我們删除一棵樹的某個節點時，将其子節點轉移給自己的parent即可，然而二叉搜尋樹需要自己的每一部分都遵守二叉樹搜尋樹的性質，是以對于大部分情況來說直接将子節點交給parent将會導緻二叉搜尋樹被破壞，是以我們需要對如下幾個情況分類讨論：
- 情況a：待删除節點沒有任何子節點，此節點是葉子節點，這時可以直接删除它
- 情況b：待删除節點隻有左/右子樹，這時直接删除節點，将子節點交給parent即可，不會影響二叉搜尋樹的性質
- 情況c：待删除節點同時擁有左右子樹，這時為了删除節點後仍是一棵二叉搜尋樹，有兩個待選方案：
- 選擇待删除節點的左子樹的最大值，和待删除節點交換值，然後将這個左子樹的最大節點删除，因為左子樹的值都需要比根節點小，是以删除根節點時從左子樹中找到最大值交換到根節點的位置，即可保證滿足二叉搜尋樹的性質；接着對左子樹最大節點做相同的分類讨論，最後經過交換後節點會滿足前兩種中的一種情況，這是删除這個節點，整個删除過程即可完成
- 原理同上一種，隻不過我們選擇了右子樹中的最小值的節點
隻有描述會比較抽象，是以每種情況我們來看圖：
情況a：
紅色虛線的部分即為待删除節點，這是直接删除即可。
情況b：
如圖所示，當隻存在一邊的子樹時，直接删除節點，将子節點交給parent即可。
情況c較為複雜，我們舉例選擇右子樹最小值的情況，另一種情況是相似的：
圖中黃色虛線部分就是“待删除節點”，加引号是因為我們并不真正删除它，而是先要把它的值和右子樹的最小值也就是紅色虛線部分交換：
交換後我們删除右子樹的最小值節點，這是它滿足情況a，是以直接被删除，删除後的樹仍是一棵二叉搜尋樹：
這裡解釋下為什麼需要交換，首先交換是把情況c盡量往情況a或b轉化簡化了問題，同時保證了二叉搜尋樹的性質；其次如果不進行交換，則需要大量移動節點，性能較差且實作極為複雜，是以我們才會選擇交換節點值的做法。
我們的代碼也會根據上述情況進行分類讨論，這次我們使用遞歸實作來簡化代碼，同樣讀者如果有興趣可以研究下循環版本：
// 公開的接口，友善使用者調用，具體實作在私有方法remove_node中
void BinaryTreeNode::remove(int value)
{
auto node = search(value);
if (!node) {
return;
}
node->remove_node();
}
// 删除節點的具體實作
void BinaryTreeNode::remove_node()
{
// parent是weak_ptr，需要檢查是否可通路
auto p{parent.lock()};
if (!p) {
return;
}
// 情況a，這時判斷節點在parent的左側還是右側
// 随後對正确的parent子節點指派nullptr，目前節點會在函數傳回後自動被釋放
if (!left && !right) {
if (value_ > p->value_) {
p->right = nullptr;
} else {
p->left = nullptr;
}
return;
}
// 情況c，選擇和右子樹最小值交換
if (left && right) {
auto target = right->min();
target->remove_node();
// 這裡和圖解有一點小小的不同
// 删除target前改變了value_，會導緻target被删除時無法正确确認自己是在parent的左側還是右側
// 是以隻能在target删除結束後再将值指派給目前節點
value_ = target->value_;
return;
}
// 下面是情況b的兩種可能的形式
// 隻存在左子樹
if (left) {
if (value_ > p->value_) {
p->right = left;
} else {
p->left = left;
}
left->parent = p;
return;
}
// 隻存在右子樹
if (right) {
if (value_ > p->value_) {
p->right = right;
} else {
p->left = right;
}
right->parent = p;
return;
}
}
進行分類讨論後代碼實作起來也就沒有那麼複雜了。
現在該測試上面的代碼了：
int main()
{
auto root = std::make_shared<BinaryTreeNode>(3);
root->insert(1);
root->insert(0);
root->insert(2);
root->insert(5);
root->insert(4);
root->insert(6);
root->insert(7);
root->layer_print();
std::cout << "max: " << root->max()->value_ << std::endl;
std::cout << "min: " << root->min()->value_ << std::endl;
root->remove(1);
// 删除後是否還是二叉搜尋樹使用中序周遊即可得知
std::cout << "after remove 1\n";
root->ldr();
root->insert(1);
root->remove(5);
std::cout << "after remove 5\n";
root->ldr();
}
結果：
如圖，二叉搜尋樹的中序周遊結果是一個有序的序列，兩次元素的删除後中序周遊的結果都為有序序列，算法是正确的。