Binary search tree, BST
对于树中的每个结点：它的左子结点的值 该结点的值，它的右子结点的值 该结点的值
(b) (e) (f) 不是 BST
不要仅关注子节点和它父亲的大小关系，也要考虑祖先（可能根本没法进入某个分支）
树的遍历
Tree walk，
先序遍历
Pre-order traversal
递归本身就是在压栈（先进后出），return 相当于返回上一级 🤯
根 左 右
中序遍历
In-order Traversal
左 根 右
遍历结果即是树的节点从小到达排列
后序遍历
Post-order traversal
左 右 根
层序遍历
Level-order Traversal
结点的插入
on a tree of height
结点的查找
Querying: run in time on a tree of height , since the sequence of nodes encountered forms a simple path downward from the root.
Both TREE-MINIMUM and TREE-MAXIMUM run in time on a tree of height since, as in TREE-SEARCH, the sequence of nodes encountered forms a simple path downward from the root.
前驱节点
Predecessor：节点值小于该节点值并且值最大的节点（左树的最右
后继节点
Successor：节点值大于该节点值并且值最小的节点（右树的最左
（即中序遍历中某节点的下一个节点）
- 若一个节点有右子树，那么后继节点就是该节点的右子树的最左叶节点
- 若一个节点没有右子树，那么判断该节点和其父节点的关系
- 若该节点是其父节点的左子节点，那么该节点的后继结点即为其父节点
- 若该节点是其父节点的右子节点，那么需要沿着其父亲节点向树的顶端寻找，直到找到一个节点 （ 是其父节点 的左节点），那么 就是该节点的后继节点
结点的删除
on a tree of height
- 如果要删除的节点没有子节点，直接删除该节点即可
- 如果要删除的节点有一个子节点，将该子节点移动到要删除的节点的位置
- 如果要删除的节点有两个子节点，找到该节点的前驱或后继节点，将该节点的值复制到要删除的节点，然后进行删除操作。