3.2.12 #

解答 #

二叉树的大小=左子树的大小+右子树的大小+1

根据上述表达式可以构造出一个递归的 Size() 方法，并删除结点中的 Size 。

Rank() 和 Select() 仍然可以正常工作，但最坏情况下的耗时可能会达到 $O(n)$ 和 $O(n^2 )$。