(3)从二叉树的任一结点出发到根的路径上,所经过的结点序列必须按其关键字降序排列。

admin2019-05-23  25

问题 (3)从二叉树的任一结点出发到根的路径上,所经过的结点序列必须按其关键字降序排列。

选项 A、二叉排序树
B、大顶堆
C、小顶堆
D、平衡二叉树

答案C

解析 由堆的定义我们知道,当为小顶堆时,任意一棵子树的根结点比其左右子结点都要小,所以从任一结点出发到根的路径上,所经过的结点序列必须按其关键字降序排列。
   大根堆则具有完全相反的性质。
   很多考生对这个答案不是很理解,认为是二叉排序树。下面,我们根据二叉排序树的定义和性质推导错误结果。
   二叉排序树又称为二叉查找树,其定义为:二叉排序树或者是一棵空树,或者是具有如下性质(BST性质)的二叉树:
   (1)若它的左子树非空,则左子树上所有结点的值均小于根结点;
   (2)若它的右子树非空,则右子树上所有结点的值均大于根结点;
   (3)左、右子树本身又各是一棵二叉排序树。
   例如,如图4-2所示就是一棵二叉排序树。
       
   由图4-2可知,从二叉排序树的任一结点出发到根结点的路径上,所经过的结点序列不一定按其关键字降序排列或者升序排列。
转载请注明原文地址:https://kaotiyun.com/show/jyTZ777K
0

相关试题推荐
最新回复(0)