ADT Binary Tree

Tom Kelliher, CS23

Apr. 18, 1996

Do we need to discuss an extension?

Consider the operations:

How efficient is a
  1. Pointer-based list?
  2. Array-based list?

Can sorting make a difference?

Is there a better way to perform ``dictionary'' operations?

Nomenclature

A tree:

  1. Vertex/node , directed edge.
  2. Root, interior vertex, leaf.
  3. Parent, child; ancestor, descendant.
  4. Siblings.
  5. Subtrees.
  6. General trees.
  7. A Binary tree, T, is a set of nodes such that either:
  8. Binary search tree:
  9. Height, level.
  10. Full, complete. The book's defn. of complete is wrong. Counterexample?
  11. Balanced binary tree, completely balanced binary tree.

Recursive structure.

ADT Tree Operations

Traversals

typedef char NodeType;

struct NodeItem
{
   NodeItem* left, right;
   NodeType item;
};

typedef NodeItem* Node;

Preorder

void Preorder(Node T, void (*Visit)(NodeType))
{
   if (T != NULL)
   {
      Visit(T->item);
      Preorder(T->left, Visit);
      Preorder(T->right, Visit);
   }
}

Inorder

void Preorder(Node T, void (*Visit)(NodeType))
{
   if (T != NULL)
   {
      Inorder(T->left, Visit);
      Visit(T->item);
      Inorder(T->right, Visit);
   }
}

Postorder

void Preorder(Node T, void (*Visit)(NodeType))
{
   if (T != NULL)
   {
      Postorder(T->left, Visit);
      Postorder(T->right, Visit);
      Visit(T->item);
   }
}

Examples

void visit(NodeType n)
{
   cout << n << endl;
}

Assume each function is called on the root of:

What is printed?

ADT Tree Implementation

Pointer-Based Implementation

Been there, done that.

How do we get to the parent from the child?

Array-Based Implementation

The tree:

char tree[MAXTREE];   // tree[0] is root

children of tree[i]:

Can get to parent from child.


Thomas P. Kelliher
Thu Apr 18 22:40:41 EDT 1996
Tom Kelliher