非二叉树的有序树遍历

Question

术语"inorder遍历"对于比二叉树更广泛的树具有明确定义的含义,还是"前"和"后"定义唯一有意义的DFS类型？我的意思是n每个节点有> 2个孩子.
我想n这是因为它可能意味着在n/2孩子们之后去了"根" ,但这是否曾经像这样使用过？奇怪的是n什么？

Answer 1

只有在将子集明确地划分为左子项和右子项时,才会继续很好地定义inorder遍历.

要看到这一点,请注意,如果我们展平树,则inorder遍历实际上按照它们将显示的顺序枚举节点(或者等效地,如果我们从左侧开始凝视树,则节点将出现的顺序).

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

例如,请考虑以下树:

如果我们将左子节点集合定义为左侧的前2个子节点,将右子节点集合定义为单个最后节点,我们将获得以下顺序遍历:

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

选择左右儿童组的方法将取决于手头的问题.