binary-search-tree - 插入 BST

Question

我想创建 BST 的可视化，但是我在网上找到的每个示例在仅插入 7 个或更少的值后都会停止。假设我正在执行以下序列：

插入（5），插入（7），插入（9），插入（8），插入（3），插入（2），插入（4），插入（6），插入（10）。

直到插入（6），我最终得到：

我的主要问题是：我从这里去哪里？我是添加到最左边的叶子上还是添加到“最低”的叶子上？

另外：根据维基百科，插入代码是：

void insert(Node* node, int value) {
    if (value < node->key) {
        if (node->leftChild == NULL)
            node->leftChild = new Node(value);
        else
            insert(node->leftChild, value);
    } else {
        if(node->rightChild == NULL)
            node->rightChild = new Node(value);
        else
            insert(node->rightChild, value);
    }
}

但据此，一旦我在 8 并且我得到 insert(3)，它将在 8 的左侧添加 3，因为它将 3 与节点 9 进行比较，看到小于点已经被8，然后以 8 作为比较的节点重新运行插入，并将 3 作为 8 的左子节点。但这只会创建一种列表。

谢谢。

Answer 1

似乎误导您的是，在每次插入时，您必须从根开始（在您的情况下是 5）。因此，让我们使用上面的图表并尝试按照您粘贴的算法插入 3：

3 < 5, we go left and we meet 3
3 == 3, we go right (here it's the same, the code above says "go right") and we meet 4
3 < 4, we go left. Since 4 has no left child, 3 becomes its left child.

尝试使用上面的算法从零开始构建你的树。顺便说一句，您不会找到很多具有 n > 10 个节点的示例，因为它们往往非常长，对读者没有任何好处。