CS 455 Lecture Notes

Week Thirteen, Tuesday: Trees

Graphs

Main and Savitch call graphs "the ultimate commonly used data structure." A tree is a special kind of graph. A graph is a set of nodes (vertices) and a set of links between nodes (edges). If the links are one-way, the graph is called "directed." A cycle in a graph is a path that returns to a starting vertex. An acyclic graph is a tree.

Graph of a Discrete Priority Queue

A priority queue is a waiting situation where some elements have a higher priority than others. For example, first class passengers have a higher priority for boarding an airplane than business class or coach class. The airport situation can be implemented by having a queue of queues, which can be represented graphically.

Introduction to Trees

The simplest tree is a binary tree, in which parent nodes have at most two children. Nodes without children are called leaves. The root of the tree is the only node without a parent, and the tree is accessed by a program by a pointer to the root.

A binary tree can be categorized as full, complete, or neither. Every full binary tree is complete, but not every complete binary tree is full.

A node in a general tree may have an unlimited number of children. These links are often kept as a linked list or an array (the choice of which represents a design decision).

Tree Representations

A complete binary tree can be represented very efficiently with an array. Data for the root will be at [0]. The parent data for a node will be at [(i - 1) / 2] and data for the left and right children will be at [2 * i + 1] and [2 * i + 2], respectively.

If the binary tree is cannot be guaranteed to be complete (the usual case) then the tree can be represented by linked nodes (implemented with a class or struct). The entire tree is represented with a pointer to the root node. Because the tree is binary, a linked list or array of pointers is not necessary: you only need pointers to the left and right children. If the node is a leaf, both pointers are null.

A Toolkit for Binary Tree Nodes

Four toolkit functions:

Create a new node.
Test whether a node is a leaf.
Return all the nodes to the heap (destroy the tree).
Copy a tree (returns a pointer to the root of a copy of the tree).

This page established November 28, 1999; last updated November 29, 1999.