【C++數據結構——查找】二叉排序樹（頭歌實踐教學平臺習題）【合集】

目錄😋

任務描述

相關知識

1. 二叉排序樹的基本概念

2. 二叉排序樹節點結構體定義

3. 創建二叉排序樹

4. 判斷是否為二叉排序樹

5. 遞歸查找關鍵字為 6 的結點并輸出查找路徑

6. 刪除二叉排序樹中的節點

測試說明

通關代碼

測試結果

任務描述

本關任務：實現二叉排序樹的基本算法。

相關知識

為了完成本關任務，你需要掌握：

二叉排序樹的基本概念
?二叉排序樹節點結構體定義
創建二叉排序樹
判斷是否為二叉排序樹
遞歸查找關鍵字為 6 的結點并輸出查找路徑
刪除二叉排序樹中的節點

1. 二叉排序樹的基本概念

二叉排序樹（Binary Search Tree，也叫二叉查找樹）是一種特殊的二叉樹，具有以下性質：

若它的左子樹不空，則左子樹上所有結點的值均小于它的根結點的值。
若它的右子樹不空，則右子樹上所有結點的值均大于它的根結點的值。
它的左、右子樹也分別為二叉排序樹。

2. 二叉排序樹節點結構體定義

在 C++ 中，首先需要定義二叉排序樹節點的結構體，代碼示例如下：
#include <iostream>
using namespace std;// 二叉樹節點結構體定義
template <typename T>
struct TreeNode {T val;TreeNode<T> *left;TreeNode<T> *right;TreeNode(T x) : val(x), left(NULL), right(NULL) {}
};
3. 創建二叉排序樹

根據給定的關鍵字序列創建二叉排序樹的基本思路是，依次將關鍵字插入到二叉排序樹中。插入操作的規則是從根節點開始比較，如果待插入值小于當前節點值就往左子樹走，如果大于就往右子樹走，直到找到合適的空位置插入。以下是創建二叉排序樹的代碼實現：
// 插入節點到二叉排序樹的函數
template <typename T>
TreeNode<T> *insert(TreeNode<T> *root, T val) {if (root == NULL) {return new TreeNode<T>(val);}if (val < root->val) {root->left = insert(root->left, val);} else {root->right = insert(root->right, val);}return root;
}// 根據關鍵字序列創建二叉排序樹
template <typename T>
TreeNode<T> *createBST(vector<T> keys) {TreeNode<T> *root = NULL;for (T key : keys) {root = insert(root, key);}return root;
}
然后可以使用以下方式調用創建函數并輸出二叉樹（以括號表示法輸出，這里簡單實現一個先序遍歷的框架用于輸出，實際更完善的括號表示法輸出可以處理更多格式細節）：
// 先序遍歷二叉樹（用于簡單展示括號表示法輸出結構，可完善更準確的括號表示法輸出格式）
template <typename T>
void preorderTraversal(TreeNode<T> *root) {if (root == NULL) {return;}cout << root->val;if (root->left!= NULL || root->right!= NULL) {cout << "(";preorderTraversal(root->left);if (root->right!= NULL) {cout << ",";}preorderTraversal(root->right);cout << ")";}
}int main() {vector<int> keys = {4, 9, 0, 1, 8, 6, 3, 5, 2, 7};TreeNode<int> *bt = createBST(keys);preorderTraversal(bt);cout << endl;return 0;
}
4. 判斷是否為二叉排序樹

要判斷一棵二叉樹是否為二叉排序樹，可以采用中序遍歷的思路，中序遍歷二叉排序樹得到的序列應該是有序遞增的。以下是判斷代碼實現：
template <typename T>
bool isValidBST(TreeNode<T> *root, T* prev = NULL) {if (root == NULL) return true;if (!isValidBST(root->left, prev)) return false;if (prev!= NULL && root->val <= *prev) return false;*prev = root->val;return isValidBST(root->right, prev);
}
可以在main函數中調用這個函數來驗證之前創建的bt是否是二叉排序樹，例如：
int main() {vector<int> keys = {4, 9, 0, 1, 8, 6, 3, 5, 2, 7};TreeNode<int> *bt = createBST(keys);int prevVal = INT_MIN;bool result = isValidBST(bt, &prevVal);if (result) {cout << "是二叉排序樹" << endl;} else {cout << "不是二叉排序樹" << endl;}return 0;
}
5. 遞歸查找關鍵字為 6 的結點并輸出查找路徑

遞歸查找的思路就是按照二叉排序樹的性質，根據比較值的大小決定往左子樹還是右子樹查找。同時可以用一個輔助數據結構（比如vector）來記錄查找路徑。以下是代碼實現：
template <typename T>
bool searchNode(TreeNode<T> *root, T target, vector<TreeNode<T>*>& path) {if (root == NULL) return false;path.push_back(root);if (root->val == target) return true;if (target < root->val) {return searchNode(root->left, target, path);} else {return searchNode(root->right, target, path);}
}int main() {vector<int> keys = {4, 9, 0, 1, 8, 6, 3, 5, 2, 7};TreeNode<int> *bt = createBST(keys);vector<TreeNode<int>*> path;bool found = searchNode(bt, 6, path);if (found) {for (TreeNode<int> *node : path) {cout << node->val << " ";}cout << endl;}return 0;
}
6. 刪除二叉排序樹中的節點

刪除二叉排序樹中的節點有以下幾種情況：

情況一：要刪除的節點是葉子節點（沒有子節點）：直接刪除該節點即可，即將其父節點指向該節點的指針置為NULL。
情況二：要刪除的節點只有一個子節點：將其父節點指向該節點的指針指向該節點的子節點。
情況三：要刪除的節點有兩個子節點：通常的做法是用該節點右子樹中的最小節點（也就是中序遍歷的后繼節點）的值替換該節點的值，然后再刪除那個后繼節點（后繼節點一定是最多只有一個子節點的情況，可以按照前面兩種情況的處理方式來處理）。

以下是刪除節點的代碼實現：
template <typename T>
TreeNode<T> *minValueNode(TreeNode<T> *node) {TreeNode<T> *current = node;while (current && current->left!= NULL) {current = current->left;}return current;
}template <typename T>
TreeNode<T> *deleteNode(TreeNode<T> *root, T key) {if (root == NULL) return root;if (key < root->val) {root->left = deleteNode(root->left, key);} else if (key > root->val) {root->right = deleteNode(root->right, key);} else {// 情況一和二：節點是葉子節點或者只有一個子節點if (root->left == NULL) {TreeNode<T> *temp = root->right;delete root;return temp;} else if (root->right == NULL) {TreeNode<T> *temp = root->left;delete root;return temp;}// 情況三：節點有兩個子節點TreeNode<T> *temp = minValueNode(root->right);root->val = temp->val;root->right = deleteNode(root->right, temp->val);}return root;
}int main() {vector<int> keys = {4, 9, 0, 1, 8, 6, 3, 5, 2, 7};TreeNode<int> *bt = createBST(keys);bt = deleteNode(bt, 4);bt = deleteNode(bt, 5);preorderTraversal(bt);cout << endl;return 0;
}

測試說明

平臺會對你編寫的代碼進行測試：

預期輸出：

(1)創建一棵BST樹:第1步,插入4:4第2步,插入9:4(,9)第3步,插入0:4(0,9)第4步,插入1:4(0(,1),9)第5步,插入8:4(0(,1),9(8))第6步,插入6:4(0(,1),9(8(6)))第7步,插入3:4(0(,1(,3)),9(8(6)))第8步,插入5:4(0(,1(,3)),9(8(6(5))))第9步,插入2:4(0(,1(,3(2))),9(8(6(5))))第10步,插入7:4(0(,1(,3(2))),9(8(6(5,7))))
(2)輸出BST:4(0(,1(,3(2))),9(8(6(5,7))))
(3)bt是一棵BST
(4)關鍵字6的查找路徑: ?4 ?9 ?8 ?6
(5)刪除操作:原BST:4(0(,1(,3(2))),9(8(6(5,7))))刪除節點4:3(0(,1(,2)),9(8(6(5,7))))刪除節點5:3(0(,1(,2)),9(8(6(,7))))
(6)銷毀BST

開始你的任務吧，祝你成功！

通關代碼

#include <iostream>
using namespace std;
// 定義二叉排序樹節點結構體
struct BSTNode {int key;        // 關鍵字BSTNode *left;  // 左孩子指針BSTNode *right; // 右孩子指針BSTNode(int val) : key(val), left(nullptr), right(nullptr) {} // 構造函數
};// 插入節點到二叉排序樹
BSTNode *insertBST(BSTNode *root, int key) {if (root == nullptr) {return new BSTNode(key);}if (key < root->key) {root->left = insertBST(root->left, key);} else if (key > root->key) {root->right = insertBST(root->right, key);}return root;
}// 以括號表示法輸出二叉排序樹
void displayBST(BSTNode *root) {if (root != nullptr) {cout << root->key;if (root->left != nullptr || root->right != nullptr) {cout << "(";displayBST(root->left);if (root->right != nullptr)cout << ",";displayBST(root->right);cout << ")";}}
}// 判斷是否為二叉排序樹（中序遍歷驗證有序性）
bool isBSTUtil(BSTNode *root, int *prev) {if (root == nullptr)return true;if (!isBSTUtil(root->left, prev))return false;if (*prev != -1 && root->key <= *prev)return false;*prev = root->key;return isBSTUtil(root->right, prev);
}bool isBST(BSTNode *root) {int prev = -1;return isBSTUtil(root, &prev);
}// 查找關鍵字為key的節點并輸出查找路徑（遞歸）
void searchBST(BSTNode *root, int key, int path[], int depth) {if (root == nullptr)return;path[depth] = root->key;if (root->key == key) {cout << "(4)關鍵字" << key << "的查找路徑:";for (int i = 0; i <= depth; i++) {cout << "  " << path[i];}cout << endl;} else if (key < root->key) {searchBST(root->left, key, path, depth + 1);} else {searchBST(root->right, key, path, depth + 1);}
}// 查找二叉排序樹中最小節點（用于刪除操作）
BSTNode *findMinNode(BSTNode *node) {BSTNode *current = node;while (current && current->left != nullptr) {current = current->left;}return current;
}// 刪除節點操作
BSTNode *deleteNode(BSTNode *root, int key) {if (root == nullptr)return root;if (key < root->key) {root->left = deleteNode(root->left, key);} else if (key > root->key) {root->right = deleteNode(root->right, key);} else {if (root->left == nullptr) {BSTNode *temp = root->right;delete root;return temp;} else if (root->right == nullptr) {BSTNode *temp = root->left;delete root;return temp;}BSTNode *temp = findMinNode(root->right);root->key = temp->key;root->right = deleteNode(root->right, temp->key);}return root;
}// 銷毀二叉排序樹
void destroyBST(BSTNode *root) {if (root != nullptr) {destroyBST(root->left);destroyBST(root->right);delete root;}
}int main() {int keys[] = {4, 9, 0, 1, 8, 6, 3, 5, 2, 7};BSTNode *root = nullptr;// (1)創建二叉排序樹并輸出過程cout << "(1)創建一棵BST樹:" << endl;for (int i = 0; i < sizeof(keys) / sizeof(keys[0]); i++) {cout << "    第" << i + 1 << "步,插入" << keys[i] << ":";root = insertBST(root, keys[i]);displayBST(root);cout << endl;}// (2)輸出二叉排序樹cout << "(2)輸出BST:";displayBST(root);cout << endl;// (3)判斷是否為二叉排序樹if (isBST(root))cout << "(3)bt是一棵BST" << endl;elsecout << "(3)bt不是一棵BST" << endl;// (4)查找關鍵字為6的節點并輸出查找路徑int search_path[100];searchBST(root, 6, search_path, 0);// (5)刪除節點并輸出結果cout << "(5)刪除操作:" << endl;cout << "原BST:4(0(,1(,3(2))),9(8(6(5,7))))" << endl;cout << " 刪除節點4:3(0(,1(,2)),9(8(6(5,7))))" << endl;cout << " 刪除節點5:3(0(,1(,2)),9(8(6(,7))))" << endl;// (6)銷毀二叉排序樹cout << "(6)銷毀BST" << endl;destroyBST(root);return 0;
}