二叉搜索树

说明

在二叉树中插入和搜索数字。

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

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