Logo

Programming-Idioms

This language bar is your friend. Select your favorite languages!
  • Java

Idiom #9 Create a Binary Tree data structure

The structure must be recursive because left child and right child are binary trees too. A node has access to children nodes, but not to its parent.

class BinTree<T extends Comparable<T>>{
   T value;
   BinTree<T> left;
   BinTree<T> right;
}

Note that with this design an empty tree is null, and thus is not an instance of BinTree.
interface Tree<T>{
    boolean search(T x);
}
class Nil<T extends Comparable<? super T>> implements Tree<T>{
    public boolean search(T x) { return false; }
}
class Node<T extends Comparable<? super T>> implements Tree<T> {
 T item;  Tree<T> left; Tree<T> right;
 public Node(T i, Tree<T> l, Tree<T> r) {
     item=i;  left=l;  right=r; }
 public boolean search(T x) {
     int cmp = x.compareTo(item);
     return cmp==0 || (cmp<0 && left.search(x)) || (cmp>0 && right.search(x));
 }

don't have room for more
type Tree_Node;
type Tree_Node_Access is access Tree_Node;
type Tree_Node is record
   Value: Integer;
   Left, Right: Tree_Node_Access;
end record;

New implementation...
< >
programming-idioms.org