C++ 中的二叉搜尋樹插入
Jinku Hu
2023年10月12日
本文將演示如何用 C++ 實現二叉搜尋樹資料結構的插入功能。
在 C++ 中的二叉搜尋樹中插入新節點
二叉樹一般表示樹結構的子集。它們被稱為二元的，因為在任何給定節點上最多有兩個孩子。在這種情況下，我們討論二叉搜尋樹，其中每個節點都包含一個稱為鍵的資料成員，並且在樹的每一層，給定節點的鍵必須大於其左子樹中的鍵且小於右子樹中的所有鍵子樹。此功能將允許我們在搜尋排序陣列時在樹上使用二分搜尋演算法。
首先，我們需要宣告一個樹節點 struct，它包括兩個指向 left/right 節點的指標和一個鍵。為簡單起見，我們將鍵儲存為 int 值，但可能需要根據問題為節點構建不同的佈局。我們還通過將單個 TreeNode 指標宣告為樹的根，然後呼叫 insertNode 函式來新增新節點來手動構建這棵樹。
為了更好地演示和驗證我們的示例，我們還包括一個函式來查詢具有給定鍵的節點和另一個列印整個樹的內容的函式。後者將幫助我們在程式的每一步輕鬆檢查樹結構。請注意，所有三個函式都使用遞迴，因為樹結構是分治演算法所固有的。
#include <iostream>
#include <vector>
using std::cout;
using std::endl;
using std::string;
using std::vector;
struct TreeNode {
int key;
struct TreeNode *left{};
struct TreeNode *right{};
};
void insertNode(TreeNode *&root, const int k) {
if (root == nullptr) {
root = new TreeNode;
root->key = k;
root->left = nullptr;
root->right = nullptr;
} else {
if (k < root->key)
insertNode(root->left, k);
else
insertNode(root->right, k);
}
}
TreeNode *findNode(TreeNode *root, const int k) {
if (root == nullptr) return nullptr;
if (k == root->key) return root;
if (k < root->key)
return findNode(root->left, k);
else
return findNode(root->right, k);
}
void printTree(TreeNode *n) {
if (n != nullptr) {
printTree(n->left);
cout << n->key << "; ";
printTree(n->right);
}
}
int main() {
std::vector<int> v1{11, 23, 3, 5, 9, 15, 2, 20};
TreeNode *root = nullptr;
for (const auto &item : v1) {
insertNode(root, item);
}
printTree(root);
cout << endl;
std::vector<int> v2{1, 22, 4, 16};
for (const auto &item : v2) {
insertNode(root, item);
}
printTree(root);
cout << endl;
return EXIT_SUCCESS;
}
輸出：
2; 3; 5; 9; 11; 15; 20; 23;
1; 2; 3; 4; 5; 9; 11; 15; 16; 20; 22; 23;
在 main 函式中，我們宣告瞭兩個任意的 int 向量，然後將它們的元素推送到樹中。請注意，我們的 insertNode 函式有兩個引數 - 根節點和一個鍵值。它需要檢查給定的根節點是否有效或只是一個 nullptr，後者表示該函式需要建立根節點內容。
如果根節點已經初始化，那麼函式應該根據鍵值進行處理，鍵值與當前節點的鍵值進行比較。如果傳遞的鍵的值小於給定的鍵，我們應該向前移動到左子樹。否則 - 右子樹。
最終，我們將到達需要儲存鍵的節點，並且中序遍歷將始終列印已排序的鍵值，如程式碼片段所示。
作者： Jinku Hu
