问答题
用关键字1，2，3，4的四个结点(1)能构造出几种不同的二叉排序树?其中(2)最优查找树有几种?(3)AVL树有几种?(4)完全二叉树有几种?试画出这些二叉排序树。【北京工业大学1997二、3(5分)】
【正确答案】正确答案：(1)本题的实质是给定中序序列1、2、3、4，有几种不同的二叉排序树，即该中序序列相当于多少不同的前序序列，这是树的计数问题。设中序序列中元素数为n，则二又数的数目为1／(n+1)C
2n
n
，这里n=4，故有14种。图示如下：
【答案解析】