问答题
在一棵表示有序集S的二叉搜索树(binary search tree)中,任意一条从根到叶结点的路径将S分为3部分:在该路径左边结点中的元素组成的集合S1;在该路径上的结点中的元素组成的集合S2;在该路径右边结点中的元素组成的集合S3。S=S1∪S2∪S3。若对于任意的a∈S1,b∈S2,c∈S3是否总有a≤b≤c?为什么?【清华大学2000四(10分)】【武汉大学2000三、3】
【正确答案】正确答案:该结论不成立。证明公式不成立时,只要找出一个反例,就可作出结论。例如,本题中对于任一a∈S1,可在S2中找到a的最近祖先f。a在f的左子树上。对于从f到根结点路径上所有b∈S2,有可能f在b的右子树上,因而a也就在b的右子树上,这时a>b,因此a
【答案解析】