非二叉树的有序树遍历 [英] In-order tree traversal for non-binary trees

问题描述

术语中序遍历"对于比二叉树更宽的树是否具有明确定义的含义，或者前"和后"顺序是唯一有意义的 DFS 类型?我的意思是每个节点有 n>2 个孩子.
我猜对于 n 来说，它甚至可能意味着在 n/2 孩子之后进入根"，但这曾经像这样使用过吗?那么奇怪的 n 呢?

Does the term "inorder traversal" have a well-defined meaning for trees wider than binary trees, or are "pre-" and "post-" order the only type of DFS that makes sense? I mean with n>2 children per-node.
I guess for n that is even it might mean going to the 'root' after n/2 children, but is this ever used like this? And what about odd n?

推荐答案

只有当您明确地将孩子集划分为左孩子和右孩子时，中序遍历才会继续被很好地定义.

The inorder traversal will continue to be well defined only if you explicitly partition the children set into left children and right children.

要看到这一点，请注意，如果我们展平树，中序遍历实际上是按照节点出现的顺序枚举节点(或者等效地，如果我们凝视，节点将出现的顺序从左边开始越过树).

To see this, note that the inorder traversal actually enumerates nodes in the order in which they will appear if we flatten the tree (or equivalently, the order in which the nodes will appear if we gaze over the tree starting from left).

因此，对于 n-ary 树，您将首先处理左子集，然后是父集和右子集.

Thus, for an n-ary tree, you will process the left children set first, followed by the parent and the right children set.

例如，考虑以下树:

如果我们将左孩子的集合定义为从左边开始的前 2 个孩子节点，而右孩子的集合是最后一个节点，我们将得到以下中序遍历:

If we define the set of left children to be the first 2 child nodes from the left, and the set of right children as the single last node, we will get the following inorder traversal :

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

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

选择左右子集的方法将取决于手头的问题.

The method of choosing the left and right children set will depend on the problem in hand.

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