0

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;
    }
}                   

}
2
Contributors
1
Reply
5
Views
4 Years
Discussion Span
Last Post by NormR1
0

I am getting caught up in private and public classes and methods...

Please explain what your problems are and post the error messages you are getting.

am getting crazy numbers for a height.

Please post the output from the program.

Have you tried debugging the code? Add lots of println statements to the code to show all the variables as they are used and changed and to show the execution flow.. The print out will show you what the computer sees and help you understand what the code is doing.

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.