// Binary Trees
//
// Paul E. Dunne 27/11/07
//
public class BinaryTree
  {
  protected int TreeRoot;                 // Tree Root
  protected BinaryTree LeftTree;             // Pointer to Left Sub-tree
  protected BinaryTree RightTree;           // Pointer to Right Sub-tree
  //*****************************************************
  // Binary Tree Methods                                *
  //*****************************************************
  //
  // Test is this tree contains exactly one node.
  //
  public boolean IsLeafNode()
    {
    return (LeftTree==null)&&(RightTree==null);
    }
  //*****************************************************
  // Set and Obtain the Root of this Binary Tree        *
  //*****************************************************
  public void SetRootValue( int root_val )
    {
    TreeRoot = root_val;
    }
  public int GetRootValue()
    {
    return TreeRoot;
    }
  //*****************************************************
  // Set the Left/Right Subtress of this BinaryTree     *
  //*****************************************************
  public void SetLeft( BinaryTree L )
    {
    LeftTree=L;
    }
  //
  public void SetRight( BinaryTree R )
    {
    RightTree=R;
    }
  //*****************************************************
  // Get the Left/Right Subtrees of this BinaryTree     *
  //*****************************************************
  public BinaryTree GetLeft ()
    {
    return LeftTree;
    }
  //
  public BinaryTree GetRight()
    {
    return RightTree;
    }
 //*********************************************************************
 public static BinaryTree BuildTree(int root, BinaryTree L, 
                                              BinaryTree R)
   {
   BinaryTree T = new BinaryTree();
   T.SetRootValue(root);
   if (!(L==null))
     T.SetLeft(L); T.SetRight(R);
   return T;
   };
 //*********************************************************************
 // Find height of T
 //*********************************************************************
 public static int DepthOf (BinaryTree T)
   {
   if (T.IsLeafNode())
     return 1;
   else
     return 1+Math.max( DepthOf(T.GetLeft()), DepthOf(T.GetRight()) );
   };
 //*********************************************************************
 // Count number of leaf nodes in T
 //*********************************************************************
 public static int LeafCount(BinaryTree T)
   {
   if (T.IsLeafNode())
     return 1;
   else
     return (LeafCount(T.GetLeft()) + LeafCount(T.GetRight()) );
   };
//******************************************************
// Return InOrder Labelling of n-leaf (2n-1 node) Tree Structure
//******************************************************
 public static BinaryTree LabelTree(BinaryTree T)
   {
   BinaryTree R = new BinaryTree();
   R.SetRootValue(LeafCount(T));
   if (!T.IsLeafNode())
     {
     R.SetLeft(LabelTree(T.GetLeft()));
     R.SetRight(LabelTree(T.GetRight()));
     };
   return R;
   };
 }