Я читал, что обход в предварительном и обратном порядке также был определен для общих (n-арных) деревьев, например:
preOrder(v)
if(v==null) return;
print(v)
for each child w of v
preOrder(w)
postOrder(v)
if(v==null) return;
for each child w of v
postOrder(w)
print(v)
Но неупорядоченный обход подходит только для бинарных деревьев. Почему я не могу создать метод обхода inOrder, как в примерах pre и postOrder, показанных выше?
Конечно, вы можете определить обход, который будет n-арным обобщением того, что inorder есть для бинарных деревьев.
Для бинарных деревьев inorder означает посещение узла после посещения его левого дочернего элемента, но до посещения его правого дочернего элемента.
Для n-ary можно, например, сказать, что узел следует посетить после того, как были посещены его k крайние левые дочерние элементы, но до любого другого из его дочерних элементов. k будет предопределенной константой, и когда k=1, а ваше дерево бинарное, тогда у вас будет тот же обход, что и при классическом inorder обход.
inOrder(k, v)
if(v==null) return;
for each child w among the first k children of v:
inOrder(k, w)
print(v)
for each child w not among the first k children of v:
inOrder(k, w)
Но, как вы можете видеть, это немного неуклюжий обход, и можно задаться вопросом, есть ли у него действительно практическое применение.
