CIS 265 – Lecture Notes – Binary Trees
V. Matos
DRIVER1
package csu.matos;
public class Driver1 {
/**
* GOAL: create a simple binary tree using custom-made linked nodes
* nodes carry Integer numbers
*/
public static void main(String[] args) {
Node<Integer> n1 = new Node<Integer> (58);
Node<Integer> n2 = new Node<Integer> (77);
Node<Integer> n3 = new Node<Integer> (25);
Node<Integer> n4 = new Node<Integer> (12);
Node<Integer> n5 = new Node<Integer> (55);
Node<Integer> n6 = new Node<Integer> (85);
Node<Integer> n7 = new Node<Integer> (80);
Node<Integer> n8 = new Node<Integer> (90);
Node<Integer> n9 = new Node<Integer> (40);
// System.out.println ( n1.showNode() );
// System.out.println ( n2.showNode() );
// System.out.println ( n3.showNode() );
Tree<Integer> tree = new Tree<Integer>();
tree.add(n1);
tree.add(n2);
tree.add(n3);
tree.add(n4);
tree.add(n5);
tree.add(n6);
tree.add(n7);
tree.add(n8);
tree.add(n9);
tree.preorder();
Node<Integer> ptr = tree.findNode(77);
System.out.println ( ptr.getData() + " is at: " + ptr );
tree.bfs();
System.out.println ( "Rightmost " + tree.findRightmostLeft(tree.getRoot()).showNode() );
System.out.println ( " Rightmost 77 is " + tree.findRightmostLeft(ptr) );
//tree.delete(tree.getRoot());
ptr = tree.findNode(85);
tree.delete(ptr);
tree.bfs();
}//main
}
Node Class
package csu.matos;
public class Node<E extends Comparable<E> implements Comparable<Node<E> {
E data;
Node<E> left;
Node<E> right;
public Node(E data) {
this.data = data;
this.left = null;
this.right = null;
}
public E getData() {
return data;
}
public void setData(E data) {
this.data = data;
}
public Node<E> getLeft() {
return left;
}
public void setLeft(Node<E> left) {
this.left = left;
}
public Node<E> getRight() {
return right;
}
public void setRight(Node<E> right) {
this.right = right;
}
// ------
public String showNode() {
return "\n\tData: " + this.getData()
+ "\n\tLocation: " + this
+ "\n\t Left: " + this.getLeft()
+ "\n\t Right: " + this.getRight();
}
public String ShowNodeLess() {
return "\tData: " + this.getData()
+ "\tLoc: " + nodeAddress(this)
+ "\t Left: " + nodeAddress(this.getLeft())
+ "\t Right: " + nodeAddress(this.getRight());
}
@Override
public int compareTo(Node<E> otherNode) {
return this.compareTo(otherNode);
}
private String nodeAddress(Node<E> ptr) {
if (ptr == null)
return "null ";
else {
String result = ptr.toString();
return result.substring(result.indexOf('@'));
}
}
}
Tree Class
package csu.matos;
import java.util.LinkedList;
import java.util.Queue;
public class Tree<E extends Comparable<E> {
Node<E> root;
//------
public Tree () {
root = null;
}
//------
public Node<E> getRoot() {
return root;
}
public void setRoot(Node<E> root) {
this.root = root;
}
// ------
public Node<E> findNode ( E data){
// locate a node containing given E-type data
Node<E> current = root;
while ( current != null ){
if ( current.getData().compareTo(data) == 0)
return current;
if ( current.getData().compareTo(data) > 0)
current = current.getLeft();
else
current = current.getRight();
}
return current;
}
// ------
public void add (Node<E> newNode){
if ( root == null ){
root = newNode;
return;
}
Node<E> current = root;
Node<E> parent = null;
boolean leftChild = false;
while ( current != null ){
if ( current.getData().compareTo(newNode.getData()) > 0){
parent = current;
current = current.getLeft();
leftChild = true;
}
else {
parent = current;
current = current.getRight();
leftChild = false;
}
}
if ( leftChild){
parent.setLeft(newNode);
}
else {
parent.setRight(newNode);
}
}
// ------
public void preorder() {
preorder(root);
}
public void preorder(Node<E> ptr) {
if (ptr == null)
return;
System.out.println ( ptr.ShowNodeLess() );
preorder(ptr.getLeft());
preorder(ptr.getRight());
}
//------
public void bfs() {
Queue<Node<E> queue = new LinkedList<Node<E> >();
queue.clear();
queue.add(root);
Node<E> current;
while ( ! queue.isEmpty() ){
current = queue.remove();
if ( current != null) {
System.out.println ( current.ShowNodeLess() );
queue.add(current.getLeft());
queue.add(current.getRight());
}
}
}//bfs
// ------
public Node<E> findRightmostLeft(Node<E> ptr) {
if ( ptr == null )
return null;
Node<E> current = ptr.getLeft();
Node<E> parent = ptr;
while ( current != null & current.getRight() != null ){
System.out.println ("debug current" + current.ShowNodeLess()
+ "\tparent:" + parent.ShowNodeLess());
parent = current;
current = current.getRight();
}
return current;
}
private Node<E> findParent (Node<E> childNode){
Node<E> ptr = root;
Node<E> parent = null;
while ( ptr != null ){
if ( ptr == childNode)
break;
parent = ptr;
if ( ptr.getData().compareTo(childNode.getData())> 0)
ptr = ptr.getLeft();
else
ptr = ptr.getRight();
}
return parent;
}
public void delete(Node<E> node2Delete) {
Node<E> rightmost = findRightmostLeft(node2Delete);
Node<E> parent;
if ( rightmost != null ){
parent = findParent( rightmost );
node2Delete.setData( rightmost.getData() );
parent.setRight( rightmost.getLeft() );
}
else {
parent = findParent( node2Delete );
if ( parent.getLeft() == node2Delete ){
parent.setLeft( node2Delete.getRight() );
}
else {
parent.setRight( node2Delete.getRight() );
}
}
System.gc();
}
}
Person class
package csu.matos;
public class Person implements Comparable<Person> {
String name;
int phone;
public Person(String name, int phone) {
super();
this.name = name;
this.phone = phone;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getPhone() {
return phone;
}
public void setPhone(int phone) {
this.phone = phone;
}
///////////////////////////////////////
public String toString() {
return " Name:" + name + " Phone:" + phone;
}
@Override
public int compareTo(Person otherPerson) {
if (this.phone == otherPerson.getPhone())
return 0;
else if (this.phone > otherPerson.getPhone())
return 1;
else
return -1;
}
}
Driver2
package csu.matos;
public class Driver2 {
/**
* Goal: testing the custom-made Tree class holding Person nodes
*/
public static void main(String[] args) {
Tree<Person> tree = new Tree<Person>();
Person p1 = new Person("AAA", 555);
System.out.println ( "p1 > " + p1);
tree.add(new Node<Person>( new Person("AAA", 555) ));
tree.add(new Node<Person>( new Person("BBB", 333) ));
tree.add(new Node<Person>( new Person("CCC", 777) ));
tree.add(new Node<Person>( new Person("DDD", 222) ));
tree.add(new Node<Person>( new Person("EEE", 111) ));
tree.add(new Node<Person>( new Person("FFF", 888) ));
tree.add(new Node<Person>( new Person("GGG", 444) ));
tree.preorder();
Person p2 = new Person("CCC", 777);
Node<Person> nodePtr = tree.findNode( p2 );
System.out.println( " p2: " + p2.toString() + "\n p2 is at: " + nodePtr);
//tree.delete( new Node<Person> (new Person("AAA", 555)) );
tree.delete ( nodePtr );
tree.preorder();
}
}
Console – Running Driver1
Data: 58 Loc: @2f9ee1ac Left: @67f1fba0 Right: @3fbefab0
Data: 25 Loc: @67f1fba0 Left: @133c5982 Right: @5f186fab
Data: 12 Loc: @133c5982 Left: null Right: null
Data: 55 Loc: @5f186fab Left: @3d4b7453 Right: null
Data: 40 Loc: @3d4b7453 Left: null Right: null
Data: 77 Loc: @3fbefab0 Left: null Right: @24c21495
Data: 85 Loc: @24c21495 Left: @41d5550d Right: @1cc2ea3f
Data: 80 Loc: @41d5550d Left: null Right: null
Data: 90 Loc: @1cc2ea3f Left: null Right: null
77 is at: csu.matos.Node@3fbefab0
Data: 58 Loc: @2f9ee1ac Left: @67f1fba0 Right: @3fbefab0
Data: 25 Loc: @67f1fba0 Left: @133c5982 Right: @5f186fab
Data: 77 Loc: @3fbefab0 Left: null Right: @24c21495
Data: 12 Loc: @133c5982 Left: null Right: null
Data: 55 Loc: @5f186fab Left: @3d4b7453 Right: null
Data: 85 Loc: @24c21495 Left: @41d5550d Right: @1cc2ea3f
Data: 40 Loc: @3d4b7453 Left: null Right: null
Data: 80 Loc: @41d5550d Left: null Right: null
Data: 90 Loc: @1cc2ea3f Left: null Right: null
debug current Data: 25 Loc: @67f1fba0 Left: @133c5982 Right: @5f186fab parent: Data: 58 Loc: @2f9ee1ac Left: @67f1fba0 Right: @3fbefab0
Rightmost
Data: 55
Location: csu.matos.Node@5f186fab
Left: csu.matos.Node@3d4b7453
Right: null
Rightmost 77 is null
Data: 58 Loc: @2f9ee1ac Left: @67f1fba0 Right: @3fbefab0
Data: 25 Loc: @67f1fba0 Left: @133c5982 Right: @5f186fab
Data: 77 Loc: @3fbefab0 Left: null Right: @24c21495
Data: 12 Loc: @133c5982 Left: null Right: null
Data: 55 Loc: @5f186fab Left: @3d4b7453 Right: null
Data: 80 Loc: @24c21495 Left: @41d5550d Right: null
Data: 40 Loc: @3d4b7453 Left: null Right: null
Data: 80 Loc: @41d5550d Left: null Right: null
Console – Running Driver2
p1 > Name:AAA Phone:555
Data: Name:AAA Phone:555 Loc: @67f1fba0 Left: @3fbefab0 Right: @133c5982
Data: Name:BBB Phone:333 Loc: @3fbefab0 Left: @5f186fab Right: @3d4b7453
Data: Name:DDD Phone:222 Loc: @5f186fab Left: @24c21495 Right: null
Data: Name:EEE Phone:111 Loc: @24c21495 Left: null Right: null
Data: Name:GGG Phone:444 Loc: @3d4b7453 Left: null Right: null
Data: Name:CCC Phone:777 Loc: @133c5982 Left: null Right: @41d5550d
Data: Name:FFF Phone:888 Loc: @41d5550d Left: null Right: null
p2: Name:CCC Phone:777
p2 is at: csu.matos.Node@133c5982
Data: Name:AAA Phone:555 Loc: @67f1fba0 Left: @3fbefab0 Right: @41d5550d
Data: Name:BBB Phone:333 Loc: @3fbefab0 Left: @5f186fab Right: @3d4b7453
Data: Name:DDD Phone:222 Loc: @5f186fab Left: @24c21495 Right: null
Data: Name:EEE Phone:111 Loc: @24c21495 Left: null Right: null
Data: Name:GGG Phone:444 Loc: @3d4b7453 Left: null Right: null
Data: Name:FFF Phone:888 Loc: @41d5550d Left: null Right: null