8. 二叉树结点的实现¶
8.1. 二叉树结点的实现¶
在本模块中，我们考察实现二叉树结点的各种方式。 根据定义，所有二叉树结点都有两个子结点， 不过其中一个或两个子结点可以为空。 二叉树结点通常包含一个值字段，字段的类型取决于具体应用。 最常见的结点实现包含一个值字段以及指向两个子结点的指针。
下面给出 BinNode 接口的一个简单实现，
我们将其命名为 BSTNode 。
它的元素类型是 Object。
当我们需要支持诸如
二叉搜索树 这样的查找结构时，
结点通常会存储一个
键值对 。
每个 BSTNode 对象还有两个指针，
一个指向其左子结点，另一个指向其右子结点。
// Binary tree node implementation for int values
class BSTNode implements BinNode {
private int element; // Element for this node
private BSTNode left; // Pointer to left child
private BSTNode right; // Pointer to right child
// Constructors
BSTNode() { left = right = null; }
BSTNode(int val) { left = right = null; element = val; }
BSTNode(int val, BSTNode l, BSTNode r)
{ left = l; right = r; element = val; }
// Get and set the element value
public int value() { return element; }
public void setValue(int v) { element = v; }
// Get and set the left child
public BSTNode left() { return left; }
public void setLeft(BSTNode p) { left = p; }
// Get and set the right child
public BSTNode right() { return right; }
public void setRight(BSTNode p) { right = p; }
// return TRUE if a leaf node, FALSE otherwise
public boolean isLeaf() { return (left == null) && (right == null); }
}
// Binary tree node implementation: supports comparable objects
class BSTNode<E extends Comparable<? super E>> implements BinNode<E> {
private E element; // Element for this node
private BSTNode<E> left; // Pointer to left child
private BSTNode<E> right; // Pointer to right child
// Constructors
BSTNode() { left = right = null; }
BSTNode(E val) { left = right = null; element = val; }
BSTNode(E val, BSTNode<E> l, BSTNode<E> r)
{ left = l; right = r; element = val; }
// Get and set the element value
public E value() { return element; }
public void setValue(E v) { element = v; }
// Get and set the left child
public BSTNode<E> left() { return left; }
public void setLeft(BSTNode<E> p) { left = p; }
// Get and set the right child
public BSTNode<E> right() { return right; }
public void setRight(BSTNode<E> p) { right = p; }
// return TRUE if a leaf node, FALSE otherwise
public boolean isLeaf() { return (left == null) && (right == null); }
}
有些程序员觉得，添加一个指向结点父结点的指针很方便， 这样可以轻松地在树中向上移动。 使用父结点指针有点类似于在双向链表中添加一个指向前一个结点的链接。 在实践中，父结点指针几乎总是多余的， 而且会增加树实现的空间开销。 父结点指针占用空间还不是唯一的问题。 更重要的是，许多对父结点指针的使用都源于对递归的不当理解， 因而表明编程水平不佳。 如果你倾向于使用父结点指针，请考虑是否存在更高效的实现方式。
在设计基于指针的结点实现时，一个重要决策是： 叶结点 和 内部结点 是否使用同一个类定义。 对两者使用同一个类会简化实现，但可能造成空间利用效率低下。 有些应用只在叶结点中需要数据值。 另一些应用则要求叶结点使用一种类型的值，而内部结点使用另一种类型的值。 例子包括 二叉 Trie 、 PR 四叉树 、 Huffman 编码树 ， 以及图 11.8.2 所示的 表达式树 。 根据定义，只有内部结点才有非空子结点。 如果我们对内部结点和叶结点使用相同的结点实现， 那么两者都必须存储子结点指针。 但在叶结点中存储子结点指针似乎是浪费的。 因此，有很多理由说明， 为内部结点和叶结点采用不同的实现可以节省空间。
作为一个在叶结点和内部结点存储不同信息的树的例子， 请考虑图 11.8.2 所示的表达式树。 表达式树表示由加、减、乘、除等二元运算符组成的代数表达式。 内部结点存储运算符，而叶结点存储操作数。 图 11.8.2 中的树表示表达式 \(4x(2x + a) - c\) 。 表达式树中叶结点的存储需求与内部结点的存储需求大不相同。 内部结点存储的是一小组运算符之一， 因此内部结点可以存储一个标识运算符的小代码， 比如用单个字节表示运算符的字符符号。 相比之下，叶结点存储变量名或数字， 为了处理范围更广的取值，它们要大得多。 同时，叶结点不必存储子结点指针。
面向对象语言
允许我们通过使用 类层次结构 来区分叶结点和内部结点。
基类 为对象提供一般性的定义，
而 子类 修改基类以添加更多细节。
可以为一般的二叉树结点声明一个基类，
并为内部结点和叶结点定义子类。
下面代码中的基类名为 VarBinNode 。
它包含一个名为 isLeaf 的虚成员函数，用于指示结点类型。
内部结点和叶结点类型的子类各自实现 isLeaf 。
内部结点存储基类类型的子结点指针；
它们不区分其子结点的实际子类。
每当检查一个结点时，
它的 isLeaf 版本会指示该结点的子类。
// Base class for expression tree nodes
public interface VarBinNode {
public boolean isLeaf(); // All subclasses must implement
}
// Leaf node
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; }
}
// Internal node
public class VarIntlNode implements VarBinNode {
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; }
}
static void traverse(VarBinNode rt) {
if (rt == null) { return; } // Nothing to visit
if (rt.isLeaf()) { // Process leaf node
Visit.VisitLeafNode(((VarLeafNode)rt).value());
}
else { // Process internal node
Visit.VisitInternalNode(((VarIntlNode)rt).value());
traverse(((VarIntlNode)rt).leftchild());
traverse(((VarIntlNode)rt).rightchild());
}
}
表达式树的实现包含两个从 VarBinNode 类派生出的子类，
分别名为 LeafNode 和 IntlNode 。
IntlNode 类可以通过 VarBinNode 类型的指针访问其子结点。
函数 traverse 演示了这些类的用法。
当 traverse 调用方法 isLeaf 时，
语言的运行时环境会判断 rt 这个特定实例恰好属于哪个子类，
并调用该子类的 isLeaf 版本。
然后方法 isLeaf 会把实际的结点类型提供给调用者。
派生类的其他成员函数，
则通过适当地对基类指针进行类型转换来访问，
如函数 traverse 所示。
