Tree 很容易被背坏。你可以背 preorder、inorder、postorder，但仍然不理解每 一种 order 保存了什么结构信息。课程用 binary-tree traversal 和 BST operations，要求我们更细心地读结构。
Binary tree 术语
定义
Binary tree
Binary tree 是每个 node 最多有两个 children 的 tree；存在时会分成 left child 和 right child。
Left-right distinction 是结构的一部分。即使 node set 一样、parent-child 关系看似相近，左右 child 交换后也可能是不同的 binary tree。
Traversal orders
对 root 、left subtree 、right subtree ：
- preorder：先 ，再 ，再 ；
- inorder：先 ，再 ，再 ；
- postorder：先 ，再 ，再 。
这三个不是任意 list，而是保存不同信息。
例题
为什么 inorder alone 不够
Sequence (B, A, C) 可以来自不同 tree。 可以是 root， 在左、 在
右；但其他 shape 也可能有同样 inorder。Inorder alone 记录 left-root-right
次序，未必记录 root hierarchy。
Reconstruction 需要两个 compatible traversals
Tutorial 的标准方法是：
- 用 preorder 或 postorder 找 root；
- 用 inorder 把 nodes 分成 left subtree 和 right subtree；
- 对两边 recursively 重复。
若 keys distinct，preorder plus inorder 足够；postorder plus inorder 也 类似。Preorder plus postorder alone 通常不能唯一决定 binary tree。
Binary search tree
定义
Binary search tree
BST 是一棵 binary tree，所有 keys unique，且每个 node 都满足：left subtree 内所有 key 小于 node key，right subtree 内所有 key 大于 node key。
BST invariant 在每个 node local 地检查，但后果是 global 的。某 node key
为 x 时，整个 left subtree 深处的每个 key 都必须小于 x。
定理
BST 的 inorder traversal 是 sorted
若 binary tree 满足 BST invariant，inorder traversal 会按 increasing order visit keys。
这解释了为什么 BST 题目常常问 inorder successor 或 ranked traversal。
Inorder successor
Inorder successor 是 inorder traversal 中下一个 node。Tutorial 分成两种情况：
- 若 node 有 right subtree，successor 是 right subtree 里的 minimum node；
- 否则，向上找 lowest ancestor，使 current node 位于那个 ancestor 的 left subtree。
第二种情况需要 parent pointer，或者能从 root 重新追踪 search path。
例题
Right-subtree case 为何成立
若 node 有 right subtree，right subtree 里每个 key 都比 node 大。当中最小 的 key 就是下一个更大的 key，所以是 inorder successor。
Deletion and replacement
BST deletion 有三种情况：
- 删 leaf：直接移除；
- 删只有一个 child 的 node：把 parent 接到那个 child；
- 删有两个 children 的 node：用 left subtree maximum 或 right subtree minimum 取代，然后把 replacement 从原位置删掉。
两种 replacement strategy 只要实作小心，都可保留 BST invariant。
快速检查
BST 的 inorder traversal 有什么用？
说出 visited keys 的次序。
解答
答案
快速检查
若 BST node 有 right subtree，它的 inorder successor 在哪里？
想下一个更大的 key。
解答
答案
练习
- 解释 preorder plus inorder 为何可以 reconstruct distinct-key binary tree。
- 列出找 inorder successor 的两种情况。
- 解释用 right-subtree minimum 取代 two-child deleted node 为何保留 BST invariant。
解答