Zusammenfassung der Ressource
Binary Search Trees 2
- 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
- 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;