binary-search-tree - 关于插入空二叉搜索树的试题

Question

我无法解释有关将元素插入二叉搜索树的某个问题。我熟悉前序、后序和中序遍历，但我不熟悉以下问题:

Suppose that we insert the elements 3, 5, 6, 1, 2, 4, 7 in that order into an initially empty binary search tree.

如果我只得到一组按该顺序插入的数字，我应该如何将其变成二叉搜索树？ 3 会是根吗？我会自己平衡其他数字到正确的子树吗？在那种情况下不会有很多解释吗？是否遵循某种约定？

谢谢。

Answer 1

向树中添加项目时，不会对现有树重新排序。新项目仅添加到叶节点。这意味着当您第一次添加 3 时，3 将是结果的根节点。当您添加 5 时，它将位于 3 的右侧，依此类推。这将产生以下树:

   3
 /   \
1     5
 \   / \
  2 4   6
         \
          7