5.1. Trees

A tree is made up of nodes (data elements) with zero, one, or several references to other nodes. Each node has only one other node referencing it. The result is a data structure that looks like Figure 5-1.

As in a linked list, a node is represented by a structure or class, and trees can be implemented in any language that includes pointers or references. In object-oriented languages you usually define a class for the common parts of a node, and one or more subclasses for the data held by a node. For example, these are the C# classes you might use for a tree of integers:

public class Node {
    public Node[] children;
}

public class IntNode : Node {
    public int value;
}
Figure 5.1. Figure 5-1

In this definition, children is an array that keeps track of all the nodes that this node references. Note that for simplicity we exposed the children as public data members. A proper class definition would make them private and expose methods to manipulate them. A fuller Java equivalent (with methods and constructors) to the preceding classes would be as follows:

public abstract class Node { private Node[] children; public Node( Node[] children ){ this.children = children; } public int getNumChildren(){ return children.length; } public Node getChild( int index ){ return children[ index ]; } } public class IntNode extends Node { private int value; public IntNode( Node[] children, int ...

Get Programming Interviews Exposed: Secrets to Landing Your Next Job, Second Edition now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.