C/C++ 高階數據結構 —— 二叉搜索樹（二叉排序樹）

在這里插入圖片描述

? 🎁個人主頁：工藤新一1

? 🔍系列專欄：C++面向對象（類和對象篇）

? 🌟心中的天空之城，終會照亮我前方的路

? 🎉歡迎大家點贊👍評論📝收藏?文章

文章目錄

二叉查找樹 OR 二叉排序樹（BST）
- 一、核心概念：一句話定義
- 二、二叉查找樹的刪除
- - 2.1刪除葉子節點
  - 2.2刪除度為1的節點
  - 2.3刪除分支節點
  - - 2.3.1普通分支節點
    - 2.3.2根節點
- 三、核心邏輯實現
- - 3.1二叉搜索樹查找邏輯
  - 3.2二叉搜索樹插入邏輯
  - 3.3二叉搜索樹刪除邏輯
  - 3.4丟棄遞歸返回值問題

二叉查找樹 OR 二叉排序樹（BST）

二叉查找樹和二叉排序樹是完全同一個概念，指的是同一種數據結構，其也是面試常客

二叉樹具體的呈現：

在這里插入圖片描述

刪除與插入的處理方式都需以查找為基礎

在標準的二叉搜索樹（BST）定義中：

? 通常不允許重復元素
? 每個節點的鍵值(key)都是唯一的
? 遵循嚴格的大小關系：左子樹 < 根節點 < 右子樹

一、核心概念：一句話定義

在這里插入圖片描述

? 二叉查找樹是一種特殊的二叉樹，他給它的節點立下了嚴格的“規矩”：對于樹中的任意一節點，其左子樹中所有節點值都必須小于根節點，其右子樹中所有節點值都必須大于其根節點

這個“規矩”就是二叉查找樹的靈魂，它的一切神奇特性都源于此

在這里插入圖片描述

二、二叉查找樹的刪除

重點問題：如何填補空缺（節點），才能保持整個二叉樹的結構不發生變化，且不違反其定義？

在這里插入圖片描述

2.1刪除葉子節點

刪除node3：

在這里插入圖片描述

2.2刪除度為1的節點

刪除node6：

在這里插入圖片描述

我們觀察node6只有左子樹，那么可以直接將 node6->left（node6的前驅節點：node5）放入node6所在的位置

在這里插入圖片描述

因此，刪除度為1的節點，我們可以直接將其左 or 右子樹，放在（占用）當前節點所處的位置上即可（其余節點不需調整）

2.3刪除分支節點

2.3.1普通分支節點

刪除node7：

在這里插入圖片描述

我們可以參考刪除度為1節點的邏輯：將 node7的前驅/后繼節點占用到node7的位置上

在這里插入圖片描述

將 node7的前驅節點（node->left）node6放置node7 所處位置上

在這里插入圖片描述

2.3.2根節點

O(logN)[查找刪除根節點] * O(1)[刪除] * O(logN)[查找替換根節點的根節點的后繼/前驅節點] * O(1)[刪除]

在這里插入圖片描述

最終形成的邏輯結果：

在這里插入圖片描述

問題：既然 node14 的后繼節點是 node15，那么為什么不是：

在這里插入圖片描述

這是因為，我們已知 node14 只有右子樹（即node14度為1），那么我們就可以直接利用 “節點度為1” 的情況的處理方式來進行節點的替換。正常對于二叉樹的樹形結構不清楚時，一定是要判斷對應刪除的節點的前驅后繼節點（處理方式：遞歸查找），進行對應刪除替換邏輯

? 刪除度為2的節點，其實是對整個樹的遞歸式的刪除（將對應節點的前驅/后繼指針刪除后再替換至當前刪除位置，并且可能會產生二次替換：將當前節點的前驅/后繼節點的前驅/后繼替換到當前前驅/后繼節點的位置上；第三次替換：…）

但實際上，搜索時間復雜度最差的情況為：O(N)

從根節點–>最終的葉子節點 == 樹的高度

樹形結構中樹的高度：logN

線性樹形結構中樹的高度：N（即整個樹的節點個數）

在這里插入圖片描述

二叉樹

邏輯結構上：樹形結構
存儲結構上：線性的單鏈表結構，因此就有了O(N)的時間復雜度

三、核心邏輯實現

二叉搜索樹（或：二叉排序樹），其最主要的特點：中序遍歷會得到一個遞增序列，無論是查找/排序都可以非常高效的實現。在實際生產過程中 二叉排序樹 是所運用到的最主要的樹形結構

創建搜索二叉樹：

// 定義樹節點存儲的數據類型
typedef int ElemType;// 定義樹的節點類型
typedef struct BinarySearchTree
{ElemType data;struct BinarySearchTree* left, * right;// 構造函數 - 初始化字段BinarySearchTree(int val) :data(val), left(nullptr), right(nullptr) { }
} TreeNode;

3.1二叉搜索樹查找邏輯

1.對比待查找關鍵字值與當前節點的數據域
2.關鍵字值 < 數據域：向左子樹遞歸查找
3.關鍵字值 > 數據域：向右子樹遞歸查找
復雜度分析：
空間復雜度：O(1) - 無需額外定義其他空間

? 時間復雜度（樹的所有動作都是基于查找來執行）：查找次數與樹的高度（層次）等價 - O(logN)

二叉樹中序遍歷（遞歸）– 算法分離：

時間復雜度：O(N)

遍歷函數：

void InOrderByRec(TreeNode* node)
{if (!node) return;InOrderByRec(node->left);cout << node->data << "->";InOrderByRec(node->right);
}

查找函數：

TreeNode* SearchByRec(TreeNode* tree, int key)
{TreeNode* cursor = tree;if (!cursor) return nullptr;if (key == cursor->data) return cursor;if(key < cursor->data)return SearchByRec(cursor->left, key); // 只在左子樹搜索if(key > cursor->data)return SearchByRec(cursor->right, key); // 只在右子樹搜索
}

簡潔代碼（三目表達式）：

C++return (key < cursor->data) ? SearchByRec(cursor->left, key) : SearchByRec(cursor->right, key);

二叉樹中序遍歷（循環）：

時間復雜度：O(logN)

TreeNode* SearchByFor(TreeNode* tree, int key)
{TreeNode* cursor = tree;while (cursor){if (key == cursor->data) return cursor;if (key < cursor->data) cursor = cursor->left;if (key > cursor->data) cursor = cursor->right;}return nullptr;
}

3.2二叉搜索樹插入邏輯

1.查找插入位置
2.新建節點，執行插入動作
3.返回操作標志

迭代邏輯：

bool Insert(TreeNode* tree, int key)
{if (!tree){tree = new TreeNode(key);return true;}// 1.查找插入的位置TreeNode* pos = tree, * parent = nullptr;// while循環結束意味著整個樹的高度查找結束while (pos){// 迭代更新 parent 成為 pos 父節點parent = pos;if (key == pos->data) return false;if (key < pos->data) pos = pos->left;if (key > pos->data) pos = pos->right;}// 2.新建節點，執行插入動作if (key < parent->data) parent->left = new TreeNode(key);if (key > parent->data) parent->right = new TreeNode(key);return true;
}

🚫🚫🚫嚴重錯誤遞歸代碼：

在這里插入圖片描述

現在的疑問希望未來可以解答：

為什么需要返回遞歸結果？并且 A如何使最后那一節點指向 TreeNode(key)？

在這里插入圖片描述

🚫🚫🚫我懂了！！！！為什么我的代碼出現了巨大錯誤！！

在這里插入圖片描述

3.3二叉搜索樹刪除邏輯

指定刪除二叉搜索樹中的節點：

1.查找指定關鍵字值的節點，及其父節點
2.檢查待刪除節點是否符合條件：
- 缺少左子樹，用右子樹補位；反之；（左右子樹不共存）
- 缺少左右子樹（即葉子節點）直接刪除（斷開與父節點的千絲萬縷）
- 左右子樹都存在，按中序遍歷查找當前節點的補位（替代）節點（前驅/后繼）
  
  直接前驅：即左子樹的最右節點（中序遍歷節點前后指針規律）
  
  直接后繼：即右子樹的最左節點
3.遞歸刪除操作：刪除替代節點
- 刪除當前節點 + 刪除補位節點 + 刪除補位節點的補位節點…
- 注意1：需保留當前待刪節點（遞歸刪除：優先刪除下層待刪節點（遍歷節點[地推] + 從下至上刪除補位節點[回歸]）- 因此再次證明遞歸是一個棧結構）
- 注意2：遞歸刪除替代節點時，需將父節點作為樹的新的樹指針需保留
4.使用補位節點替換原本的待刪節點
- 修改/斷開鏈接：父節點/左/右子樹

在這里插入圖片描述

bool Delete(TreeNode* tree, int key)
{if (!tree) return false;//1.查找指定關鍵字值的節點，及其對應父節點TreeNode* pos = tree, *child = nullptr, *parent = nullptr;while (pos){if (key == pos->data){child = pos;// 結束最內層循環break; // 貌似不可使用 return; - 結束整個函數運行}// 若根節點為目標節點 parent == nullptr，反之迭代更新 parentparent = child; // 當前節點為父節點，向其子節點查找if (key < pos->data) pos = pos->left;if (key > pos->data) pos = pos->right;}// 開發技巧：對child進行為空判定，因為 key 可能不存在于樹中，child 仍然為 nullptrif (!child) return false;// 2.檢查待刪除節點是否符合條件（進行遞歸刪除）：// a.左/右子樹不共存 + 左/右子樹同時不存在（葉子節點）if (!child->left || !child->right){
/*// 補位節點TreeNode* subNode = nullptr;if (!child->left) subNode = child->right;else subNode = child->left;subNode = child->left == nullptr ? child->right : child->left;
*/TreeNode* subNode = child->left == nullptr ? child->right : child->left;// parent 判空（刪除根節點時）if (parent){// 將補位節點掛載到 parent下方// 若child 原本掛載到 parent的左子樹上，就讓補位節點替換到 parent左子樹上（child的位置）if (parent->left == child) parent->left = subNode;if (parent->right == child) parent->right = subNode;}else // 父節點不存在 - 即刪除根節點 - 直接將子樹節點向上提升一個層次{// 直接將下級子樹的根節點作為整個樹的根節點 - 為什么可以這么做？因為左右子樹不共存tree = subNode;}return true;}// b.左右子樹都存在，按中序遍歷查找當前節點的補位（替代）節點（前驅/后繼）TreeNode* replacer = child, * replacer_parent = parent;// 查找直接前驅 - 左子樹的最右節點pos = child->left;// 查找直接后繼 - 右子樹的最左節點：pos = child->right;while (pos){// 補位節點的父節點就是上一次循環的 replacerreplacer_parent = replacer;// 記錄補位節點replacer = pos;pos = pos->right;// pos = pos->left; 直接后繼（直接前驅/后繼無法共存）}// 3.遞歸刪除操作：刪除替代節點// 樹根 - replacer_parent; 待刪除內容 - replacer->dataDelete(replacer_parent, replacer->data);// 4.使用補位節點替換原本的待刪節點if (parent){// parent->left 指向待刪節點if (parent->left == child)// 那么就使其指向補位節點parent->left = replacer;elseparent->right = replacer;}replacer->left = child->left;replacer->right = child->right;// 斷開已刪除節點與子樹的聯系（與父節點的聯系已斷開）child->left = nullptr, child->right = nullptr;
}