More Binary Tree exercises

Binary Tree Node


public class BTNode
{
   char element;
   BTNode left;
   BTNode right;

   public BTNode(){}

   public BTNode(char element)
   {
      this.element = element;
   }

   public BTNode (int element, BTNode left, BTNode right)
   {
      this.element = element;
      this.left = left;
      this.right = right;
   }
}

Binary Tree

Binary Tree Node

public class BTNode
{
   char element;
   BTNode left;
   BTNode right;

   public BTNode(){}

   public BTNode(char element)
   {
      this.element = element;
   }

   public Node (int element, BTNode left, BTNode right)
   {
      this.element = element;
      this.left = left;
      this.right = right;
   }
}

Binary tree traversals.

The next link has a useful tool to visualize preorder,
inorder, postorder, and level order binary tree traversals:

http://nova.umuc.edu/~jarc/idsv/lesson1.html



Preorder traversal: print node element, then visit left and right nodes recursively.


public void preorder(BTNode node)
{
   if (node != null)
   {
      System.out.print(node.element + " ");
      preorder(node.left);
      preorder(node.right);
   }
}

Postorder traversal: visit left and right nodes, then print node element.


public void postorder(BTNode node)
{
   if (node != null)
   {
      postorder(node.left);
      postorder(node.right);
      showNode(node);
   }
}

Inorder traversal: visit left, print node element, visit right.


public void inorder(BTNode node)
{
   BTNode child;
   if(node != null)
   {
      inorder(node.left);
      showNode(node);
      inorder(node.right);
   }
}


Other Binary Tree routines.

isEven returns true if the binary tree has an even number of nodes, otherwise returns false. If the tree is null returns true.


public boolean isEven(BTNode node)
{
   if(node == null)
      return true;
   else if(node.left == null && node.right == null)
      return false;
   else
   return (isEven(node.left) != isEven(node.right));
}



noLeftChildren returns true if the Binary tree has no left children, otherwise returns false.

//Iterative version:

public boolean noLeftChildren(BTNode node)
{
   while(node != null)
   {
      if (node.left != null)
         return false;
      node = node.right;
   }
   return true;

}

//Recursive version

public boolean noLeftChildren(BTNode node)
{
   if (node == null)
      return true;
   else if(node.left != null)
      return false;
   else
   return (noLeftChildren(node.right));
}

fullNodesCount returns the number of full nodes in a binary tree.

public int fullNodesCount( BTNode node)
{
   int counter = 0;
   if (node == null)
      return 0;
   else if (node.left != null && node.right != null)
      counter ++;
   counter += fullNodesCount(node.left);
   counter += fullNodesCount(node.right);
   return counter;
}

A) Given a binary tree of integer elements, write a function which performs a PREORDER traversal. When the function "visits" a node, print out the element.

public void preorder(BTNode node)
{
   if (node != null)
   {
      System.out.print(node.element + " ");
      preorder(node.left);
      preorder(node.right);
   }
}

B) Repeat, but print out the elements only at every other layer, starting from the root. You decide on the appropriate parameters to your function. Also show the initial call to your function.


As an example, this tree:



would result in the following output: 5, 2, 6, 8, 1, 7.


// print must be set to true for the initial call
// to everyOtherPreorder

public void everyOtherPreorder(Node node, boolean print)
{
   if (node != null)
   {
      if(print)
         showNode(node);
      everyOtherPreorder(node.left, !print);
      everyOtherPreorder(node.right, !print);
   }
}

Given a binary tree of integer elements, return a copy of the same tree. Consider what the return value should be if the given tree happens to be NULL.

public Node copyTree(Node T)
{
   if(T == null)
      return null;
   Node left = copyTree(T.left);
   Node right = copyTree(T.right);
   return (new Node(T.element, left, right));
}

Consider these two binary trees, where the first tree consists of identical integer elements:



The problem is: Given a binary tree (but NOT a key x), return TRUE (1) if every node in the tree contains exactly the same element. It does not matter what the value is, just that all values are the same. Otherwise, return FALSE (0). If the tree is empty, return TRUE.

In the example, the function would return TRUE for the first tree, but FALSE for the second tree.

Do not call any other functions, and do not do any type of "counting''.

public class BTree
{
   BTNode root;

   public BTree(){}
   public BTree(int element)
   {
      root = new BTNode(element);
   }

   public boolean allSame(BTNode node)
   {
      if (node != null)
      {
         if (node.element != root.element)
            return false;
         else
            return(allSame(node.left) && allSame(node.right));
         }
   return true;
   }

   //Testing
   public static void main(String args[])
   {
      BTree T = new BTree(5);
      T.root.left = new BTNode(4);
      T.root.right = new BTNode(9);
      T.root.left.left = new BTNode(2);
      T.root.left.right = new BTNode(8);
      T.root.left.left.left = new BTNode(10);
      T.root.left.left.left.left = new BTNode(15);
      T.root.left.left.left.left.left = new BTNode(20);
      T.root.left.left.left.right = new BTNode(6);
      T.root.right.left = new BTNode(1);
      T.root.right.left.right = new BTNode(3);
      T.root.right.left.right.left = new BTNode(7);

      System.out.println("Allsame?: " + T.allSame(T.root));

      BTree T2 = new BTree(5);
      T2.root.left = new BTNode(5);
      T2.root.right = new BTNode(5);
      T2.root.left.left = new BTNode(5);
      T2.root.left.right = new BTNode(5);
      T2.root.left.left.left = new BTNode(5);
      T2.root.left.left.left.left = new BTNode(5);
      T2.root.left.left.left.left.left = new BTNode(5);
      T2.root.left.left.left.right = new BTNode(5);
      T2.root.right.left = new BTNode(5);
      T2.root.right.left.right = new BTNode(5);
      T2.root.right.left.right.left = new BTNode(5);

      System.out.println("Allsame?: " + T2.allSame(T2.root));
   }
}

Write a function which is provided a pointer to the root of a (possibly empty) binary tree, and performs this operation: swap the character element of the given node with the element of the node of the left child. The entire tree should undergo this transformation, starting from the root. Do not move any pointers, just move elements. If the node does not have a left child, then a swap does not occur. Obviously, if the tree is empty, there is nothing to do. Note that the function does not have a return type.
Example of "swap with left":




public void swapWithLeft(BTNode node)
{
   char temp;
   if (node != null)
   {
      if(node.left != null)
      {
         temp = node.element;
         node.element = node.left.element;
         node.left.element = temp;
      }
      swapWithLeft(node.left);
      swapWithLeft(node.right);
   }
}

General Tree - postorder

General Tree Node

public class Node
{
   char element;
   Node firstChild;
   Node nextSibling;

   Node(){}
   Node(char element)
   {
      this.element = element;
   }
}


Postorder visits the root last.
For general tree: do a postorder traversal each of the subtrees of the root one-by-one in the order given; and then visit the root.



public void postorder(Node node)
{
   Node child;
   if(node != null)
   {
      child = node.firstChild;
      if(child != null)
         postorder(child);
      System.out.print(node.element +", ");
      postorder(node.nextSibling);
   }
}

Test:

public static void main(String args[])
{

   GTree T2 = new GTree ('A');
   T2.root.firstChild = new Node('B');
   T2.root.firstChild.nextSibling = new Node('C');
   T2.root.firstChild.nextSibling.nextSibling = new Node('D');
   T2.root.firstChild.firstChild = new Node('E');
   T2.root.firstChild.firstChild.nextSibling = new Node('F');
   T2.root.firstChild.nextSibling.firstChild = new Node('G');

   System.out.println("\n postorder: visit others, then print root");
   T2.postorder(T2.root);
}

Sorting - Heap Sort

int[]H;
int size;
public void constructHeap()
{
int parent, v, child;
boolean heap;
for(int i = size/2; i >= 1; i--)//visit each parent node
{
parent = i;
v = H[parent];
heap = false;
while(!heap && parent * 2 <= size) { child = parent *2; if(child <> H[child])
child++;

if(v >= H[child])
heap = true;
else
{
H[parent] = H[child];
parent = child;
H[parent] = v;
}
}
}
}

public void maxRootDeletion()
{
int lastElement;

for (int i = size; i >=1; i--)
{
lastElement = H[size];
H[size--]= H[1];
H[1] = lastElement;
constructHeap();
}
}

public void heapSort()
{
constructHeap();
maxRootDeletion();
}

Sorting - Merge Sort

public static int[] mergeSort( int[] a)
{
   if (a.length > 1)
   {
      int middle = (a.length/2);
      int[] b = Arrays.copyOfRange(a, 0, middle);// copy a[0...middle-1] to b
      int[] c = Arrays.copyOfRange(a, middle, a.length);//copy a[middle... a.length -1] to c

      b = mergeSort(b);
      c = mergeSort(c);
      a = merge(b,c);
   }
   return a;
}

private static int[] merge(int[] b, int[] c)
{

   int[] merged = new int[b.length + c.length ];
   int i =0, j =0, k =0;
   while (i < b.length && j < c.length)
   {
      if (b[i] <= c[j])
      {
         merged[k]= b[i];
         i++;
      }
      else
      {
         merged[k]= c[j];
         j++;
      }
      k++;
   }
   if (i == b.length)
      System.arraycopy(c, j, merged, k, c.length-j);
   else
      System.arraycopy(b, i, merged, k,b.length-i);
   return merged;
}

//Testing

public static void showArray(int array[])
{
   System.out.print( "Array: [ ");
   for(int i = 0; i < array.length; i++)
      System.out.print(array[i]+ " ");
   System.out.println("]");
}

public static void main(String args[])
{
   int a[]={0,5,3,1,9,8,22,4,7,6,45};
   showArray(a);
   a=mergeSort(a);
   showArray(a);
}

Sorting - Bubble Sort

public int[] bubbleSort(int[] a)
{
   int temp;
   for (int i =0; i < j =" 0;"> a[j+1])
   {
      temp = a[j];
      a[j] = a[j+1];
      a[j+1]= temp;
   }
   return a;
}

Sorting - Selection Sort

public int[] selectionSort(int[] a)
{
   int min,temp;
   for (int i = 0; i < a.length-1; i++)
   {
      min =i;
      for (int j = i+1; j < a.length; j++)
         if (a[j] < a[min])
            min = j;
      temp = a[i];
      a[i] = a[min];
      a[min]= temp;
   }
   return a;
}

Sorting - Insertion Sort

public static int[] insertionSort( int[] a)
{
   int v, j;
   for (int i = 1; i < a.length; i++)
   {
      v = a[i];
      j = i-1;
      while ( j >= 0 && a[j]> v)
            a[j+1]= a[j--];
      a[j+1]=v;
      }
   return a;
}

Sorting - Quick Sort

public static void quickSort(int array[], int left, int right)
{
   int p= partition(array,left, right);
   if (p -1 > left)
      quickSort(array, left, p-1);
   if (p +1 < right)
      quickSort(array, p+1, right);
}

private static int partition(int array[], int left, int right)
{
   if (left >= right)
      return -1;

   int i = left;
   int pivot = array[left];
   int j = right;

   while ( i < j)
   {
      i++;
      while (i < j && array[i]< pivot )
      { i++;}

      while ( j> 0 && array[j]> pivot )
      { j --;}

      swap(array, i,j);
   }
   swap(array, i,j);
   swap(array, left,j);
   return j;
}

private static void swap(int array[], int i,int j)
{
   if (i != j)
   {
      int temp = array[j];
      array[j]= array[i];
      array[i]= temp;
   }
}

//Testing

public static void showArray(int array[])
{
   System.out.print("Array: [");
   for (int i = 0; i < array.length; i++)
      System.out.print(array[i] + " ");
   System.out.println("]");
}

public static void main(String args[])
{
   int array[] = {5,3,1,9,8,2,4,7};
   showArray(array);
   quickSort(array, 0, array.length-1);
   showArray(array);
}