Introduction

We extend the concept of linked data structures to structure containing nodes with more than one self-referenced field. A binary tree is made of nodes, where each node contains a "left" reference, a "right" reference, and a data element. The topmost node in the tree is called the root.Every node (excluding a root) in a tree is connected by a directed edge from exactly one other node. This node is called a parent. On the other hand, each node can be connected to arbitrary number of nodes, called children. Nodes with no children are called leaves, or external nodes. Nodes which are not leaves are called internal nodes. Nodes with the same parent are called siblings.

• The depth of a node is the number of edges from the root to the node.
• The height of a node is the number of edges from the node to the deepest leaf.
• The height of a tree is a height of the root.
• A full binary tree.is a binary tree in which each node has exactly zero or two children.
• A complete binary tree is a binary tree, which is completely filled, with the possible exception of the bottom level, which is filled from left to right.

n = 1 + 2 + 4 + ... + 2h-1 + 2h = 2h+1 - 1

h = O(log n)

Advantages of trees

• Trees reflect structural relationships in the data
• Trees are used to represent hierarchies
• Trees provide an efficient insertion and searching
• Trees are very flexible data, allowing to move subtrees around with minumum effort

Traversals

• depth-first traversal
• breadth-first traversal

• PreOrder traversal - visit the parent first and then left and right children;
• InOrder traversal - visit the left child, then the parent and the right child;
• PostOrder traversal - visit left child, then the right child and then the parent;

As an example consider the following tree and its four traversals: PreOrder - 8, 5, 9, 7, 1, 12, 2, 4, 11, 3 InOrder - 9, 5, 1, 7, 2, 12, 8, 4, 3, 11 PostOrder - 9, 1, 2, 12, 7, 5, 3, 11, 4, 8 LevelOrder - 8, 5, 4, 9, 7, 11, 1, 12, 3, 2

Binary Search Trees

A BST is a binary tree where nodes are ordered in the following way: each node contains one key (also known as data) the keys in the left subtree are less then the key in its parent node, in short L < P; the keys in the right subtree are greater the key in its parent node, in short P < R; duplicate keys are not allowed. In the following tree all nodes in the left subtree of 10 have keys < 10 while all nodes in the right subtree > 10. Because both the left and right subtrees of a BST are again search trees; the above definition is recursively applied to all internal nodes:

Implementation

public class BST <AnyType extends Comparable<AnyType>>
{
   private Node<AnyType> root;

   private class Node<AnyType>
   {
      private AnyType data;
      private Node<AnyType> left, right;

      public Node(AnyType data)
      {
         left = right = null;
         this.data = data;
      }
   }
   ...

}

Insertion

11, 6, 8, 19, 4, 10, 5, 17, 43, 49, 31

Searching

Deletion

• is not in a tree;
• is a leaf;
• has only one child;
• has two children.

11, 6, 8, 19, 4, 10, 5, 17, 43, 49, 31

Non-Recursive Traversals

public Iterator<AnyType> iterator()
{
  return new PreOrderIterator();
}

private class PreOrderIterator implements Iterator<AnyType>
{
  ...
}

public AnyType next()
{
   Node cur = stk.peek();
   if(cur.left != null)
   {
      stk.push(cur.left);
   }
   else
   {
      Node tmp = stk.pop();
      while(tmp.right == null)
      {
         if (stk.isEmpty()) return cur.data;
         tmp = stk.pop();
      }
      stk.push(tmp.right);
   }
   return cur.data;
}

public AnyType next()
{
   if (stk.isEmpty()) throw new java.util.NoSuchElementException();

   Node cur = stk.pop();
   if(cur.right != null) stk.push(cur.right);
   if(cur.left != null) stk.push(cur.left);

   return cur.data;
}

Level Order Traversal