在一棵表示有序集S的二叉搜索树(binary search tree)中,任意一条从根到叶结点的路径将S分为3部分:在该路径左边结点中的元素组成的集合S1;在该路径上的结点中的元素组成的集合S2;在该路径右边结点中的元素组成的集合S3。S=S1∪S2∪S3

admin2019-08-01  45

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

选项

答案不是。如下图所示的二叉搜索树: [*] 取从4到12的路径,则S1={1,2,3,7},.S2={4,8,10,12},S3为空集,取S1中的元素7和S2中的 元素4,令a=7,b=4,有a>b。则上述命题不成立。

解析
转载请注明原文地址:https://kaotiyun.com/show/lCCi777K
0

最新回复(0)