I need to develop a graphical representation of a balanced binary tree using random numbers from an array with the number of elements entered by the user. That part I got down and it is working fine. The next part of the assignment requires me to display the number of leaves, height and width of the tree, total number of nodes, and nodes w/ one child. This is where I am having a problem and it may be just a fundamental lack of Java structure. I am getting caught up in private and public classes and methods...
Where in my code do I need to place methods for each of the above things so that I can make a call and return a value to display in the proper text fields? I attempted to do so with height, but am getting crazy numbers for a height. Any advise would be greatly appreciated!!!
import java.util.*;
import java.awt.*;
import java.awt.event.*;
import javax.swing.*;
import java.util.Random;
public class AVLTreeDemo extends JFrame
implements ActionListener
{
private AVLTree avlTree = new AVLTree();
private JLabel cmdResultLabel, cmdResultLabel2, cmdResultLabel3, cmdResultLabel4, cmdResultLabel5, cmdResultLabel6, cmdResultLabel7, cmdResultLabel8;
private JTextField cmdResultTextField, cmdResultTextField2, cmdResultTextField3, cmdResultTextField4, cmdResultTextField5, cmdResultTextField6, cmdResultTextField7, cmdResultTextField8;
private JLabel cmdLabel;
private JTextField cmdTextField;
public AVLTreeDemo()
{
setTitle("Balanced Binary Tree");
JPanel resultPanel = new JPanel (new GridLayout(2,8));
cmdResultLabel = new JLabel("Width of the Tree: ");
cmdResultLabel2 = new JLabel("Nodes With One Child: ");
cmdResultLabel3 = new JLabel("Total Number of Nodes: ");
cmdResultLabel4 = new JLabel("Height of the Tree: ");
cmdResultLabel5 = new JLabel("Number of Leaves: ");
cmdResultLabel6 = new JLabel("PreOrder: ");
cmdResultLabel7 = new JLabel("InOrder: ");
cmdResultLabel8 = new JLabel("PostOrder ");
cmdResultTextField = new JTextField();
cmdResultTextField2 = new JTextField();
cmdResultTextField3 = new JTextField();
cmdResultTextField4 = new JTextField();
cmdResultTextField5 = new JTextField();
cmdResultTextField6 = new JTextField();
cmdResultTextField7 = new JTextField();
cmdResultTextField8 = new JTextField();
resultPanel.add(cmdResultLabel);
resultPanel.add(cmdResultLabel2);
resultPanel.add(cmdResultLabel3);
resultPanel.add(cmdResultLabel4);
resultPanel.add(cmdResultLabel5);
resultPanel.add(cmdResultLabel6);
resultPanel.add(cmdResultLabel7);
resultPanel.add(cmdResultLabel8);
resultPanel.add(cmdResultTextField);
resultPanel.add(cmdResultTextField2);
resultPanel.add(cmdResultTextField3);
resultPanel.add(cmdResultTextField4);
resultPanel.add(cmdResultTextField5);
resultPanel.add(cmdResultTextField6);
resultPanel.add(cmdResultTextField7);
resultPanel.add(cmdResultTextField8);
cmdResultTextField.setEditable(false);
cmdResultTextField2.setEditable(false);
cmdResultTextField3.setEditable(false);
cmdResultTextField4.setEditable(false);
add(resultPanel, BorderLayout.NORTH);
cmdLabel = new JLabel ("Enter the number of elements to add to the array: ");
cmdTextField = new JTextField();
JPanel cmdPanel = new JPanel(new GridLayout(2,6));
cmdPanel.add(cmdLabel);
cmdPanel.add(cmdTextField);
cmdTextField.addActionListener(this);
add(cmdPanel, BorderLayout.SOUTH);
pack();
setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
setVisible(true);
}
JPanel view = null;
public void actionPerformed(ActionEvent evt)
{
int sheight;
String cmdStr = cmdTextField.getText();
Scanner sc = new Scanner(cmdStr);
String cmd = sc.next();
if(isNumber(cmd))
{
int value = Integer.parseInt(cmd);
int [] arr = new int[value];
Random randy = new Random();
for (int k = 0; k < arr.length; k++)
{
int d = randy.nextInt(99);
arr[k] = d;
}
for (int k = 0; k < arr.length; k++)
{
avlTree.add(arr[k]);
if (view != null)
remove(view);
view = avlTree.getView();
add(view);
pack();
validate();
}
}
sheight = AVLTree.AVLNode.findHeight();
String heightstr = String.valueOf(sheight);
cmdResultTextField4.setText(heightstr);
cmdResultTextField2.setText(" ");
cmdResultTextField3.setText(" ");
int leaves = AVLNode.countLeaves();
String sleaves = String.valueOf(leaves);
cmdResultTextField5.setText(sleaves);
}
private boolean isNumber(String s)
{
return Character.isDigit(s.charAt(0));
}
/** The main method creates an instance of the AVLTreeDemo
class which causes it to display its window
*/
public static void main (String [ ] args)
{
AVLTreeDemo atd = new AVLTreeDemo();
}
//////////////////////////////////////////////////////////////////////////////////////
public class AVLTree
{
/**
AVLNode represents a node in an AVL tree
*/
public class AVLNode
{
int value; //Value Stored in this node
AVLNode left, right; // Left and right subtrees
int height; // Height of node
public AVLNode(int value)
{
// Call the sister constructor
this(value, null, null);
}
public AVLNode(int val, AVLNode left1, AVLNode right1)
{
value = val;
left = left1;
right = right1;
height = 0;
}
/**
The resetHeight methods recomputes height
if the left or right subtrees have changed
*/
void resetHeight()
{
int leftHeight = getHeight(left);
int rightHeight = getHeight(right);
height = 1 + Math.max(leftHeight, rightHeight);
}
/*public static int findHeight()
{
int leftHeight = getHeight(left);
int rightHeight = getHeight(right);
int fheight = 1 + Math.max(leftHeight, rightHeight);
return fheight;*/
}
//////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////
/**
The BTreeDisplay class grpahically displays
a binary tree
*/
public class BTreeDisplay extends JPanel
{
/**
Constructor.
@param tree - The root of the binary tree
tree to display
*/
BTreeDisplay(AVLNode tree)
{
setBorder(BorderFactory.createEtchedBorder());
setLayout(new BorderLayout());
if (tree != null)
{
String value = String.valueOf(tree.value);
int pos = SwingConstants.CENTER;
JLabel rootLabel = new JLabel(value, pos);
add(rootLabel, BorderLayout.NORTH);
JPanel panel = new JPanel(new GridLayout(1, 2));
panel.add(new BTreeDisplay(tree.left));
panel.add(new BTreeDisplay(tree.right));
add(panel);
}
}
}
public int getHeight(AVLNode tree)
{
if (tree == null) return -1;
else
return tree.height;
}
public boolean add(int x)
{
root = add(root, x);
return true;
}
public JPanel getView()
{
return new BTreeDisplay(root);
}
public boolean isEmpty()
{
return root == null;
}
public AVLNode root = null;
private AVLNode add(AVLNode bTree, int x)
{
if (bTree == null)
return new AVLNode(x);
if (x < bTree.value)
bTree.left = add(bTree.left, x);
else
bTree.right = add(bTree.right, x);
int leftHeight = getHeight(bTree.left);
int rightHeight = getHeight(bTree.right);
if (Math.abs(leftHeight - rightHeight) == 2)
return balance(bTree);
else
{
bTree.resetHeight();
return bTree;
}
}
private AVLNode balance(AVLNode bTree)
{
int rHeight = getHeight(bTree.right);
int lHeight = getHeight(bTree.left);
if (rHeight > lHeight)
{
AVLNode rightChild = bTree.right;
int rrHeight = getHeight(rightChild.right);
int rlHeight = getHeight(rightChild.left);
if (rrHeight > rlHeight)
return rrBalance(bTree);
else
return rlBalance(bTree);
}
else
{
AVLNode leftChild = bTree.left;
int llHeight = getHeight(leftChild.left);
int lrHeight = getHeight(leftChild.right);
if (llHeight > lrHeight)
return llBalance(bTree);
else
return lrBalance(bTree);
}
}
private AVLNode rrBalance(AVLNode bTree)
{
AVLNode rightChild = bTree.right;
AVLNode rightLeftChild = rightChild.left;
rightChild.left = bTree;
bTree.right = rightLeftChild;
bTree.resetHeight();
rightChild.resetHeight();
return rightChild;
}
private AVLNode rlBalance (AVLNode bTree)
{
AVLNode root = bTree;
AVLNode rNode = root.right;
AVLNode rlNode = rNode.left;
AVLNode rlrTree = rlNode.right;
AVLNode rllTree = rlNode.left;
rNode.left = rlrTree;
root.right = rllTree;
rlNode.left = root;
rlNode.right = rNode;
rNode.resetHeight();
root.resetHeight();
rlNode.resetHeight();
return rlNode;
}
private AVLNode llBalance (AVLNode bTree)
{
AVLNode leftChild = bTree.left;
AVLNode lrTree = leftChild.right;
leftChild.right = bTree;
bTree.left = lrTree;
bTree.resetHeight();
leftChild.resetHeight();
return leftChild;
}
private AVLNode lrBalance(AVLNode bTree)
{
AVLNode root = bTree;
AVLNode lNode = root.left;
AVLNode lrNode = lNode.right;
AVLNode lrlTree = lrNode.left;
AVLNode lrrTree = lrNode.right;
lNode.right = lrlTree;
root.left = lrrTree;
lrNode.left = lNode;
lrNode.right = root;
lNode.resetHeight();
root.resetHeight();
lrNode.resetHeight();
return lrNode;
}
}
}