非二叉树的顺序遍历

Question

对于比二叉树更宽的树，术语“中序遍历”是否有明确定义的含义，或者“前序”和“后序”是唯一有意义的DFS类型？我的意思是每个节点具有n>2个孩子。
我猜对于偶数的n，在遍历完n/2个孩子后回到“根”可能意味着这样做，但是是否曾经使用过这种方法？奇数的n呢？

- Baruch

Answer 1

如果你明确将子节点集合划分为左儿子和右儿子，那么中序遍历将仍然被定义得很好。

要了解这一点，要注意中序遍历实际上按照节点展平的顺序枚举节点（或等效地，从左边开始观察树时节点出现的顺序）。

因此，对于一个n叉树，你将首先处理左子节点集，然后是父节点和右子节点集。

例如，考虑以下树： 如果我们将左儿子集定义为从左侧开始的前2个子节点，并将右儿子集定义为最后一个节点，我们将获得以下中序遍历：

14、15、5、16、17、18、6、19、2、20、21、7、8、9、3、10、1、11、12、4、13

选择左儿子和右儿子集的方法取决于所面对的问题。

- axiom

---

以7为根的子树，不应该是20、7、21，而是20、21、7，就像你输入的那样吗？ - ASLLOP

请注意，我们将左子节点定义为“从左侧开始的前两个子节点”（20、21是从左侧开始的前两个子节点）。也许在答案中可以更清晰地表述。 - axiom

你说得对，我只是认为它仅适用于具有两个以上子节点的节点。 - ASLLOP

Answer 2

如果您明确将子节点集分为左子节点和右子节点，中序遍历才会继续被定义清晰。

要理解这一点，请注意中序遍历实际上按照节点的顺序枚举它们出现的顺序，如果我们展开树（或等效地，从左侧开始查看树时节点出现的顺序）。

因此，对于一个n叉树，您将首先处理左子节点集，然后是父节点和右子节点集。

例如，考虑以下树：输入图像描述

如果我们将左子节点集定义为从左侧开始的前2个子节点，并将右子节点集定义为最后一个单独的节点，则将获得以下中序遍历：

14、15、5、16、17、18、6、19、2、20、21、7、8、9、3、10、1、11、12、4、13

选择左子节点和右子节点集的方法取决于手头的问题。

- Sammy Niyitanga foreigner