二叉搜索树

说明

在二叉树中插入和查找数字。

当我们需要表示有序数据时，数组并不是一种好的数据结构。

假设我们有数组 [1, 3, 4, 5]，往里面加入 2，它就变成了 [1, 3, 4, 5, 2]。 现在我们又得把整个数组重新排序一遍！ 我们可以改进一下：只需要为新元素腾出空间，即 [1, nil, 3, 4, 5]，然后把新元素放进腾出的那个空间里。 但这样做仍然需要把许多元素向下移动一位。

然而，二叉搜索树处理有序数据的效率要高得多。

二叉搜索树由一系列相互连接的节点组成。 每个节点包含一份数据（例如数字 3）、一个名为 left 的变量和一个名为 right 的变量。 left 和 right 变量指向 nil，或者指向其他节点。 由于这些其他节点下面又连着别的节点，我们说 left 和 right 变量指向的是子树。 左子树中的所有数据都小于或等于当前节点的数据，右子树中的所有数据都大于当前节点的数据。

例如，假设我们有一个包含数据 4 的节点，然后加入数据 2，树就会变成这样：

      4
     /
    2

如果接着加入 6，树就会变成这样：

      4
     / \
    2   6

如果接着加入 3，树就会变成这样。

       4
     /   \
    2     6
     \
      3

如果接着加入 1、5 和 7，树就会变成这样。

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

致谢

这些图片由 habere-et-dispertire 使用 Till Tantau 开发的 PGF/TikZ 制作。