COMP1927 - Trees

Introduction to Trees

Trees are another data structure we often encounter. They're useful for manipulating hierarchical data, sorting and searching.

Definitions

Edge
Connections between nodes.
Path
Connected edges (ways of following lines to get between nodes).
Height
Length of longest path from root (i.e. how many levels down the lowest leaf node is).
Node Level
Length of path from node to root.
Balanced
Tree has the minimal possible height for the number of nodes, and the number of nodes in the left and right subtrees differ by 0 or 1.
Degenerate
Tree with maximal height for the number of nodes (e.g. basically a list)
Descendants
All nodes below the current node, reachable by a path.
Internal Node
A node with children.
External Node
A leaf node, no children.

Types of Trees

Ordered Tree

An ordered tree is, as the name suggests, a tree where the data is ordered based on something such as size.

Binary Tree

A binary tree is a tree where each internal node (non-leaf node) has at most 2 children.

Full Binary Tree

In a full binary tree every internal node has exactly two children

Perfect Binary Tree

In a perfect binary tree all leaves are at the same depth. Meaning that each leaf is the same number of levels down from the root as every other leaf.

Ordered Binary Tree

Essentially a combination of an ordered tree and a binary tree.
The left children <= parent, and the right children >= parent.
It's also called a binary search tree.

Full m-ary Tree

Each internal node has exactly m children.

Binary Search Trees

As said above, a binary search tree is an ordered binary tree. More info

Tree Traversal

There are a number of ways to traverse a tree; depth-first and breadth-first being one way of splitting the two types.

More details on tree/graph traversal