树形查找
二叉排序树：每个结点的值都大于其左子树任一结点的值而小于其右子树任一结点的值。
查找
function treesrh(k:keytype):pointer;
var q:pointer;
begin
q:=root;
while (q<>nil) and (q^.key<>k) do
if k<q^.key then q:=q^.left
else q:=q^.right;
treesrh:=q;
end;
第1题：
● 对于二叉查找树（Binary Search Tree） ，若其左子树非空，则左子树上所有结点的值均小于根结点的值；若其右子树非空，则右子树上所有结点的值均大于根结点的值；左、右子树本身就是两棵二叉查找树。因此，对任意一棵二叉查找树进行 （61） 遍历可以得到一个结点元素的递增序列。在具有 n 个结点的二叉查找树上进行查找运算，最坏情况下的算法复杂度为 （62） 。
（61）
A. 先序
B. 中序
C. 后序
D. 层序
（62）
A. O(n2
B. O(nlog2n)
C. O(log2n)
D. O(n)
第2题：
从供选择的答案中选出应填入下列叙述中()内的正确答案：
在二叉排序树中，每个结点的关键码值(A)，(B)一棵二叉排序树，即可得到排序序列。同一个结点集合，可用不同的二叉排序树表示，人们把平均检索长度最短的二叉排序树称做最佳二叉排序树，最佳二叉排序树在结构上的特点是(C)。
供选择的答案
A：①比左子树所有结点的关键码值大，比右子树所有结点的关键码值小
②比左子树所有结点的关键码值小，比右子树所有结点的关键码值大
③比左右子树的所有结点的关键码值大
④与左子树所有结点的关键码值和右子树所有结点的关键码值无必然的大小关系
B：①前序遍历 ②中序(对称)遍历
③后序遍历 ④层次遍历
C：①除最下二层可以不满外，其余都是充满的
②除最下一层可以不满外，其余都是充满的
③每个结点的左右子树的高度之差的绝对值不大于1
④最下层的叶子必须在左边
第3题：
A.左、右子树的高度均相同
B.左、右子树高度差的绝对值不超过1
C.左、右子树的结点数均相同
D.左、右子树结点数差的绝对值不超过1
第4题：
一棵二叉树满足下列条件：对任一结点，若存在左、右子树，则其值都小于它的左子树上所有结点的值，而大于右子树上所有结点的值。现采用【 】遍历方式就可以得到这棵二叉树所有结点的递增序列。
A．先根
B．中根
C．后根
D．层次
第5题：
如果二叉树中任何一个结点的值都大于它的左子树上所有结点的值而小于右子树上所有结点的值，要得到各结点值的递增序列，应按下列哪种次序排列结点?
A．先根
B．中根
C．后根
D．层次
第6题：
此题为判断题(对，错)。
第7题：
对于二叉查找树(Binary Search Tree)，若其左子树非空，则左子树上所有结点的值均小于根结点的值；若其右子树非空，则右子树上所有结点的值均大于根结点的值。左、右子树本身就是两棵二叉查找树。因此，对任意一棵二叉查找树进行(61)遍历可以得到一个结点元素的递增序列。在具有n个结点的二叉查找树上进行查找运算，最坏情况下的算法复杂度为(62)。
A．先序
B．中序
C．后序
D．层序
第8题：
●二叉排序树或者是一棵空树，或者是具有如下性质的二叉树：若其左子树非空，则左子树上所有结点的值均小于根结点的值；若其右子树非空，则右子树上所有结点的值均大于根结点的值；其左、右子树本身就是两棵二叉排序树。根据该定义，对一棵非空的二叉排序树进行 （42)遍历，可得到一个结点元素的递增序列
（42）
A. 先序（根、左、右）
B. 中序（左、根、右）
C. 后序（左、右、根）
D. 层序（从树根开始，按层次）
第9题：
下面关于二叉排序树叙述中，正确的是
A．右结点的度大于左结点的度
B．右子树的度大于左子树的度
C．左子树中所有的结点的关键码值都小于该结点的关键码值
D．右子树中所有的结点的关键码值都小于该结点的关键码值
第10题：
“一棵二叉树若它的根结点的值大于左子树所有结点的值，小于右子树所有结点的值，则该树一定是二叉排序树”。设有查找表{7，16，4，8，20，9，6，18，5}，依次取表中数据构造一棵二叉排序树.对上述二叉树给出后序遍历的结果。
后续遍历 5，6，4，9，8，18，20，16，7
略