Binary Tree Help
Hi, how do i create a Binary Tree using nodes and stacks? I've created a stack interface, and a full and empty exception class but i'm now creating the TreeStack class to create the tree. It uses 3 complete levels, therfore 7 nodes and 7 stacks. Each stack limit is going to be set to maximum 10. I've created the methods and the arrays i think i'll need but i'm not sure how to create the tree itself. Here's the code i have done:
Stack.java:
public interface Stack {
// accessor methods
public int size(); //# return the number of elements stored in the stack
public boolean isEmpty(); //# test whether the stack is empty
public Object top() //# return the top elemet
throws StackEmptyException; //# thrown if called on an empty stack
// update methods
public void push (Object element); //# insert an element onto the stack
public Object pop() //# return and remove the top element of the stack
throws StackEmptyException; //# thrown if called on an empty stack
}
StackEmptyException.java:
public class StackEmptyException extends RuntimeException {
public StackEmptyException(String err) {
super(err);
}
}
StackFullException.java:
public class StackFullException extends RuntimeException {
public StackFullException(String err) {
super(err);
}
}
TreeStack.java
public class TreeStack{
// Create Arrays
// Max nodes needed is 7 (3 complete levels)
BinaryTreeNodes[] bn = new BinaryTreeNodes[7];
// Max stacks needed is 7 (3 complete levels)
BinaryTreeStack[] bs = new BinaryTreeStack[7];
// At each node a stack is created as required
// i.e. the data structure is a tree of stacks.
// Each stack only need to have a maximum capacity of 10.
// Create Binary Tree
BinaryTree[] b = new BinaryTree();
public void input(){
// Get user input
public void printLevelOrder(){
}
public void printPopLevelOrder(){
}
public void printPopInorder(){
}
public void printPopPrerder(){
}
public void printPopRoot(){
}
When attempting to run the program i want it to run by entering input like this:
java TreeStack
1 3 2 printLevelOrder printPopRoot
CONTROL-D (i.e. end of file)
Any help is much appreciated or if anyone knows where i can read up on this topic.
Thanks.
# 2 Re: Binary Tree Help
I have created a Binary Tree Node class.. It doesnt use stacks at each node, but I suppose you could alter it to do so...
public class BTNode
{
private Object data;
private BTNode left, right;
public BTNode(Object initialData, BTNode initialLeft, BTNode initialRight)
{
data = initialData;
left = initialLeft;
right = initialRight;
}
public BTNode()
{ this(null, null, null); }
public BTNode(Object newdata)
{ this(newdata, null, null); }
//NODE methods
public Object getData() //return and set data in node
{return data;}
public void setData(Object data)
{this.data = data; }
public BTNode getLeft() //return and set left child
{return left; }
public void setLeft(BTNode left)
{this.left = left; }
public BTNode getRight() //return and set right child
{return right; }
public void setRight(BTNode right)
{this.right = right; }
public boolean isLeaf() //return true if this is leaf node
{return (left == null)&&(right == null); }
// TREE Methods - for tree starting at this node
// get specific data from a tree
public Object getLeftmostData()
{ if(left == null)
return data;
else
return left.getLeftmostData(); }
public Object getRightmostData()
{ if(right == null)
return data;
else
return right.getRightmostData(); }
// print data in a tree
public void inorderPrint()
{
if (left != null)
left.inorderPrint( );
System.out.print(data+"\t");
if (right != null)
right.inorderPrint( ); }
public void preorderPrint()
{
System.out.print(data+"\t");
if (left != null)
left.preorderPrint( );
if (right != null)
right.preorderPrint( ); }
public void postorderPrint()
{
if (left != null)
left.postorderPrint( );
if (right != null)
right.postorderPrint( );
System.out.print(data+"\t"); }
// pretty print a tree
//public void print(int depth);
//Interface for Nodes in Binary Tree (3)
//removing nodes from a tree
//returns reference to tree after removal of node
public BTNode removeLeftmost()
{
if (left == null) // we are as deep as we can get
return right; // remove this node by returning right subt ree
else
{ // keep going down recursively
left = left.removeLeftmost( );
// when done, return node that act ivated this
// method as root of t ree
return this; }}
public BTNode removeRightmost()
{
if (right == null) // we are as deep as we can get
return left; // remove this node by returning left subt ree
else
{ // keep going down recursively
right = right.removeRightmost( );
// when done, return node that activated this
// method as root of tree
return this; }}
//returns number of nodes in tree
public static long treeHeight(BTNode root)
{
if (root == null)
return -1;
else
return 1 + Math.max(treeHeight(root.left),
treeHeight(root.right));
}
public static long treeSize(BTNode root)
{
if (root == null)
return 0;
else
return 1 + treeSize(root.left) + treeSize(root.right);
}
//copying a tree: returns reference to root of copy
// public BTNode treeCopy(BTNode root);
public static BTNode insertNode(BTNode root, int key){
if (root == null) // null tree, so create node at root
return new BTNode(new Integer(key));
Integer data_element = (Integer) root.data;
if (key <= data_element.intValue())
root.setLeft(insertNode(root.left, key));
else root.setRight(insertNode(root.right, key));
return root; }
public static BTNode findNode(BTNode root,int key){
if (root == null)
return null; // null tree
Integer data_element = (Integer) root.data;
if (key == data_element.intValue())
return root;
else
if (key <= data_element.intValue())
return findNode(root.left, key);
else return findNode(root.right, key); }
public static BTNode removeNode(BTNode root, int key){
if (root == null) return null;
Integer data_element = (Integer) root.data;
if (key < data_element.intValue())
root.setLeft(removeNode(root.left, key));
else if (key > data_element.intValue())
root.setRight(removeNode(root.right,key));
else { // found it
if (root.right == null) root = root.left;
else if (root.left == null) root = root.right;
else { //two children
Integer temp = (Integer)
root.left.getRightmostData();
root.setData(temp);
root.setLeft(root.left.removeRightmost());
}
}
return root; }
public static BTNode copyTree(BTNode bt){
if (bt==null) return null;
BTNode left=copyTree(bt.left);
BTNode right=copyTree(bt.right);
return new BTNode(bt.data,left,right); }
}