§06 树状结构
二叉搜索树
二叉搜索树让每个结点都满足"左子树 ＜ 根 ＜ 右子树"，于是查找、插入、删除都能沿路径下行。 查找比目标小就向左、大就向右；插入的新结点总是叶子； 删除按三种情况处理——叶子直接摘、单孩子用孩子顶替、双孩子用中序后继替换。
二叉搜索树
伪代码
1
procedure bstSearch(root, x)
2
p = root
3
while p ≠ null 且 p.data ≠ x do
4
if x < p.data then p = p.left // 目标小，去左子树
5
else p = p.right // 目标大，去右子树
6
return p // 命中返回结点，否则为 null
7
end procedure