许多编程语言，尤其是函数式语言，使用了代数数据类型。代数数据类型是一种组合类型，可以像代数那样计算，典型代表有“积类型”（也称序对）和“和类型”（最简单的形式为枚举类型）。一个例子如下： Haskell> data Term = Constant Int | Add Term Term | IfZero Term Term Term 这就是说，类型为Term的值是Constant、Add或IfZero的一种。每一种值的构造都需要一些参数，如Consant值的构造需要一个整数参数。对代数数据类型的值进行操作时，可以使用模式匹配的方式进行，即通过匹配值的构造方示。下列代码表示对类型为Term的值的一种操作： Haskell> eval term = case term of Constant i -> i Add e1 e2 -> eval e1 + eval e2 IfZero e1 e2 e3 -> if eval e1 == 0 then eval e2 else eval e3 一、请用java语言实现下列代数结构及其操作： (1) 列表结构 Haskell> data List a = Nil | Cons a (List a) Haskell> size list = case list of Nil -> 0 Cons a list1 -> 1+ size list1 (2) 树结构 Haskell> data Tree t = Leaf t | Node (Tree t) (Tree t) Haskell> size tree = case tree of Leaf leaf -> 1 Node t1 t2 -> 1 + size t1 + size t2

下面是Java语言实现的代码：

(1) 列表结构

public abstract class List<A> {
public abstract int size();
}

public class Nil<A> extends List<A> {
@Override
public int size() {
return 0;
}
}

public class Cons<A> extends List<A> {
private final A head;
private final List<A> tail;

public Cons(A head, List<A> tail) {
this.head = head;
this.tail = tail;
}

@Override
public int size() {
return 1 + tail.size();
}
}

(2) 树结构

public abstract class Tree<T> {
public abstract int size();
}

public class Leaf<T> extends Tree<T> {
private final T value;

public Leaf(T value) {
this.value = value;
}

@Override
public int size() {
return 1;
}
}

public class Node<T> extends Tree<T> {
private final Tree<T> left;
private final Tree<T> right;

public Node(Tree<T> left, Tree<T> right) {
this.left = left;
this.right = right;
}

@Override
public int size() {
return 1 + left.size() + right.size();
}
}