整数如何放置在树结构中？

Question

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

Answer 1

简单回顾一下背景（如果您已经了解，请跳过此部分）：

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

是一种特殊类型的树，其中每个节点最多有两个子节点。二叉树中的所有节点都有一个

值、一个左指针和一个右指针。指针指向左子节点和右子节点（如果存在）。如果它们不存在，则指针不指向任何地方。 二叉搜索树是一种特殊类型的二叉树，其中节点以特殊方式组织：

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

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

二叉搜索树这样组织，可以轻松搜索值。

现在介绍插入算法...

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

NULL
：

3

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

所以要插入号码

     6
   /   \
  4     9
 / \   /
2   5 8

...

从顶部节点开始

3

小于

3
• ，所以向左

• 6

  小于

  3

  ，所以向左

• 4

  大于

  3

  ，所以向右走
• 我们找到了新节点的空白空间，因此将其插入此处

   6
      /\
     4 9
    /\/
   2 5 8
    \
     3
  

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

伪代码：

Insert()