Data Structures for Trees

Data Structures for Trees
An Introduction

Prof. David Bernstein
James Madison University

Computer Science Department

bernstdh@jmu.edu

Background

Graph:
- A set of vertices/nodes and a set of edges/links/arcs (each joining a pair of nodes)
Tree:
- A connected graph with no circuits

N-ary Trees

Defined:
- A directed tree in which each vertex has at most N "outbound" arcs and at most one "inbound" arc
Other Terminology:
- The vertex incident to the inbound arcs is called the parent
- The vertices incident to the outbound arcs are called the children
The Most Common Example:
- Binary Tree
- (Courtesy of Hackles)

Binary Trees

An Example

Common Data Structures

N-ary Trees:
- Contiguous structures (when the size is known)
- Linked Structures
General Trees:
- Linked structures

Contiguous Structures for N-ary Trees

A Contiguous Structure for this Example:

45

41

42

35

29

38

34

22

11

40

9

18

Contiguous Structures for N-ary Trees (cont.)

Index Calculations:
- parent(i) = (i - 1) / N
- firstChild(i) = (i * N) + 1
- lastChild(i) = (i * N) + N
Back to the Example:
- The 42 is in position 2
- Its parent is in position (2-1)/3 = 0
- It's children are in positions 7 through 9

Linked Structures for Trees

Nodes:
- Contain child nodes or pointers to child nodes
- May contain a pointer to the parent node
Example: