数据结构与算法分析 8.9分
读书笔记 4.6 树的遍历
knightley

按顺序打印二叉查找树的例程采用的是中序遍历的方法,其总的运行时间是O(N)。关于运行时间的解释参见书上的具体解释。

使用后序遍历可以用来计算树的高度(为了计算一个节点的高度,我们需要知道它的两棵子树的高度),其总的运行时间也是O(N)。

先序遍历可以用来利用节点深度标志每一个节点。

在层序遍历(level-order traversal)中,所有深度为D的节点要在深度D+1的节点之前进行处理。层序遍历与其他类型遍历不同的地方在于它不是递归地实施的;它用到队列,而不是递归所默示的栈。

这里要注意层序遍历与其他几种遍历方式实现上的差异,层序遍历要用到队列。

0
《数据结构与算法分析》的全部笔记 68篇
豆瓣
免费下载 iOS / Android 版客户端