有序树遍历

Question

有序树遍历

Chr*_*s S 21 binary-tree tree-traversal data-structures

我之前的一篇学术课程中有以下关于二阶树(不是BST)的有序遍历(它们也称之为pancaking)的文本:

有序树遍历

在树的外面画一条线.从根的左侧开始,绕过树的外部,最后到根的右侧.尽可能靠近树,但不要越过树.(想想树 - 它的分支和节点 - 作为一个坚实的障碍.)节点的顺序是这条线在它们下面经过的顺序.如果您不确定何时"在节点下面",请记住"左侧"节点始终位于第一位.

这是使用的示例(从下面略微不同的树)

但是,当我在谷歌搜索时,我得到一个相互矛盾的定义.例如维基百科的例子:

顺序遍历序列:A,B,C,D,E,F,G,H,I(左子节点,根节点,右节点)

但根据(我的理解)定义#1,这应该是

A,B,D,C,E,F,G,I,H

任何人都可以澄清哪个定义是正确的？它们可能都描述了不同的遍历方法,但碰巧使用相同的名称.我很难相信同行评审的学术文本是错误的,但不能确定.

Answer 1

Joh*_*ker 36

在我对绘图的不良尝试中,这是显示如何挑选它们的顺序. 替代文字

几乎选择正在绘制的线上方的节点.

@ForYourOwnGood:正确. (21认同)
克里斯对第一个定义的解读是错误的,特别是"在下面传递".克里斯有BDCE,但你在D.之前通过C.除了A上的红线没有指向下方(而G下的红线是边缘的:-),这个图解释了所有,特别是.与"直接在上面"的评论. (3认同)

Answer 2

And*_*son 26

忘记定义,只需应用算法就容易多了:

void inOrderPrint(Node root)
{
  if (root.left != null) inOrderPrint(root.left);
  print(root.name);
  if (root.right != null) inOrderPrint(root.right);
}

Run Code Online (Sandbox Code Playgroud)

这只是三行.重新排列订单前后的订单.

归档时间：	16 年，7 月前
查看次数：	56325 次
最近记录：	6 年，5 月前