国家开放大学

设有查找表{5，14，2，6，18，7，4，16，3}，依次取表中数据，构造一棵二叉排序树。并说明如何由序列的二叉排序树得到相应序列的排序结果，对上述二叉排序给出中序遍历的结果。

题目
设有查找表{5，14，2，6，18，7，4，16，3}，依次取表中数据，构造一棵二叉排序树。并说明如何由序列的二叉排序树得到相应序列的排序结果，对上述二叉排序给出中序遍历的结果。
如果没有搜索结果，请直接 联系老师 获取答案。
如果没有搜索结果，请直接 联系老师 获取答案。
相似问题和答案

第1题：

对一棵二叉排序树进行中序遍历时，得到结点序列的排序状况是______。


正确答案：从小到大
从小到大 解析：一棵二叉排序数具有如下性质；①若其左子树不为空，则左子树上的所有结点值都小于根结点值；②若右子树不为空，则右子树上的所有结点值均大于根结点的值；③左右子树也分别为二叉排序树。因此对其进行中序遍历得到的结点序列是从小到大排列的。

第2题：

中序遍历二叉排序树可以得到一个有序的序列。()


答案：对
解析：
二叉排序树的左子树一定小于根节点，右子树一定大于根节点，中序遍历的顺序是首先中序遍历左子树，然后访问根节点，最后中序遍历右子树，所以中序遍历二叉排序树可以得到一个有序序列。

第3题：

(1)“一棵二叉树若它的根结点的值大于左子树所有结点的值,小于右子树所有结点的值,则该树一定是二叉排序树”。该说法是否正确,若认为正确,则回答正确,若认为不正确则说明理由?(2)设有查找表{7,16,4,8,20,9,6,18,5},依次取表中数据构造一棵二叉排序树. 对上述二叉树给出后序遍历的结果.


参考答案：

第4题：

设有一个整数序列{50，38，16，82，110，13，64}，依次取出序列中的数，构造一棵二叉排序树。利用上述二叉排序树，为了查找110，经多少次元素间的比较能成功查到？为了查找15，经多少次元素间的比较可知道查找失败？
（1）

（2）三次；四次
略

第5题：

“一棵二叉树若它的根结点的值大于左子树所有结点的值，小于右子树所有结点的值，则该树一定是二叉排序树”。设有查找表{7，16，4，8，20，9，6，18，5}，依次取表中数据构造一棵二叉排序树.对上述二叉树给出后序遍历的结果。
后续遍历 5，6，4，9，8，18，20，16，7

略

第6题：

在一棵二叉排序树中，按【 】遍历得到的节点序列是有序序列。


正确答案：中序
中序 解析：二叉排序树的特点是左子树各节点的值小于树根节点，右子树各节点的值大于等于树根节点的值。中序遍历是“左子树—树根节点—右子树”，因此要得到有序节点序列，应进行中序遍历。

第7题：

给定数列{8，17，5，9，21，10，7，19，6}，依次取序列中的数构造一棵二叉排序树。并对上述二叉树给出中序遍历得到的序列。
（1）

（2）5，6，7，8，9，10，17，18，19，21
略

第8题：

在一棵二叉排序树上实施_______遍历后,其关键字序列是一个有序表()

A、先序

B、中序

C、后序

D、深度


参考答案：B

第9题：

设有一个整数序列d{40，28，6，72，100，3，54}依次取出序列中的数，构造一棵二叉排序树。并对上述二叉排序树，在等概率条件下，求成功查找的平均查找长度。
（1）

（2）ASL=（1×1+2×2+3×3+4）/7=18/7
略

第10题：

设有查找表{5，14，2，6，18，7，4，16，3}，依次取表中数据，构造一棵二叉排序树。并说明如何通过序列的二叉排序树得到相应序列的排序结果，对上述二叉排序给出中序遍历的结果。
（1）

（2）中序遍历
中序2，3，4，5，6，7，14，16，18
略

更多相关问题
相关内容