User:Tendy-bear
DATA STRUCTURES BINARY TREE
1 Create a basic binary search tree class. At this point, you will only need a basic constructor method that initializes the node's value and an insert method. The insert method will traverse a tree and make a new node in the right place. ""public class BinaryTree { BinaryTree left; BinaryTree right; int value;
public BinaryTree(int v) { value = v; }
// Insert a value into the tree public void insert(int v) { if(v < value) { if(left == null) left = new BinaryTree(v); else left.insert(v); }
else if(v > value) { if(right == null) right = new BinaryTree(v); else right.insert(v); } } }"" Step2 Create the instance (node) of the binary tree that will be the root node. Like any other node, the root node needs to have a value. It's usually best to choose a value close to the median of the objects you're storing, as binary trees should be as balanced as possible. ""BinaryTree b = new BinaryTree(50);"" Step3 Insert nodes into the tree in specific order to retain balance, as this binary tree isn't auto-balancing. This example creates the smallest tree possible in order to maintain efficiency.""b.insert(20); b.insert(40); b.insert(10); b.insert(5); b.insert(45);
b.insert(70); b.insert(60); b.insert(80); b.insert(55); b.insert(85);"" Step4 Move across the tree using an inorder traversal. The left tree is traversed first, followed by the root node, and then the right tree is traversed. Using recursion, the code is merely three lines. However, since recursion takes stack space, it should be used carefully. With a small and balanced binary tree, recursion won't overflow the stack. Step5 Add a new method to the Java BinaryTree class called inorder. ""public void inorder() { if(left != null) left.inorder(); System.out.println(value); if(right != null) right.inorder(); }"" Step6 Call the inorder method after your inserts to print the nodes in sorted order.""b.inorder();"
INoRDER
public class BinaryTreeTest {
public static void main(String[] args) {
new BinaryTreeTest().run();
}
static class Node {
Node left;
Node right;
int value;
public Node(int value) {
this.value = value;
}
}
public void run() {
// build the simple tree from chapter 11.
Node root = new Node(5);
System.out.println("Binary Tree Example");
System.out.println("Building tree with root value " + root.value);
insert(root, 1);
insert(root, 8);
insert(root, 6);
insert(root, 3);
insert(root, 9);
System.out.println("Traversing tree in order");
printInOrder(root);
System.out.println("Traversing tree front-to-back from location 7");
printFrontToBack(root, 7);
}
public void insert(Node node, int value) {
if (value < node.value) {
if (node.left != null) {
insert(node.left, value);
} else {
System.out.println(" Inserted " + value + " to left of "
+ node.value);
node.left = new Node(value);
}
} else if (value > node.value) {
if (node.right != null) {
insert(node.right, value);
} else {
System.out.println(" Inserted " + value + " to right of "
+ node.value);
node.right = new Node(value);
}
}
}
public void printInOrder(Node node) {
if (node != null) {
printInOrder(node.left);
System.out.println(" Traversed " + node.value);
printInOrder(node.right);
}
}
/**
* uses in-order traversal when the origin is less than the node's value
*
* uses reverse-order traversal when the origin is greater than the node's
* order
*/
public void printFrontToBack(Node node, int camera) {
if (node == null)
return;
if (node.value > camera) {
// print in order
printFrontToBack(node.left, camera);
System.out.println(" Traversed " + node.value);
printFrontToBack(node.right, camera);
} else if (node.value < camera) {
// print reverse order
printFrontToBack(node.right, camera);
System.out.println(" Traversed " + node.value);
printFrontToBack(node.left, camera);
} else {
// order doesn't matter
printFrontToBack(node.left, camera);
printFrontToBack(node.right, camera);
}
}
}
COMPLETE
/** BinTree.java
* Binary Tree * j.g.c. 3/11/00, from A.McC * see also Weiss p. 115 */
import java.util.*; import java.text.*; import java.io.*;
public class BinTree {
private Node root;
public BinTree() {
root = null;
}
public boolean isEmpty() {
return root==null;
}
public void clear() {
root=null;
}
public void insert(Comparable e) {
root = insert(e,root);
}
public void remove(Comparable e) {
root = remove(e,root);
}
private Node remove(Comparable e, Node n) {
if (n == null) return n; // empty tree so nothing to remove
else if(e.compareTo(n.data) < 0) {
// search for e in left sub-tree. Set left-sub tree to
// result of recursive call to delete from left-subtree
n.left= remove(e, n.left);
}
else if (e.compareTo(n.data) > 0) {
// search for e in right sub-tree. Set right-sub tree to
// result of recursive call to delete from right-subtree
n.right= remove(e, n.right);
}
else if (n.left != null && n.right != null) {
// n refers to node to be deleted and it has no null children
// find the in-order successor, disconnect it and return its
// data value, setting this as the new data element of n
n.data = disconnectSucc(n);
} else if (n.left == null) {
// n refers to node to be deleted and its left child is
// null so set n to refer to right child
n = n.right;
} else {
// n refers to node to be deleted and its left child
// is not null so set n to refer to left child
n = n.left;
}
return n;
}
boolean find(Comparable e) {
return find(e,root);
}
public void displayInOrder() {
displayInOrder(root);
System.out.println();
}
public void displayPreOrder() {
displayPreOrder(root);
System.out.println();
}
public void displayPostOrder() {
displayPostOrder(root);
System.out.println();
}
private Comparable disconnectSucc(Node n) {
Node succParent = n;
Node succ = n;
Node curr = n.right;
// locate successor
while (curr != null) {
succParent = succ;
succ = curr;
curr = curr.left;
}
// test if successor is right child of its parent node
if (succ == succParent.right) {
// set right child of parent to right child of successor
succParent.right = succ.right;
} else {
// set left child of parent to right child of successor
succParent.left = succ.right;
}
return succ.data;
}
private Node insert(Comparable e, Node n) {
if (n == null) n = new Node(e,null,null);
else if (e.compareTo(n.data) < 0) n.left= insert(e, n.left);
else if (e.compareTo(n.data) > 0) n.right= insert(e, n.right);
return n;
}
private boolean find(Comparable e, Node n) {
if (n == null) return false;
else if (e.compareTo(n.data) == 0) return true;
else if (e.compareTo(n.data) < 0) return find(e, n.left);
else return find(e,n.right);
}
private void displayInOrder(Node n) {
if (n!=null){
displayInOrder(n.left);
System.out.print(n.data+" ");
displayInOrder(n.right);
}
}
private void displayPostOrder(Node n) {
if (n!=null) {
displayPostOrder(n.left);
displayPostOrder(n.right);
System.out.print(n.data+" ");
}
}
private void displayPreOrder(Node n) {
if (n!=null) {
System.out.print(n.data+" ");
displayPreOrder(n.left);
displayPreOrder(n.right);
}
}
private class Node {
public Comparable data;
public Node left;
public Node right;
public Node() {
this(null, null, null);
}
public Node(Comparable e) {
this(e, null, null);
}
public Node(Comparable e, Node leftn, Node rightn) {
data = e;
left = leftn;
right = rightn;
}
public String toString() {
String s= new String("("+data+")");
return s;
}
}
} // end of class BinTree
13.2.0.0.2 Exercising Program
/* ---BinTreeT.java
j.g.c. 3/11/00 exercises BinTree */
import java.util.*; import java.text.*; import java.io.*;
public class BinTreeT{
public static void main(String[] arg) {
BinTree t = new BinTree(); int ele, n= 10; int a[]= new int[n]; long rseed= 139; Random rand = new Random(rseed); PrintStream out= System.out;
int r;
for (int i = 0; i < n; i++){
r= rand.nextInt(100);
t.insert(new Integer(r));
a[i]= r;
}
out.println("Values in order of insertion: ");
Arrays.println(a);
out.println("Tree, in-order: ");
t.displayInOrder();
out.println("Tree, post-order: ");
t.displayPostOrder();
out.println("Tree, pre-order: ");
t.displayPreOrder();
}
}
LAPORAN MINGGU KEMAREN
// BinarySearchTree class // // CONSTRUCTION: with no initializer // // ******************PUBLIC OPERATIONS********************* // void insert( x ) --> Insert x // void remove( x ) --> Remove x // void removeMin( ) --> Remove minimum item // Comparable find( x ) --> Return item that matches x // Comparable findMin( ) --> Return smallest item // Comparable findMax( ) --> Return largest item // boolean isEmpty( ) --> Return true if empty; else false // void makeEmpty( ) --> Remove all items // ******************ERRORS******************************** // Exceptions are thrown by insert, remove, and removeMin if warranted
/**
* Implements an unbalanced binary search tree. * Note that all "matching" is based on the compareTo method. * @author Mark Allen Weiss */
public class BinarySearchTree {
/**
* Construct the tree.
*/
public BinarySearchTree( ) {
root = null;
}
/**
* Insert into the tree.
* @param x the item to insert.
* @throws DuplicateItemException if x is already present.
*/
public void insert( Comparable x ) {
root = insert( x, root );
}
/**
* Remove from the tree..
* @param x the item to remove.
* @throws ItemNotFoundException if x is not found.
*/
public void remove( Comparable x ) {
root = remove( x, root );
}
/**
* Remove minimum item from the tree.
* @throws ItemNotFoundException if tree is empty.
*/
public void removeMin( ) {
root = removeMin( root );
}
/**
* Find the smallest item in the tree.
* @return smallest item or null if empty.
*/
public Comparable findMin( ) {
return elementAt( findMin( root ) );
}
/**
* Find the largest item in the tree.
* @return the largest item or null if empty.
*/
public Comparable findMax( ) {
return elementAt( findMax( root ) );
}
/**
* Find an item in the tree.
* @param x the item to search for.
* @return the matching item or null if not found.
*/
public Comparable find( Comparable x ) {
return elementAt( find( x, root ) );
}
/**
* Make the tree logically empty.
*/
public void makeEmpty( ) {
root = null;
}
/**
* Test if the tree is logically empty.
* @return true if empty, false otherwise.
*/
public boolean isEmpty( ) {
return root == null;
}
/**
* Internal method to get element field.
* @param t the node.
* @return the element field or null if t is null.
*/
private Comparable elementAt( BinaryNode t ) {
return t == null ? null : t.element;
}
/**
* Internal method to insert into a subtree.
* @param x the item to insert.
* @param t the node that roots the tree.
* @return the new root.
* @throws DuplicateItemException if x is already present.
*/
protected BinaryNode insert( Comparable x, BinaryNode t ) {
if( t == null )
t = new BinaryNode( x );
else if( x.compareTo( t.element ) < 0 )
t.left = insert( x, t.left );
else if( x.compareTo( t.element ) > 0 )
t.right = insert( x, t.right );
else
throw new DuplicateItemException( x.toString( ) ); // Duplicate
return t;
}
/**
* Internal method to remove from a subtree.
* @param x the item to remove.
* @param t the node that roots the tree.
* @return the new root.
* @throws ItemNotFoundException if x is not found.
*/
protected BinaryNode remove( Comparable x, BinaryNode t ) {
if( t == null )
throw new ItemNotFoundException( x.toString( ) );
if( x.compareTo( t.element ) < 0 )
t.left = remove( x, t.left );
else if( x.compareTo( t.element ) > 0 )
t.right = remove( x, t.right );
else if( t.left != null && t.right != null ) // Two children
{
t.element = findMin( t.right ).element;
t.right = removeMin( t.right );
} else
t = ( t.left != null ) ? t.left : t.right;
return t;
}
/**
* Internal method to remove minimum item from a subtree.
* @param t the node that roots the tree.
* @return the new root.
* @throws ItemNotFoundException if x is not found.
*/
protected BinaryNode removeMin( BinaryNode t ) {
if( t == null )
throw new ItemNotFoundException( );
else if( t.left != null ) {
t.left = removeMin( t.left );
return t;
} else
return t.right;
}
/**
* Internal method to find the smallest item in a subtree.
* @param t the node that roots the tree.
* @return node containing the smallest item.
*/
protected BinaryNode findMin( BinaryNode t ) {
if( t != null )
while( t.left != null )
t = t.left;
return t;
}
/**
* Internal method to find the largest item in a subtree.
* @param t the node that roots the tree.
* @return node containing the largest item.
*/
private BinaryNode findMax( BinaryNode t ) {
if( t != null )
while( t.right != null )
t = t.right;
return t;
}
/**
* Internal method to find an item in a subtree.
* @param x is item to search for.
* @param t the node that roots the tree.
* @return node containing the matched item.
*/
private BinaryNode find( Comparable x, BinaryNode t ) {
while( t != null ) {
if( x.compareTo( t.element ) < 0 )
t = t.left;
else if( x.compareTo( t.element ) > 0 )
t = t.right;
else
return t; // Match
}
return null; // Not found
}
/** The tree root. */
protected BinaryNode root;
// Test program
public static void main( String [ ] args ) {
BinarySearchTree t = new BinarySearchTree( );
final int NUMS = 4000;
final int GAP = 37;
System.out.println( "Checking... (no more output means success)" );
for( int i = GAP; i != 0; i = ( i + GAP ) % NUMS )
t.insert( new Integer( i ) );
for( int i = 1; i < NUMS; i+= 2 )
t.remove( new Integer( i ) );
if( ((Integer)(t.findMin( ))).intValue( ) != 2 ||
((Integer)(t.findMax( ))).intValue( ) != NUMS - 2 )
System.out.println( "FindMin or FindMax error!" );
for( int i = 2; i < NUMS; i+=2 )
if( ((Integer)(t.find( new Integer( i ) ))).intValue( ) != i )
System.out.println( "Find error1!" );
for( int i = 1; i < NUMS; i+=2 ) {
if( t.find( new Integer( i ) ) != null )
System.out.println( "Find error2!" );
}
}
}
// Basic node stored in unbalanced binary search trees
// Note that this class is not accessible outside
// of this package.
class BinaryNode {
// Constructors
BinaryNode( Comparable theElement ) {
element = theElement;
left = right = null;
}
// Friendly data; accessible by other package routines
Comparable element; // The data in the node
BinaryNode left; // Left child
BinaryNode right; // Right child
}
/**
* Exception class for duplicate item errors * in search tree insertions. * @author Mark Allen Weiss */
public class DuplicateItemException extends RuntimeException {
/**
* Construct this exception object.
*/
public DuplicateItemException( ) {
super( );
}
/**
* Construct this exception object.
* @param message the error message.
*/
public DuplicateItemException( String message ) {
super( message );
}
}
/**
* Exception class for failed finds/removes in search * trees, hash tables, and list and tree iterators. * @author Mark Allen Weiss */
public class ItemNotFoundException extends RuntimeException {
/**
* Construct this exception object.
*/
public ItemNotFoundException( ) {
super( );
}
/**
* Construct this exception object.
* @param message the error message.
*/
public ItemNotFoundException( String message ) {
super( message );
}
}