三元树的预序遍历

Question

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

public void preorder(){

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

它按根、左、右顺序遍历。我很困惑如何在添加了中间子节点的情况下做到这一点。如果有人能解释这个，那就太好了。谢谢

Answer 1

n进制树的一般预序遍历如下：

• 遍历节点本身
• 如果存在，则遍历子₀
• 如果存在，则遍历子₁
• ...
• 如果存在，则遍历子_N

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

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