A-A+

在一棵表示有序集S的二叉搜索树(binary searCh tree)中 任意一条从根到叶结

2022-08-12 15:48:30 问答库 阅读 196 次

问题详情

在一棵表示有序集S的二叉搜索树(binary searCh tree)中,任意一条从根到叶结点的路径将S分为三部分:在该路径左边结点中的元素组成的集合S1;在该路径上的结点中的元素组成的集合S2;在该路径右边结点中的元素组成的集合S3。S=S1∪S2∪S3。若对于任意的a∈S1,b∈S2,C∈S3是否总有a≤b≤C?为什么?


请帮忙给出正确答案和分析,谢谢!

参考答案

正确答案:该结论不成立。对于任一α∈A可在B中找到最近祖先f。a在f的左子树上。对于从厂到根结点路径上所有b∈B}有可能厂在6的右子树上因而a也就在b的右子树上这时a>b因此a<b不成立。同理可以证明b<c不成立。而对于任何a∈Ac∈C均有a<c。
此题考查的知识点是二叉排序树的定义。二叉排序树(BinarySortTrree)又称二叉查找树。它或者是一棵空树,或者是具有下列性质的二叉树:(1)若左子树不空,则左子树上所有结点的值均小于它的根结点的值;(2)若右子树不空,则右子树上所有结点的值均大于它的根结点的值;(3)左、右子树也分别为二叉排序树。

考点:表示