data-structures - 中序树遍历的问题

Question

我在维基百科找到了这张图片：

根据图片下方的文字，顺序为：A、B、C、D、E、F、G、H、I

我理解顺序AF，但我不理解的是最后三个节点的顺序。不应该是H，I，G吗？我以为您应该在第二次相遇时列出内部节点并在第一次相遇时离开？

编辑：如果图片中的树是普通树而不是二叉树，我的顺序是否正确？（这样 G 将只有一个节点，而不是右节点和空左节点。）

Answer 1

不幸的是，维基百科是对的！

详细算法

inorder_traversal(node)
{
    if(node!=NULL)
       {
           inorder_traversas(node->left);                          
           print(node->data);         //you overlooked this statement on reaching G
           inorder_traversal(node->right);              
       }
}

您在哪里错过了重点/走错了路？

在从 F 到达 G 时，您尝试进入 G 的左孩子，它是 NULL（简而言之inorder_traversal(node->left)，由于算法已经检查并且 G 的左孩子为 NULL，因此语句失败if(node!=NULL) ，所以之后它再次返回 G，之后您忽略了 将在那里打印 G的 print语句- 在忽略该 print 语句后，您跳转到下一个检查 node->right 是否为 NULL 的语句 - 您发现它不为空（将您带到 I）。然后您没有直接打印I并检查它的左孩子。因为左孩子H在那里，所以你打印了它然后你返回给I - 父母，它的右孩子是空的。因此维基百科是正确的。

测试中序遍历的提示 ：制作一个接受整数（或一般数字）作为输入数据的二叉树，当您以中序方式遍历时，数字将按升序打印。

Answer 2

维基百科提到的答案是正确的。你说你了解 AF，所以我会从 G 那里得到。

有序遍历遵循序列：左-父-右。所以当遍历F，算法走到F的右孩子时，首先遇到G，然后尝试定位G的左孩子。由于G的左孩子为null，所以什么都不打印，然后去父, 即 G; 所以 G 被打印出来。现在，它转到 G 的右孩子，即 I。现在，它找到 I 的左孩子，即 H 并打印它。然后它返回到我的父级并打印它。然后它遍历到 I 的右侧并发现它为空。现在，由于所有节点都已遍历，算法终止。因此订单是 GHI

Answer 3

中序遍历的工作方式如下：

1- print the left sub tree.
2- print the root.
3- print the right sub tree

在您提供的示例中：

1- the left sub-tree of `G` is empty, so we do not print any thing.
2- we print the node `G`.
3- finally we print the right sub-tree of `G`