Binary Search Trees 2

To Compare Objects of the same class ( needed to add to tree)
1. Steps
  1. Define own class e.g. Student
  2. Implement Comparable interface
  3. Provide an implementation of interface method 'compareTo' in own class (criteria on which to compare) (e.g. age)
    1. returns 0 if equal, returns 1 if current obj is > than argument obj,returns -1 if current obj is < than argument obj
  4. to sort a list:
    1. add objects to an arrayList in PVSM: e.g. students
    2. invoke Collection.sort(students) to sort the collection ArrayList
implementation
1. int size(), int size(BTNode<T> current
  1. uses recursion size(root)
    1. IF current == null returns 0 (base) ELSE returns (1 + size(left-child node) + size(right-child node)
2. create BinaryTree interface
3. create BinarySearchTree class that implements BinaryTree interface
4. create BTNode
5. create BTTest
6. T findMin(), T findMin(BTNode<T> current)
  1. uses recursion findMin(root)
    1. if (current.left == null) return current.element; else return findMin(current.left);
      1. always go left due to ordered structure as min value will be the last left node (down tru' left nodes until no left child)
  2. non recursive method: while (current.left != null) { current = current.left; } return current.element;
7. T findMax(), T findMax(BTNode<T> current)
  1. uses recursion findMax(root)
    1. if (current.right == null) return current.element; else return findMax(current.right);
      1. always go right due to ordered structure as max value will be the last right node (down tru' right nodes until no right child)
  2. non recursive method: while (current.right != null) { current = current.right; } return current.element;

Next up

Binary Search Trees 2

Description

Resource summary

0 comments

Similar

	Created by Eithne O'Sullivan over 7 years ago