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

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

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