有序二叉树让搜索、排序遍历、插入三者兼得

把一个有序列表存成二叉树（每个节点大于其左子树所有节点、小于其右子树所有节点），能同时高效支持三种看起来不相关的操作：搜索时，从根开始比较目标值和当前节点，比它小就转向左孩子、比它大就转向右孩子，等价于对不断缩小的子树反复做[[递归：把重复当作自身的子任务|二分搜索]]；按顺序打印时，只需要”先递归打印左子树、再打印根、再递归打印右子树”，因为左子树全都更小、右子树全都更大，顺序自然正确；插入新值时，沿着搜索这个值本该在的路径往下走，走到第一个空指针就是它该待的位置——新节点总是可以简单地作为一个新叶子插入，完全不需要挪动其他节点腾地方。发散：这个案例说明了选对数据结构能让原本互相牵制的多个需求同时变得轻松——如果坚持用邻接表存有序列表，插入一个新元素就得移动后面所有元素来腾空位，而换成树形结构后，插入操作反而变成了整个方案里最简单的部分，这正是”数据结构的选择本质上是在为最重要的那个操作让路”的具体例证。