顺序树遍历:哪个定义正确? [英] Inorder tree traversal: Which definition is correct?

问题描述

我从一段时间前的一门学术课程中获得了以下内容的文字，内容是对二叉树(不是BST)的有序遍历(也称为pancaking):

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

有序遍历树

在 树.从根的左侧开始， 绕到树的外面， 到根的右边. 尽量靠近树木， 但不要越过树. (考虑到 树-它的分支和节点-如 坚固的障碍.) 节点是这条线的顺序 在他们下面经过.如果你是 不确定何时进入地下" 一个节点，请记住到 左"总是第一位.

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 (左子节点，根节点，右节点)

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屋！