黑马程序员技术交流社区

标题: 关于二叉树 [打印本页]

作者: 张文星 时间: 2013-3-15 12:58
标题: 关于二叉树
本帖最后由张文星于 2013-3-15 23:20 编辑

请问在二叉树遍历的时候才用先序法、中序法、后序法哪种效率更高，或者是都一样，又或者是要分情况？

作者: 彭颖 时间: 2013-3-15 14:55
如果数据是按照链表来组织，访问数据元素的最坏情形耗时0（n），而对于二杈树来说，访问数据元素的最坏情形耗时0（logn）。应为对于输入的n个数据元素，创建二杈树的同时，也已经对数据进行了有序排列（左子树节点值小于根节点，右子树节点值大于根节点），这样就使得搜索数据时可以少遍历log2/n的数据，是分治思想的应用。又因为为输入的n个数据元素创建链表或二杈树的时间复杂度是一样的，所以可以说遍历搜索数据元素时，二叉树结构比链表的效率高。
另外，就是时间效率的高也是通过对空间的额外需求换来的，二叉树结构比链表需要更多的空间来存储。

先序中序和后序都是要看你想怎么去实现这个遍历，是用栈模拟递归，或者是来写指针。不同的顺序实现的难度不一样。

作者: fighting 时间: 2013-3-15 23:21
我感觉这三种遍历算法的复杂度应该是一样的吧，无论是使用递归或是用栈来操作树的节点，但树的深度是一定的啊，
因此效率应该差不多的。
至于楼上说的查找，那自然是排序好的树总比没有排序的树查找起来更方便，尤其像平衡二叉树这样的树。

欢迎光临黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2