Priority Queues Top Binary Search Trees Contents

Binary Trees

Synopsis

A binary tree is a two-dimensional linked-list. Typically, a node in a binary tree has two next pointers, named left and right, and a value pointer. Binary tree nodes may have parent pointers, as well

Structure

    class binaryTreeNdde
        {
        var value;
        var left;
        var right;
        }

    class binaryTree
        {
        var root;              //points to the root binary node
        //operations
        ...
        }

Vocabulary

The terms used in describing a binary tree are:

full
Each node in the tree has either two children or no children.
perfect
A full tree with all the leaves at the same level.
complete
A tree that is perfect except for, perhaps, the level furthest from the root. In that furthest level, all the leaves are piled up to the left. A heap is an example of a complete binary tree.
balanced
A tree is balanced if the longest path from the root to a leaf is not much longer than the shortest path. In other words, a nearly perfect tree. What constitutes "not much more" and "nearly" depends on the situation.
completely unbalanced
A tree is completely unbalanced if it has but one leaf.
root
The root node of a binary tree is the only node with no parent. It is considered the "top" of the tree, since trees are commonly drawn upside down, with the branches pointing downwards.
leaf,leaves
A node whose left and right pointers are null. In other words, a node with no children.
parent
Other than the root, each node n has exactly one other node p pointing to it. The node p is said to be the parent of n.
child,children
Other than the leaves, each node p points to one or two other nodes. These nodes are said to be the children of p.
sibling
The other child of a parent node (if it exists).

Supports

Complete binary trees (heaps) are used in heapsorting and other higher-order algorithms.

The most common use of a binary tree is when it is formulated as a binary search tree.

Dependencies

Binary trees are implemented with nodes.

Operations

The common operations on a binary tree are insert, find, and delete. The actual implementation of these operations depends on the kind of binary tree, say a binary search tree or a heap.

Traversals

in-order

In an in-order traversal is easily implemented using a recursive process that implements the following steps:

  1. traverse the left side
  2. process the node
  3. traverse the middle side

Note that the node processing step occurs "in the middle". Hence the name, in-order. Processing the node is a phrase meant to capture the purpose of the traversal. For printing out the nodes of a tree, processing the node means printing the value of the node. Here is such a traversal:

    function print-in-order(node)
        {
        if (node.get-left() == null)
            print-in-order(node.get-left());

        println(node.get-value());

        if (node.get-right() == null)
            print-in-order(node.get-right());
        }

This code can be simplified by the strategy of "falling off the tree". One detects a falling off by seeing if the given node has become null. If so, no processing is done. Recall that the null value is used to signify that a node pointer does not point to any node.

    function print-in-order(node)
        {
        if (node != null)
            {
            print-in-order(node.get-left());
            println(node.get-value());
            print-in-order(node.get-right());
            }
        }

pre-order

A pre-order traversal is like an in-order traversal, except node processing happens first:

  1. process the node
  2. traverse the left side
  3. traverse the right side

post-order

In a post-order traversal, node processing happens last.

level-order

A level order uses a queue as an auxilliary structure. The traversal starts be enqueuing the root node. Next a loop:

The loop continues until the queue is empty.

Concept Inventory

     
  1. This is a question.
    1. This is one possible answer
    2. This is another possible answer

lusth@cs.ua.edu


Priority Queues Top Binary Search Trees Contents