8.8. Binary Tree Node Implementations¶
8.8.1. Binary Tree Node Implementations¶
In this module we examine various ways to implement binary tree nodes. By definition, all binary tree nodes have two children, though one or both children can be empty. Binary tree nodes typically contain a value field, with the type of the field depending on the application. The most common node implementation includes a value field and pointers to the two children.
Here is a simple implementation for the
BinNode
interface, which we will name BSTNode
.
Its element type is an Object.
When we need to support search structures such as the
Binary Search Tree,
the node will typically store a
key-value pair.
Every BSTNode
object also has two pointers,
one to its left child and another to its right child.
// Binary tree node implementation: supports comparable objects
class BSTNode implements BinNode {
private Comparable 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(Comparable val) { left = right = null; element = val; }
BSTNode(Comparable val, BSTNode l, BSTNode r)
{ left = l; right = r; element = val; }
// Get and set the element value
public Comparable value() { return element; }
public void setValue(Comparable v) { element = v; }
public void setValue(Object v) { // We need this one to satisfy BinNode interface
if (!(v instanceof Comparable))
throw new ClassCastException("A Comparable object is required.");
element = (Comparable)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); }
}
Some programmers find it convenient to add a pointer to the node’s parent, allowing easy upward movement in the tree. Using a parent pointer is somewhat analogous to adding a link to the previous node in a doubly linked list. In practice, the parent pointer is almost always unnecessary and adds to the space overhead for the tree implementation. It is not just a problem that parent pointers take space. More importantly, many uses of the parent pointer are driven by improper understanding of recursion and so indicate poor programming. If you are inclined toward using a parent pointer, consider if there is a more efficient implementation possible.
An important decision in the design of a pointer-based node implementation is whether the same class definition will be used for leaves and internal nodes. Using the same class for both will simplify the implementation, but might be an inefficient use of space. Some applications require data values only for the leaves. Other applications require one type of value for the leaves and another for the internal nodes. Examples include the binary trie, the PR Quadtree, the Huffman coding tree, and the expression tree illustrated by Figure 8.9.2. By definition, only internal nodes have non-empty children. If we use the same node implementation for both internal and leaf nodes, then both must store the child pointers. But it seems wasteful to store child pointers in the leaf nodes. Thus, there are many reasons why it can save space to have separate implementations for internal and leaf nodes.
As an example of a tree that stores different information at the leaf and internal nodes, consider the expression tree illustrated by Figure 8.9.2. The expression tree represents an algebraic expression composed of binary operators such as addition, subtraction, multiplication, and division. Internal nodes store operators, while the leaves store operands. The tree of Figure 8.9.2 represents the expression \(4x(2x + a) - c\). The storage requirements for a leaf in an expression tree are quite different from those of an internal node. Internal nodes store one of a small set of operators, so internal nodes could store a small code identifying the operator such as a single byte for the operator’s character symbol. In contrast, leaves store variable names or numbers, which is considerably larger in order to handle the wider range of possible values. At the same time, leaf nodes need not store child pointers.
Object-oriented languages
allow us to differentiate leaf from
internal nodes through the use of a class hierarchy.
A base class provides a general definition for an
object,
and a subclass modifies a base class to add more detail.
A base class can be declared for binary tree nodes in general,
with subclasses defined for the internal and leaf nodes.
The base class in the following code is named
VarBinNode
.
It includes a virtual member function named
isLeaf
, which indicates the node type.
Subclasses for the internal and leaf node types each implement
isLeaf
.
Internal nodes store child pointers of the base class type;
they do not distinguish their children’s actual subclass.
Whenever a node is examined, its version of isLeaf
indicates
the node’s subclass.
// 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; }
}
// Preorder traversal
public 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());
}
}
The Expression Tree implementation includes two subclasses derived
from class VarBinNode
, named LeafNode
and
IntlNode
.
Class IntlNode
can access its children through
pointers of type VarBinNode
.
Function traverse
illustrates the use of these classes.
When traverse
calls method isLeaf
,
the language’s runtime environment
determines which subclass this particular instance of rt
happens to be and calls that subclass’s version of isLeaf
.
Method isLeaf
then provides the actual node type to its
caller.
The other member functions for the derived subclasses are accessed by
type-casting the base class pointer as appropriate, as shown in
function traverse
.