三叉树的前序遍历

Question

我需要执行三元树的前序遍历。二叉树上的这种遍历我很熟悉，比如：

public void preorder(){

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

这里按照Root, Left, Right的顺序遍历。我对如何添加中间子节点感到困惑。如果有人可以解释这一点，那就太好了。谢谢

Answer 1

一般n叉树的前序遍历如下：

遍历节点本身
如果存在，则遍历child₀
如果存在，遍历child₁
...
如果存在，则遍历child_n

二叉树正好只有child₀（左）和child₁（右），但是三叉树还有一个中间.所以你的遍历在遍历左右子树之间会有一个额外的语句：

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);
}

三叉树的前序遍历

Preorder traversal of ternary tree

java

tree-traversal

preorder

ternary-tree