中序的妙处

如果一棵二叉树满足"每个节点：左子树所有值都比它小，右子树所有值都比它大"，它就叫二叉搜索树（BST，Binary Search Tree）。它有个漂亮性质：中序遍历（左→根→右）出来的序列，正好是从小到大排好序的。道理不难——中序保证先访问完所有比根小的（左子树），再访问根，再访问所有比根大的（右子树），递归下去每一层都有序。

void inorder(int u) {              // 输出即为升序
    if (!u) return;
    inorder(l[u]);
    cout << val[u] << ' ';
    inorder(r[u]);
}

由此还能推出：BST 里查一个数，像二分一样每步往左或往右走，平均 $O(\log n)$。用途：判断一棵树是不是 BST，跑一遍中序看是否严格递增即可（$O(n)$）。坑：BST 要求"左子树全部小于根"，不是只比左孩子大就行；如果插入的数据本身有序，BST 会退化成一条链，操作变成 $O(n)$，这也是后来要平衡树的原因。