整数如何放置在树结构中？真的很混乱

Question

到目前为止，我知道小值整数放在左轴，大值放在右轴。谁能给个好的解释。谢谢

Answer 1

简单回顾一下背景（如果您已经知道，请跳过）：

一棵树是由边连接的节点集合，不允许有环路。最顶层的节点称为 根节点 。节点可以有零个或多个子节点，这些子节点是从它向下延伸的节点。所有节点都有一个 父节点 从它向上延伸（根是例外，没有父节点）。允许多个父项会产生循环，这在树中是不允许的。

二叉树是一种特殊类型的树，其中每个节点最多有两个子节点。二叉树中的所有节点都有一个值、一个左指针和一个右指针。指针指向左右子节点（如果存在）。如果它们不存在，则指针是 NULL 指针不指向任何地方。

一棵二叉搜索树是一种特殊类型的二叉树，其中节点以特殊方式组织：

给定任何节点，其左子树中的所有节点都将具有较小的值
给定任何节点，其右子树中的所有节点都将具有更大的值

二叉搜索树是这样组织的，以便于搜索值。

现在是插入算法...

假设我们得到了要插入到以下树中的数字 3：

我们需要做的就是从根部开始向下沿着树向下移动，如果我们的新值小于节点值则向左移动，如果我们的新值大于节点值则向右移动。当我们找到一个空的 space 来插入节点时，我们停止。

所以要插入数字 3...

从顶部节点开始
3小于6，向左走
3小于4，向左走
3大于2，所以向右走
我们发现新节点为空 space，因此将其插入此处

Insert()过程可以递归定义。一旦我们决定向左或向右移动，我们就可以只关注当前节点下面的子树而忘记树的其余部分。

在伪代码中：

Insert(Node root, int newValue)
    if (root is empty)
        Node N = new Node
        N.value = newValue
    else if (root.value < newValue)
        Insert(root.left, newValue)
    else if (root.value > newValue)
        Insert(root.left, newValue)

整数如何放置在树结构中？真的很混乱

How does the integers placed inside a tree structure? really confusing

tree

data-structures