Question

1.定义与性质

（1）设 x 为二叉查找树中的一个结点，若 y 是 x 左子树中的一个结点，则 key[y] <= key[x]；若 y 是 x 右子树中的一个结点，则 key[x]<=key[y]

（2）二叉查找树上执行的基本操作的时间与树的高度成正比。

2.结构

（1）结点结构：

关键字 key

卫星数据 data

分别指向父、左右孩子的指针 p, left, right

3.在二叉查找树上的操作

查找一个关键字：SEARCH(x, k)

求最小关键字：MINIMUM(x)

求最大关键字：MAXIMUM(x)

求前驱：PREDECESSOR(x)

求后继：SUCCESSOR(x)

插入一个结点：INSERT(T, z)

删除一个结点：DELETE(z)

4.二叉查找树的应用

1.遍历：中序遍历、先序遍历、后序遍历

2.查找：查找包含某个关键字的结点，查找关键字最大或最小的结点、查找某个结点的前驱或后继