二叉搜索树

在有序数组中插入一个数可能需要移动许多元素。二叉搜索树使用相互连接的节点组织数据，为插入和查找提供另一种实现方式；实际效率与树的形状有关。

任务说明

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

需要经常维护有序数据时，数组不一定是最合适的结构。

例如向 [1, 3, 4, 5] 添加 2，若直接追加为 [1, 3, 4, 5, 2]，还要重新排序。也可先腾出位置形成 [1, nil, 3, 4, 5]，再插入 2，但仍需移动许多元素。

二叉搜索树在合适的树形结构下，能更有效地维护这些数据。

树由相连的节点组成。每个节点包含数据，以及 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 制作。