二叉排序树
标签: 数据结构
学习人数: 6214


全屏播放
赞赏支持

前言

数据结构中,线性表分为无序线性表和有序线性表。
无序线性表的数据是杂乱无序的,所以在插入和删除时,没有什么必须遵守的规则,可以插入在数据尾部或者删除在数据尾部。但是在查找的时候,需要遍历整个数据表,导致无序线性表的查找效率低。
有序线性表的数据则相反,查找数据时的时候因为数据是有序的,可以用二分法、插值法、斐波那契查找法来实现。但是,当进行插入和删除操作时,需要维护表中数据的有序性,会耗费大量的时间。
那么,我们希望找到一种数据结构,既可以有较高的插入和删除效率,并且具备较高的查找效率,因此,二叉排序树应运而生。

 

定义
二叉排序树(Binary Sort Tree),又称二叉查找树(Binary Search Tree),也称二叉搜索树。二叉排序树或者是一棵空树,或者是具有下列性质的二叉树:

(1)若左子树不空,则左子树上所有结点的值均小于或等于它的根结点的值;
(2)若右子树不空,则右子树上所有结点的值均大于或等于它的根结点的值;
(3)左、右子树也分别为二叉排序树;

 

构造一棵二叉排序树
...

登录查看完整内容


课后作业

课后习题

 

【2018年真题】已知二叉排序树如下图所示,元素之间应满足的大小关系是()

A. x1 < x2 < x5        B. x1 < x4 < x5        C. x3 < x5 < x4        D. x4 < x3 < x5

参考答案:C

 

【2013年真题】在任意一棵非空二叉排序树T1中,删除某结点v 之后形成二叉排序树T2,再将v插入T2形成二叉排序树T3。下列关于T1与T3的叙述中,正确的是()
I. 若v 是 T1 的叶结点,则 T1 与 T3 不同 
II.若v 是 T1 的叶结点,则 T1 与 T3 相同 
III. 若v 不是 T1 的叶结点,则 T1 与 T3 不同 
IV. 若v 不是 T1 的叶结点,则 T1 与 T3 相同 
A. 仅 I、III         B. 仅 I、IV         C. 仅 II、III         D. 仅 II、IV

参考答案:C
答案解析:在一棵二叉排序树中删除一个结点后再将此结点插入到二叉排序树中,如果删除的结 点是叶子结点,那么在插入结点后,后来的二叉排序树与删除结点之前相同。如果删除的结 点不是叶子结点,那么再插入这个结点后,后来的二叉树可能发生变化,不完全相同。 

 

【2011年真题】对于下列关键字序列,不可能构成某二叉排序树中一条查找路径的序列是()。
A.95,22,91,24,94,71
B.92,20,91,34,88,35 
C.21,89,77,29,36,38 
D.12,25,71,68,33,34

解答:A。选项A中,当查到91后再向24查找,说明这一条路径之后查找的数都要比91小,后面的94就错了。 

 

【2009年真题】下列二叉排序树中,满足平衡二叉树定义的是()。 

参考答案:B
答案解析:考查平衡二叉树的定义。 
根据平衡二叉树的定义有,任意结点的左右子树高度差的绝对值不超过 1。而其余三个答案均可以找到不符合的结点。


登录后发布评论

暂无评论,来抢沙发