9. 基于组合模式的表达式树¶

9.1. 基于组合模式的表达式树¶

我们还可以采用另一种方法来分别表示叶结点和内部结点，同样是使用虚基类和针对这两种类型的独立结点类。这就是使用组合设计模式来实现结点。这种方法与过程式方法明显不同，因为结点类自身实现了 traverse 的功能。下面是其实现。基类 VarBinNode 声明了一个成员函数 traverse ，每个子类都必须实现它。然后每个子类针对自己在遍历中的角色，实现各自适当的行为。整个遍历过程是通过在根结点上调用 traverse 来启动的，而根结点又会对其子结点调用 traverse 。

/** Base class: Composite */
public interface VarBinNode {
  public boolean isLeaf();
  public void traverse();
}

/** Leaf node: Composite */
public class VarLeafNode implements VarBinNode {
  private String operand;                 // Operand value

  VarLeafNode(String val) { operand = val; }
  public boolean isLeaf() { return true; }
  public String value() { return operand; }

  public void traverse() {
    Visit.VisitLeafNode(operand);
  }
}

/** Internal node: Composite */
public class VarIntlNode implements VarBinNode { // Internal node
  private VarBinNode left;                // Left child
  private VarBinNode right;               // Right child
  private Character operator;             // Operator value

  VarIntlNode(Character op, VarBinNode l, VarBinNode r) {
    operator = op; left = l; right = r;
  }
  public boolean isLeaf() { return false; }
  public VarBinNode leftchild() { return left; }
  public VarBinNode rightchild() { return right; }
  public Character value() { return operator; }

  public void traverse() {
    Visit.VisitInternalNode(operator);
    if (left != null) { left.traverse(); }
    if (right != null) { right.traverse(); }
  }
}

   /** Preorder traversal */
   public static void traverse(VarBinNode rt) {
     if (rt != null) { rt.traverse(); }
   }

将组合实现与过程式方法相比较时，两者各有优缺点。非组合方法不要求结点类了解 traverse 函数。使用这种方法，很容易向树类添加执行其他遍历或对树中结点执行其他操作的新方法。然而，我们看到非组合方法中的 traverse 确实需要熟悉每个结点子类。因此，添加一个新的结点子类就需要修改 traverse 函数。相比之下，组合方法要求树上的任何需要遍历的新操作也必须在结点子类中实现。另一方面，组合方法使 traverse 函数无需了解各结点子类各自的能力。这些子类自行承担对自己执行遍历的职责。一个附带的好处是， traverse 无需显式枚举所有不同的结点子类，并为每个子类指定适当的操作。只有两个结点类时，这只是个小问题。但如果有许多这样的子类，这就可能成为一个更大的问题。一个缺点是，不能在 NULL 指针上调用遍历操作，因为没有对象来接收该调用。通过使用享元来实现空结点，可以避免这个问题。如果组合实现针对的是满树，那么就不必显式检查子结点是否为空。

通常，在这个例子中，如果 traverse 是树类的成员函数，并且结点子类对树类的使用者隐藏，那么非组合版本会更受青睐。另一方面，如果结点对象对树的使用者而言，除了作为树中结点的存在之外还有其他意义，那么组合版本可能更受青睐，因为此时隐藏结点的内部行为变得更加重要。

组合设计的另一个优点是，实现每种结点类型的功能可能更容易。这是因为它使你能够只专注于该结点类型完成其工作所需的信息传递和其他行为。这降低了程序员在处理与递归处理相关的复杂信息流时常常感到不知所措的复杂度。

CS3 数据结构与算法

Chapter 7 Binary Trees

9. 基于组合模式的表达式树¶

9.1. 基于组合模式的表达式树¶