问题
单项选择题 案例分析题
对于二叉查找树（BinarySearchTree），若其左子树非空，则左予树上所有节点的值均小于根节点的值；若其右子树非空，则右子树上所有节点的值均大于根节点的值；左、右子树本身就是两棵二叉查找树。因此，对任意一棵二叉查找树进行（1）遍历可以得到一个节点元素的递增序列。在具有n个节点的二叉查找树上进行查找运算，最坏情况下的算法复杂度为（2）。
空白（2）处应选择（）
A.O（n2）
B.O（nlog2n）
C.O（log2n）
D.O（n）
答案
参考答案：D
解析：参考排序二叉树的性质可知，第1小题的答案应该是中序。对于第2小题，在具有n个节点的二叉树上进行查找运算时，最坏的情况就是单支树的情况，有n个节点，需要比较n次，所以时间复杂度为O（n）。