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?


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


typedef char NodeType;

struct NodeItem
   NodeItem* left, right;
   NodeType item;

typedef NodeItem* Node;


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


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


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


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