二叉搜索树

说明

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

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

假设我们有数组[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 制作。