Предзаказ обхода тройного дерева

Question

Мне нужно выполнить предварительный обход троичного дерева. Я знаком с этим обходом двоичного дерева, например:

public void preorder(){

   System.out.println(data); 
   if (left != null)
      left.preorder();
   if (right != null)
      right.preorder();
}

Это происходит в порядке Root, Left, Right. Я не понимаю, как это сделать с добавлением среднего дочернего узла. Если бы кто-нибудь мог объяснить это, было бы здорово. Спасибо

Answer 1

Общий обход предзаказа n-арного дерева происходит следующим образом:

• Пройдите сам узел
• Если существует, переберите ребенка₀
• Если существует, пройти ребенка₁
• ...
• Если существует, переберите дочерний_n

Бинарное дерево имеет только дочерний₀ (слева) и дочерний₁ (справа), но троичное дерево также имеет середину. Таким образом, ваш обход будет иметь дополнительное утверждение между обходом левого и правого поддерева:

if (middle != null)
    middle.preorder();

Answer 2

Траверс среднего узла между левым и правым узлом

public void preOrder(Node node) {
    if (node == null) {
        return;
    }
    System.out.print(" " + node.data);
    preOrder(node.left);
    preOrder(node.middle);
    preOrder(node.right);
}