Trees

Table of contents

1. Introduction
2. Representing a rooted tree
3. References

Introduction

A tree is set $T$ of one or more nodes, where:

1. There is one designated root node of the tree, $root(T)$.
2. The remaining nodes are partitioned into $m >= 0$ disjoint sets $T_1 ... T_m$, where each of the sets are also trees. The trees $T_1 ... T_m$ are called subtrees of $T$.

[1, P. 308]

Trees use the same terminology as family trees to describe relationships between nodes. A node can have a parent, a sibling, a grandparent, etc. [1, P. 311].

The number of subtrees of a tree is called its degree. A tree of degree 0 is a leaf [1, P. 308].

A forest is a set of of zero or more disjoint trees. Deleting the root of a tree creates a forest [1, P. 309].

Representing a rooted tree

A rooted binary tree can be represented as nodes with pointers parent, left, and right, where parent points to the parent node, left points to the left child node and right points to the right child node [2, P. 246].

$x$ is the root of the tree if parent $= NULL$.

Note: future diagrams don’t show NULL pointers explicitly.

A rooted tree node with $n$ children (an n-ary tree) can be represented using similar pointers. Instead of a pointer to each child from the parent, each node contains a left_child pointer to the leftmost child (or NULL if not), and a right_child pointer to the right most child (or NULL if $n \lt 2$).

Each node then contains two pointers: left_sibling and right_sibling. left_sibling points to the previous sibling (NULL if none exists), and right_sibling points to its immediate right sibling (NULL if none exists) [2, P. 246].

References

1. [1] D. E. Knuth, The Art of Computer Programming, vol. 1. Boston, MA, USA: Addison-Wesley Longman Publishing Co., Inc., 1998.
2. [2] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, 3rd ed. The MIT Press, 2009.