java - 三叉树的前序遍历

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

二叉树恰好只有孩子₀（左）和孩子₁（右），但三叉树也有中间。所以你的遍历在遍历左右子树之间会有一个额外的语句：

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