Trees

page last updated 3/29/08

Hierarchical structures

Countries States Counties Townships

Colleges Departments Courses Sections Students

Sentence Noun-Phrase Verb-Phrase
Verb-Phrase Verb Noun-Phrase
etc.

Directory structures 

Type hierarchy as example

 

 

Not a tree

Terminology

Node
a component of the tree that holds data
Root  top element of the hierarchical structure; the starting element.  There is only one root per tree 
Child   
a  node's immediate successor; 
a node may have zero or more successors
Parent 
a node's predecessor :  if node C is a child of node P, then P is a parent of C
a node has exactly one parent 
Leaf a node that has no children 
Descendant 
 
an extension of the child relationship: If C is a child of P, then C is a descendant of P, or if C is a child of a descendant D then C is a descendant of D 
Ancestor 
an extension of the parent relationship: If D is a descendant of A then A is an ancestor of D.
Sibling child node that has the same parent as another node
Edge/branch the line or connection between a parent and child (there may be a weight value associated with the edge)
Path the sequence of edges between a node and one of its descendents
Path length the number of edges in a path
Interior node a node that has at least one child
Depth or level the length of the path connecting a node to the root.  The root's depth or level is 0
Height the longest path length in the tree
Subtree the tree made of all descendents using some non-root node

 

 

 

 

General tree

  1. An empty tree, one with no nodes, is a tree
  2. A single node is a tree (it is also the root).
  3. The structure formed by taking a node R and on or more separate trees and making R the parent of all roots of the trees is a tree .

Examples of general trees

Subtree - the empty tree is a subtree of any tree
any node of a tree, together with all its descendants, is a subtree
Level - the level of the root node is 0
the level of any node other than the root is one greater than the level of its parent
Height - the height of a tree is the maximum of the levels of its leaves.

 

 

 

 

Binary trees

  1. Every node in a binary tree can have at most two children
  2. The children are labeled left child and right child.

Examples of binary trees

 

 

 

 

Formal Definitions

Nonrecursive definition of a general tree: A general tree is either empty or consists of a finite set of nodes and a finite set of edges that connect pairs of nodes.  The node at one end of an edge is called the parent and at the other the child.  One node is distinguished from all others and is called the root.  All nodes except the root are connected by an edge to exactly one parent.

Recursive definition of a general tree: A general tree is either empty or consists of a finite set of nodes T.  One node r is distinguished from all others and is called the root.  In addition, the set T-{r} is partitioned into disjoint subsets, each of which is a general tree.

Recursive definition of a binary tree:  A binary tree is either empty or consists of a root plus a left subtree and a right subtree, each of which are binary trees.

 

 

 

Linked Representations

Each node consists of a value field and links to each of its children.

In the case of a general tree, the node must be contain enough links for the maximum number of children.  This approach has an artificial limit that you may want to avoid.  Consider the general tree to the right and draw its linked representation.  What degree of links (maximum number of children) are needed?

 

 

 

Binary trees have only a pair of links: left child and right child. Consider the binary tree to the right  and draw its representation.

A binary tree can be used to represent any general tree.  The left child holds the first child of the original general tree and the right child holds the next sibling.  Represent the above general tree in this binary tree definition.

 

 

 

 

Array representation of a complete binary tree

When a tree is complete, an array can efficiently represent a binary tree.  A complete binary tree is one that each level except the last has a complete complement of nodes and if the nodes on the last level are filled in from the left.

The array order would be: A B C E G K M Q W

A full binary tree is one where all the leaves are on the same level, and every non-leaf node has two children.

Note: In the MA 116 textbook, the definition of a full binary tree is simply "every non-leaf node has two children."

 

0 1 2 3 4 5 6 7 8 9
A B C E G K M Q W  

Given an arbitrary position p, you can calculate its parent, left child and right child, left and right siblings:

parent = (p-1)/2
leftSibling = i-1
rightSibling = i+1
leftChild = i*2+1
rightChild = i*2+2

This is used for the heap data structures.

 

 

Binary Search Trees

A BST is a specialized binary tree with the following properties

  1. no two nodes in the tree contain the same data
  2. The data values in the tree come from a data type (class)  for which < and > (or compareTo) are defined
  3. The data (key) value of every node in the tree is
    - greater than any data value in its left subtree
    - less than any data value in its right subtree

 

 

Binary Tree Traversals

Traversal Definitions

Preorder traversal: Visit the root, visit the left subtree, visit the right subtree

Inorder traversal: Visit the left subtree, visit the root, visit the right subtree

Postorder traversal: Visit the left subtree, visit the right subtree, visit the root

 

 

The Comparable Interface

Consist of exactly one abstract method:

public int compareTo (Object o);
// Returns a negative integer, zero, or a positive integer as this object 
//is less than, equal to, or greater than the parameter object

Consistent with the way we have been using compareTo (in Listable)

Our trees will hold objects of type Comparable

 

 

 

Binary Search Tree Interface

The BSTInterface.java interface (code only)

 

 

BST Node Definition

The BSTNode class (code)

The BinarySearchTree class (code)