408答疑

---

---

三、樹形查找

二叉排序樹（BST）

• 構造二叉排序樹的目的并不是排序，而是提高查找、插入和刪除關鍵字的速度，二叉排序樹這種非線性結構也有利于插入和刪除的實現。
• 二叉排序樹（也稱二叉查找樹）或者是一棵空樹，或者是具有下列特性的二叉樹：
  1. 若左子樹非空，則左子樹上所有結點的值均小于根結點的值。
  2. 若右子樹非空，則右子樹上所有結點的值均大于根結點的值。
  3. 左、右子樹也分別是一棵二叉排序樹。

二叉排序樹中結點值之間的關系

根據二叉排序樹的定義，左子樹結點值 < 根結點值 < 右子樹結點值，因此對二叉排序樹進行中序遍歷，可以得到一個遞增的有序序列。如下圖所示二叉排序樹的中序遍歷序列為 123468。

二叉樹形查找

• 二叉樹形查找是以二叉排序樹（BST）為基礎進行查找，并演化出相應的平衡樹AVL和紅黑樹RB。
• 除了掌握基礎的查找，還需掌握平衡樹的平衡調整過程。

二叉排序樹的查找過程

二叉排序樹的查找是從根結點開始，沿某個分支逐層向下比較的過程。若二叉排序樹非空，先將給定值與根結點的關鍵字比較，若相等，則查找成功；若不等，若小于根結點的關鍵字，則在根結點的左子樹上查找，否則在根結點的右子樹上查找。這顯然是一個遞歸的過程。

示例

如下圖中查找值為 4 的結點。首先 4 與根結點 6 比較。由于 4 小于 6，所以在根結點 6 的左子樹中繼續查找。由于 4 大于 2，所以在結點 2 的右子樹中查找，查找成功。

向二叉排序樹中插入結點

二叉排序樹作為一種動態樹表，其特點是樹的結構通常不是一次生成的，而是在查找過程中，當樹中不存在關鍵字值等于給定值的結點時再進行插入的。

插入過程

• 若原二叉排序樹為空，則直接插入；
• 否則，若關鍵字 $k$ 小于根結點值，則插入到左子樹，若關鍵字 $k$ 大于根結點值，則插入到右子樹。
• 插入的結點一定是一個新添加的葉結點，且是查找失敗時的查找路徑上訪問的最后一個結點的左孩子或右孩子。

示例

下圖展示了在一棵二叉排序樹中依次插入結點 28 和結點 58 的過程，虛線表示的邊是其查找的路徑。

構造二叉排序樹的過程

從一棵空樹出發，依次輸入元素，將它們插入二叉排序樹中的合適位置。設查找的關鍵字序列為 {45, 24, 53, 45, 12, 24}，則生成的二叉排序樹如下圖所示。

構造示例

每一步都是根據關鍵字與當前樹中結點的比較結果，決定插入的位置。

二叉排序樹中刪除結點的操作

在二叉排序樹中刪除一個結點時，不能簡單地刪除該結點及其所有子結點，而是需要重新鏈接因刪除結點而斷開的二叉鏈表，確保二叉排序樹的性質不丟失。刪除操作的實現過程按以下三種情況來處理：

情況一：被刪除結點是葉結點

• 若被刪除結點 $z$ 是葉結點，則直接刪除，不會破壞二叉排序樹的性質。

情況二：被刪除結點只有一棵左子樹或右子樹

• 若結點 $z$ 只有一棵左子樹或右子樹，則讓 $z$ 的子樹成為 $z$ 父結點的子樹，替代 $z$ 的位置。

情況三：被刪除結點有左、右兩棵子樹

• 若結點 $z$ 有左、右兩棵子樹，則令 $z$ 的直接后繼（或直接前驅）替代 $z$，然后從二叉排序樹中刪去這個直接后繼（或直接前驅），這樣就轉變成了第一或第二種情況。

二叉排序樹中刪除并插入某結點的分析

若在二叉排序樹中刪除并插入某結點，得到的二叉排序樹是否和原來的相同？

不一定。這個問題需要考慮刪除和插入操作對樹結構的影響，以及這些操作是否能夠恢復到原始的樹結構。具體分析可能涉及到樹的平衡性、結點的相對位置以及操作的順序等因素。

代碼實操

結構定義

• 定義二叉排序樹的結點結構體 BSTNode，包含數據域 data，指向左子樹的指針 left 和指向右子樹的指針 right。

typedef struct BSTNode {ElemType data;struct BSTNode *left;struct BSTNode *right;
} BSTNode, *BSTRoot;

插入操作

• 在二叉排序樹中插入值 x，遞歸地找到正確的位置插入新結點。

bool insertBST(BSTNode *&t, int x) {if (t == NULL) {t = (BSTNode*)malloc(sizeof(BSTNode));t->data = x;t->left = t->right = NULL;return true; // 插入成功}if (x == t->data)return false; // 插入失敗if (x < t->data)insertBST(t->left, x);elseinsertBST(t->right, x);return true;    
}

查找操作

• 在二叉排序樹中查找關鍵字 key，遞歸地遍歷樹直到找到或到達葉子結點。

BSTNode* searchBST(BSTNode *t, int key) {if (t == NULL || t->data == key)return t;if (key < t->data)return searchBST(t->left, key);else return searchBST(t->right, key);
}

刪除操作

• 刪除二叉排序樹中關鍵字為 key 的結點，處理三種情況：無子結點、一個子結點、兩個子結點。

bool removeBST(BSTNode *&t, int key) {if (t == NULL)return false; // 刪除失敗if (key < t->data)removeBST(t->left, key);else if (key > t->data)removeBST(t->right, key);else {BSTNode *p = NULL;if (t->left != NULL && t->right != NULL) {p = t->left;while (p->right != NULL)p = p->right;t->data = p->data;removeBST(t->left, p->data);} else {BSTNode *child = (t->left != NULL) ? t->left : t->right;p = t;t = child;free(p);}}return true;
}

中序遍歷

• 對二叉排序樹進行中序遍歷，輸出有序序列。

void sortBST(BSTNode *t) {if (t != NULL) {sortBST(t->left);printf("%d ", t->data);sortBST(t->right);}
}

六、參考資料

鮑魚科技課件

b站免費王道課后題講解:

網課全程班:

26王道考研書