3.2.22 #

解答 #

这里的前驱和后继指的是二叉树中序遍历序列里结点的前驱和后继。

由于二叉搜索树的性质，它的中序遍历序列是递增有序的。

因此一个结点如果有左子树，要么前驱就是左子树中最大的结点（最右侧）；

同理结点如果有右子树，要么后继就是右子树中最小的结点（最左侧）。

于是结点的前驱不会有右子节点，后继不会有左子节点，得证。