A.O(n)B.O(n2)C.O(log2n)D.O(nlog2n)

Question

A．O(n)

B．O(n2)

C．O(log2n)

D．O(nlog2n)

Answer 1

正确答案：A
解析：中序遍历二叉树的过程为：若二叉树非空，则先中序遍历左子树，然后访问根结点，最后中序遍历右子树。根据二叉查找树的定义，显然，对二叉查找树进行中序遍历，得到结点元素的递增序列。在二叉查找树上进行查找的过程为：若二叉查找树非空，将给定值与根结点的关键字值相比较，若相等，则查找成功；若不等，则当根结点的关键字值大于给定值时，到根的左子树中进行查找。否则到根的右子树中进行查找。若找到，则查找过程是走了一条从树根到所找到结点的路径；否则，查找过程终止于一棵空树。因此，在具有n个结点的二叉查找树上进行查找的算法复杂度与树的高度同阶，即最坏情况下的算法复杂度为O(n)。