直接在二叉排序树中查找关键字 K 与在中序遍历输出的有序序列中查找关键字 K ，其效率是否相同？输入关键字有序序列来构造一棵二叉排序树，然后对此树进行查找，其效率如何？为什么？

举报纠错

切换

1 个答案

解析：在二叉排序树上查找关键字K，走了一条从根结点至多到叶子的路径，时间复杂度是O(logn)，而在中序遍历输出的序列中查找关键字K，时间复杂度是O（n）。按序输入建立的二叉排序树，蜕变为单枝树，其平均查找长度是（n+1）/2，时间复杂度也是O（n）。图略

还没有评论

切换

撰写答案

扫描后移动端查看本题