目录

创建二叉搜索树 (Creating a Binary Search Tree)

回到本源——“创建”是什么？

推导与洞察——创建就是重复插入

代码实现

在 BST 中查找 (Searching in a BST)

“查找”的逻辑是什么？

代码实现——迭代与递归

迭代方式 (Iterative Search)

递归方式 (Recursive Search)

---

我们继续按照第一性原理来探讨二叉搜索树（BST）的两个最基础、最核心的操作：创建（Creating） 和 查找（Searching）。

创建二叉搜索树 (Creating a Binary Search Tree)

回到本源——“创建”是什么？

我们先思考一下，“创建一棵树”这个动作的本质是什么？

一棵树不是像数组那样，一次性在内存里“框”出一大块连续空间。它是由一个个独立的节点，通过指针链接而成的动态结构。所以，“创建一棵树”无法一步完成。它必然是一个从无到有、逐步建立的过程。

这个过程通常是这样的：

1. 开始时，我们什么都没有，只有一棵空树。

2. 我们得到第一个数据，把它放进空树里。

3. 我们得到第二个数据，再把它按照规则放进已经有一个节点的树里。

4. 我们得到第三个、第四个……第 n 个数据，依次将它们插入到这棵不断成长的树中。

推导与洞察——创建就是重复插入

我们发现一个关键点：

创建一棵全新的 BST，其本质就是从一棵空树开始，连续执行 insert (插入) 操作。

这个结论非常重要。它告诉我们，我们并不需要一个全新的、名为 create() 的复杂函数。我们只需要利用上一节已经打磨好的 insert() 函数即可。

数据结构：在二叉搜索树中插入元素（Insert in a BST）-CSDN博客

创建流程推导： 假设我们要用一组数据 [15, 8, 20, 3, 12] 来创建一棵 BST。

1. 初始化：定义一个指向树根的指针，并让它指向 NULL，代表这是一棵空树。

Node* root = NULL;

2. 处理第一个元素 15：调用 insert(root, 15)。

• insert 函数发现 root 是 NULL。

• 它会创建一个新节点 Node(15) 并返回其地址。

• 我们需要用 root 来接收这个地址：root = insert(root, 15);

• 现在的树：

   15

3. 处理第二个元素 8：调用 insert(root, 8)。

• insert 函数从 root (15) 开始。

• 8 < 15，向左递归，发现 15->left 是 NULL。

• 创建新节点 Node(8) 并将其链接到 15->left。

• 现在的树：

   15
  /
 8

4. 处理第三个元素 20：调用 insert(root, 20)。

• 20 > 15，向右递归，将 Node(20) 链接到 15->right。

5. 重复此过程... 直到所有数据都通过 insert 函数找到了它们在树中的唯一合法位置。

最终，我们就“创建”了我们想要的那棵树。

---

代码实现

基于以上推导，创建树的代码就非常直观了。我们只需要一个循环，在循环里不断调用 insert 函数。

#include <iostream>
#include <cstddef> // for NULL

// --- 我们需要把之前定义的 Node 结构体和 insert 函数放在这里 ---
struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int value) {
        data = value;
        left = right = NULL;
    }
};

Node* insert(Node* root, int value) {
    if (root == NULL) {
        return new Node(value);
    }
    if (value < root->data) {
        root->left = insert(root->left, value);
    } else if (value > root->data) {
        root->right = insert(root->right, value);
    }
    return root;
}
// ----------------------------------------------------------------

// 为了验证树是否创建成功，我们也把中序遍历函数拿过来
void inorderTraversal(Node* root) {
    if (root == NULL) return;
    inorderTraversal(root->left);
    std::cout << root->data << " ";
    inorderTraversal(root->right);
}

int main() {
    Node* root = NULL; // 1. 从一棵空树开始
    int data[] = {15, 8, 20, 3, 12, 18, 25};
    int n = sizeof(data) / sizeof(data[0]);

    std::cout << "开始创建 BST..." << std::endl;
    // 2. 遍历数组，依次将每个元素插入树中
    for (int i = 0; i < n; ++i) {
        std::cout << "插入: " << data[i] << std::endl;
        root = insert(root, data[i]);
    }
    std::cout << "BST 创建完毕!" << std::endl;

    // 3. 验证创建结果
    std::cout << "中序遍历结果 (应该是有序的): ";
    inorderTraversal(root);
    std::cout << std::endl;

    return 0;
}

---

在 BST 中查找 (Searching in a BST)

“查找”的逻辑是什么？

我们为什么要用 BST？初心就是为了快速查找。它的速度源于它“左小右大”的结构。这个结构就是我们查找时的唯一路标。

假设我们要在这棵树里查找数字 12：

      15
     /  \
    8    20
   / \   / \
  3  12 18  25

从根节点 15 开始。

• 我们要找 12。12 < 15。

• 根据“左小右大”的原则，如果 12 存在，它必然在 15 的左子树。我们绝不需要看右子树一眼。问题规模缩小了一半。

移动到 15 的左孩子 8。

• 我们要找 12。12 > 8。

• 根据原则，如果 12 存在，它必然在 8 的右子树。

移动到 8 的右孩子 12。

• 我们要找 12。当前节点的值就是 12！

• 找到了！ 查找成功。

如果我们要找 10 呢？

1. 从 15 出发，向左到 8。

2. 从 8 出发，向右到 12。

3. 从 12 出发，10 < 12，应该向左。但是 12 的左孩子是 NULL。

4. 我们走到了一个“死胡同”。这意味着，10 在这棵树里不存在。因为如果它存在，必然就在这个位置，但这里是空的。

 查找过程就是一个利用 BST 性质，不断缩小范围的线性路径。要么找到目标，要么走到 NULL。

---

代码实现——迭代与递归

这个查找逻辑可以用两种非常经典的方式实现：迭代（循环）和递归。

迭代方式 (Iterative Search)

迭代方式就是用一个循环来模拟我们手动“往下走”的过程。

函数签名和循环框架

我们需要一个指针，current，从 root 开始，不断移动。循环的条件就是 current 还没有走到 NULL。

/*
 * 功能：在以 root 为根的树中查找 key
 * 返回值：如果找到，返回指向该节点的指针；否则，返回 NULL
 */
Node* searchIterative(Node* root, int key) {
    Node* current = root; // 从根节点开始
    
    // 只要还没走到死胡同，就继续查找
    while (current != NULL) {
        // ... 比较和移动的逻辑 ...
    }
    
    // 如果循环结束了 (current 变成了 NULL)，说明没找到
    return NULL;
}

填充循环内的逻辑

在循环内部，就是我们推导出的比较和移动的逻辑。

Node* searchIterative(Node* root, int key) {
    Node* current = root;
    while (current != NULL) {
        // 情况1: 找到了！
        if (key == current->data) {
            return current; // 立即返回找到的节点指针
        }
        // 情况2: key 太小，往左走
        else if (key < current->data) {
            current = current->left;
        }
        // 情况3: key太大，往右走
        else { // key > current->data
            current = current->right;
        }
    }
    return NULL; // 循环正常结束，说明没找到
}

这段代码非常直观，完美地模拟了查找过程。

递归方式 (Recursive Search)

递归方式把“在当前子树查找”这个问题，分解为“在更小的左/右子树查找”的子问题。

函数签名和基本情况 (Base Case)

递归必须有终点。查找的终点有两个：

1. 走到了 NULL（死胡同），说明没找到。

2. 当前节点的值就是要找的 key，说明找到了。

Node* searchRecursive(Node* root, int key) {
    // 基本情况1: 走到死胡同了，或者树本身就是空的
    if (root == NULL) {
        return NULL;
    }
    // 基本情况2: 找到了！
    if (key == root->data) {
        return root;
    }

    // ... 递归步骤待实现 ...
}

实现递归步骤

如果基本情况不满足，我们就需要决定去左边还是右边继续查找。

Node* searchRecursive(Node* root, int key) {
    if (root == NULL || root->data == key) {
        return root; // 将两个基本情况合并，更简洁
    }

    // 递归步骤：
    if (key < root->data) {
        // 问题转化为：在左子树中查找 key
        // 并且，左子树的查找结果，就是我们当前函数的最终结果
        return searchRecursive(root->left, key);
    } else { // key > root->data
        // 问题转化为：在右子树中查找 key
        return searchRecursive(root->right, key);
    }
}

递归代码非常简洁，它把“移动指针”这个动作，变成了“用子树作为新参数发起一个新调用”。

使用示例： 我们可以在 main 函数里加上查找的调用。

int main() {
    // ... (创建树的代码) ...
    
    int key_to_find = 12;
    std::cout << "查找 " << key_to_find << " (迭代方式)..." << std::endl;
    Node* result1 = searchIterative(root, key_to_find);
    if (result1 != NULL) {
        std::cout << "找到了！节点值为: " << result1->data << std::endl;
    } else {
        std::cout << "未找到。" << std::endl;
    }

    int key_to_find2 = 10;
    std::cout << "查找 " << key_to_find2 << " (递归方式)..." << std::endl;
    Node* result2 = searchRecursive(root, key_to_find2);
    if (result2 != NULL) {
        std::cout << "找到了！节点值为: " << result2->data << std::endl;
    } else {
        std::cout << "未找到。" << std::endl;
    }
    
    return 0;
}