顺序树遍历 [英] In-order tree traversal

问题描述

我有一段时间以前学习过的课程，介绍了一个二进制树（而不是BST）的顺序遍历（也称为薄饼）：

I have the following text from an academic course I took a while ago about in-order traversal (they also call it pancaking) of a binary tree (not BST):

按顺序树遍历

在外面画一条线的
树。从根的左边开始，
并绕着树的外侧，
最终到根的右边。
尽可能靠近树，
但不要越过树。 （想想
树 - 它的分支和节点 - 作为
一个坚实的障碍。）
节点的顺序是这行
在它们之下通过的顺序。如果你是
不确定当你走到
a节点下面时，请记住，到
左边的节点始终是第一个。

Draw a line around the outside of the tree. Start to the left of the root, and go around the outside of the tree, to end up to the right of the root. Stay as close to the tree as possible, but do not cross the tree. (Think of the tree — its branches and nodes — as a solid barrier.) The order of the nodes is the order in which this line passes underneath them. If you are unsure as to when you go "underneath" a node, remember that a node "to the left" always comes first.

这里是使用的示例（与下面略有不同的树）

Here's the example used (slightly different tree from below)

然而，当我在google上进行搜索时，我会得到一个冲突的定义。例如维基百科例子：

However when I do a search on google, I get a conflicting definition. For example the wikipedia example:

顺序遍历顺序：A，B，C，
D，E，F，G，H，I
（leftchild，rootnode ，右结点）

Inorder traversal sequence: A, B, C, D, E, F, G, H, I (leftchild,rootnode,right node)

但是根据（我的理解）定义1，这应该是

But according to (my understanding of) definition #1, this should be

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

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

任何人都可以澄清哪个定义是正确的？他们可能会描述不同的遍历方法，但恰好是使用相同的名称。我很难相信同行评审的学术文本是错误的，但不能确定。

Can anyone clarify which definition is correct? They might be both describing different traversal methods, but happen to be using the same name. I'm having trouble believing the peer-reviewed academic text is wrong, but can't be certain.

推荐答案

在我的坏尝试在这里的绘图是显示如何选择它的顺序。

In my bad attempt at the drawing here's the order that shows how they should be picked.

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

pretty much pick the node that is directly above the line being drawn,.

这篇关于顺序树遍历的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！