我之前的一篇学术课程中有以下文字关于二阶树（不是BST）的顺序遍历（它们也称之为pancaking）：
顺序树遍历
在树的外面画一条线。从根的左侧开始，绕过树的外部，最后到根的右侧。尽可能靠近树，但不要越过树。 （想想树 - 它的分支和节点 - 作为一个坚固的障碍。）节点的顺序是这条线在它们下面经过的顺序。如果您不确定何时“在节点下面”，请记住“左侧”节点始终位于第一位。
这是使用的示例（从下面略微不同的树）
但是，当我在谷歌搜索时，我得到一个相互矛盾的定义。例如wikipedia example：
顺序遍历序列：A，B，C，D，E，F，G，H，I（左子节点，根节点，右节点）
但根据（我的理解）定义＃1，这应该是
A，B，D，C，E，F，G，I，H
任何人都可以澄清哪个定义是正确的？它们可能都描述了不同的遍历方法，但碰巧使用相同的名称。我很难相信同行评审的学术文本是错误的，但不能确定。
在我对绘图的不良尝试中，这是显示如何挑选它们的顺序。
几乎选择正在绘制的线上方的节点。
嘿，根据我在维基中提到的是正确的，顺序遍历的顺序是左右根。
直到A，B，C，D，E，F我认为你已经理解了。现在在根F之后，下一个节点是G，它不具有左节点而是具有右节点，因此根据规则（左 - 右 - 右）它的空-g-right。现在我是G的正确节点，但我有一个左节点，因此遍历将是GHI。这是对的。
希望这可以帮助。
对于内联树遍历，您必须记住遍历的顺序是左节点右侧。对于您遇到冲突的上图，在读取左侧任何叶子（子）节点之前读取父节点时会发生错误。
正确的遍历将是：尽可能离开叶子节点（A），返回父节点（B），向右移动，但由于D左边有一个孩子，你再次向下移动（C），备份到C的父母（D），到D的右边的孩子（E），反向回到根（F），移到右边的叶子（G），移动到G的叶子但是因为它有一个左叶子节点移动到那里（H） ，回到父母（I）。
当我将它列在括号中时，上面的遍历读取节点。
包数据结构;
公共类Binary Tree Traversal {
public static Node<Integer> node;
public static Node<Integer> sortedArrayToBST(int arr[], int start, int end) {
if (start > end)
return null;
int mid = start + (end - start) / 2;
Node<Integer> node = new Node<Integer>();
node.setValue(arr[mid]);
node.left = sortedArrayToBST(arr, start, mid - 1);
node.right = sortedArrayToBST(arr, mid + 1, end);
return node;
}
public static void main(String[] args) {
int[] test = new int[] { 1, 2, 3, 4, 5, 6, 7 };
Node<Integer> node = sortedArrayToBST(test, 0, test.length - 1);
System.out.println("preOrderTraversal >> ");
preOrderTraversal(node);
System.out.println("");
System.out.println("inOrderTraversal >> ");
inOrderTraversal(node);
System.out.println("");
System.out.println("postOrderTraversal >> ");
postOrderTraversal(node);
}
public static void preOrderTraversal(Node<Integer> node) {
if (node != null) {
System.out.print(" " + node.toString());
preOrderTraversal(node.left);
preOrderTraversal(node.right);
}
}
public static void inOrderTraversal(Node<Integer> node) {
if (node != null) {
inOrderTraversal(node.left);
System.out.print(" " + node.toString());
inOrderTraversal(node.right);
}
}
public static void postOrderTraversal(Node<Integer> node) {
if (node != null) {
postOrderTraversal(node.left);
postOrderTraversal(node.right);
System.out.print(" " + node.toString());
}
}
}
包数据结构;
公共类Node {
E value = null;
Node<E> left;
Node<E> right;
public E getValue() {
return value;
}
public void setValue(E value) {
this.value = value;
}
public Node<E> getLeft() {
return left;
}
public void setLeft(Node<E> left) {
this.left = left;
}
public Node<E> getRight() {
return right;
}
public void setRight(Node<E> right) {
this.right = right;
}
@Override
public String toString() {
return " " +value;
}
}
重新排序>> 2 2 1 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5
void
inorder (NODE root)
{
if (root != NULL)
{
inorder (root->llink);
printf ("%d\t", root->info);
inorder (root->rlink);
}
}
这是递归定义有序遍历的最简单方法，只需在main函数中调用此函数即可获得给定二叉树的有序遍历。
对于预订是正确的，nt是为了有序
忘记定义，只需应用算法就容易多了：
void inOrderPrint(Node root)
{
if (root.left != null) inOrderPrint(root.left);
print(root.name);
if (root.right != null) inOrderPrint(root.right);
}
这只是三行。重新排列订单前后的订单。
如果仔细阅读，您会看到第一个“定义”表示从根的左侧开始，节点的顺序由您在其下面传递时确定。所以B不是第一个节点，因为你在前往A的路上从左边传递，然后在A下首先通过，之后你上升并通过B。因此，似乎两个定义都给出了相同的结果。
我个人发现this lecture非常有帮助。
两种定义都给出了相同的结果。不要被第一个例子中的字母所迷惑 - 看看路径上的数字。第二个例子确实使用字母来表示路径 - 也许这就是让你失望的东西。
例如，在您的示例顺序中显示您如何使用第一个树的算法遍历第二个树，您在“B”之后放置“D”，但您不应该因为仍然有一个左手子节点D可用（这就是为什么第一项说“这条线在它们下面经过的顺序”。
这可能是迟到的，但它可能对以后的任何人都有用..你只需要不要忽略虚节点或空节点，例如节点G有一个左空节点。考虑到这个空节点将使每个事情都好。
正确的遍历将是：尽可能远离叶节点（不是根节点）
F是root还是left，我不确定
我认为第一个具有a根的二叉树是一个没有正确构造的二叉树。
尝试实现，以便树的所有左侧都小于根，并且树的所有右侧都大于或等于根。
但根据（我的理解）定义＃1，这应该是
A, B, D, C, E, F, G, I, H
不幸的是，你的理解是错误的。
每当到达节点时，必须先下降到可用的左节点，然后再查看当前节点，然后查看可用的右节点。在C之前选择D时，您没有先下降到左侧节点。