Binary Search Trees 2

Binary Search Trees 2

1. To Compare Objects of the same class ( needed to add to tree)

   • Steps
     • Define own class e.g. Student
     • Implement Comparable interface
     • Provide an implementation of interface method 'compareTo' in own class (criteria on which to compare) (e.g. age)
       • returns 0 if equal, returns 1 if current obj is > than argument obj,returns -1 if current obj is < than argument obj
     • to sort a list:
       • add objects to an arrayList in PVSM: e.g. students
       • invoke Collection.sort(students) to sort the collection ArrayList

2. implementation

   • int size(), int size(BTNode<T> current
     • uses recursion size(root)
       • IF current == null returns 0 (base) ELSE returns (1 + size(left-child node) + size(right-child node)
   • create BinaryTree interface
   • create BinarySearchTree class that implements BinaryTree interface
   • create BTNode
   • create BTTest
   • T findMin(), T findMin(BTNode<T> current)
     • uses recursion findMin(root)
       • if (current.left == null) return current.element; else return findMin(current.left);
         • always go left due to ordered structure as min value will be the last left node (down tru' left nodes until no left child)
     • non recursive method: while (current.left != null) { current = current.left; } return current.element;
   • T findMax(), T findMax(BTNode<T> current)
     • uses recursion findMax(root)
       • if (current.right == null) return current.element; else return findMax(current.right);
         • always go right due to ordered structure as max value will be the last right node (down tru' right nodes until no right child)
     • non recursive method: while (current.right != null) { current = current.right; } return current.element;