General Trees

04 Jun 2020

A tree is an abstract data type (ADT) built with nodes that store data. Every non-empty tree must have a root node. A root node may have addresses of its children nodes that it is pointing to, and every child node with its own set of children nodes store the addresses its children nodes, and so on. Children nodes that do have their own children have null pointers instead of the addresses of children nodes.

Two nodes that are children of the same parent are called siblings. A node is internal if it has one or more children; it is external if it has no children. External nodes are also known as leaves.

An edge of the tree is a pair of parent-child node. A path of the tree is the daisy-chained edges with ancestor-decendent relationships.

Now, having defined the structure, properties, and some basic terminologies about trees, we explore the topics of a tree’s bare basic functions, height and depth, traversal methods, and applications.

Functions

Trees of different types are created and modified (mutated) differently. Discussion about functions associated with creating and modigying/mutating trees will be put off for later articles. But all trees share many common accessor, query, and other more general functions.

Accessor functions

 root(): Returns the position of the root of the tree (or null if empty).
 parent(p): Returns the position of the parent of position p (or null if p is the root).
 children(p): Returns an iterable collection containing the children of position p (if any).
 numChildren(p): Returns the number of children of position p.

Query functions

int getElement(p): Returns the element stored at position p.
sInternal(p): Returns true if position p has at least one child.
isExternal(p): Returns true if position p does not have any children.
isRoot(p): Returns true if position p is the root of the tree.

General functions

size(): Returns the number of positions (and hence elements) that are contained in the tree.
isEmpty(): Returns true if the tree does not contain any positions (and thus no elements).
iterator(): Returns an iterator for all elements in the tree (so that the tree
positions(): Returns an iterable collection of all positions of the tree.

If an invalid position is sent as a parameter to any method of a tree, then an IllegalArgumentException is thrown.

Height and Depth

Traversal

Application

In general, the non-linearity property of trees allows us to implement algorithms a lot faster with trees than with other linear data types like arrays and lists.

The file system of a computer is a tree. Internal nodes of the tree are directories and the external nodes, the leaves, are files. In Unix or Linux, the root of the file system is eponymously called the root directory and represented by the “/” symbol.