Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 18 of 18

Thread: Unbalance Tree to Balanced Tree

  1. #1
    Junior Member
    Join Date
    Nov 2018
    Posts
    11
    Thanks
    4
    Thanked 0 Times in 0 Posts

    Default Unbalance Tree to Balanced Tree

    Im doing a project, the project requires that I build an unbalance tree then balance it.
    Im having trouble with the recursion that is building the tree. The function is called balance. The tree isnt balancing itself properly.


    This is small description of the project:
    In this project, you will have to build a binary
    tree, balance it (i.e. make sure that the whole tree and each subtree have
    comparable number of child nodes on either side), and use it to search for a
    particular word.

    When any node is unbalanced, you must find a new pivot node. This new pivot
    node is the node which, if promoted to be the root of this sub tree, will have equal
    weight on either side.

    package tree;
    import java.io.BufferedReader;
    import java.io.FileReader;
    import java.io.IOException;
     
    /**
     * <h2>Main</h2> <p></p>
     */
     
    public class Main {
     
     
    	public static void main(String[] args) throws IOException {
    		Input userIn = new Input();
    		//BalanceTree<String> newtree=new BalanceTree<String>();
     
    		//Open text file. Make sure to change the file path to your personal file path for any .txt document.
    		BufferedReader file = new BufferedReader(new FileReader("C:\\Users\\Malcolm\\Documents\\School\\Test.txt"));
    		//Initializes word to null.
    		String word = null;
    		TreeNode myTreeNode = new TreeNode(null, null);
    		int count = 0;
    		//Set word equal to a line in the text file. While word is not null,
    		while ((word = file.readLine())!= null) {
    			//insert the word into the tree and convert the tree to a balanced binary tree.
    			//newtree.convertTree(newtree.insertElement(word));
    			if(count == 0) {
    				myTreeNode.setLeft(new TreeNode(myTreeNode, word));
    			}else {
    				myTreeNode.setRight(new TreeNode(myTreeNode, word));
    				TreeNode test = new TreeNode(null,null);
    				test.setLeft(myTreeNode);
    				myTreeNode.setParent(test);
    				myTreeNode = new TreeNode(null, null);
    				myTreeNode = test;
     
    			}
    			count+=1;
    		}
    		myTreeNode = myTreeNode.getLeft();
     
     
    		//Close text file read in to prevent leakage.
    		file.close();
     
     
    		balance(myTreeNode);
     
     
     
     
     
    		//System.out.println(x);
    		//Ask user for the word they would like to search.
    		System.out.print("Enter a word and this wil tell you whether it is in the tree or not: ");
    		//Set the user input.
    		userIn.setStringInput();
    		//Search the tree using the user input and set the results equal to word.
    		//BalanceTree<String>.Node<String> inword = newtree.searchTree(userIn.getStringInput());
     
    		//If the input word matches any word in the tree is will print the output below along wiht the initial word,
    		if(userIn!=null)
     
    			System.out.println(userIn + " is within the tree.");
    		//If the input does not match it will display that there is an error 
    		else
     
    			System.out.println("Error the word " + userIn.getStringInput() + " is not in the tree.");
        } 
    	static int Thanos(TreeNode myTreeNode, int x ) {
    		TreeNode tree = new TreeNode(null,null);
    		tree =  myTreeNode;
    		if(tree.getLeft() == null) {
    			return x;
    		}else{
    			//System.out.println(x);
    			return Thanos(myTreeNode.getLeft(), x+1);
    		}
    	}
     
    	static void balance(TreeNode myTreeNode ) {
    		int x = 1;
     
    		x = Thanos(myTreeNode, x);
    		int k = x;
    		k = k % 2;
    		if (k != 1) {
    			x = x / 2;
    		}else {
    			x = ((x-1)/2)+1;
    		}
    		TreeNode Traverse = new TreeNode(null,null);
    		TreeNode amid = new TreeNode(null,null);
    		Traverse = myTreeNode;
    		 amid = myTreeNode;
    		while(x != 1) {
    			Traverse = Traverse.getLeft();
     
    			if (x == 3) {
    				amid = Traverse;
    			}
    			x -= 1;
     
    		}
    		TreeNode test = new TreeNode(amid, Traverse.getRight().getValue());
    		amid.setLeft (test);
    		Traverse.setRight(myTreeNode);
    		myTreeNode.setParent(Traverse);
    		myTreeNode = new TreeNode(null, null);
    		myTreeNode = Traverse;
     
    		x = Thanos(myTreeNode.getLeft(), 1);
    		if(x >2) {
    		balance(myTreeNode.getLeft());
    		}
     
    		TreeNode RTraverse = new TreeNode(null,null);
    		RTraverse = Traverse.getRight();
    		TreeNode Ramid = new TreeNode(null,null);
    		x = Thanos(RTraverse, 0);
    		if (x > 2) {
    			while(x != 1) {
     
     
    			if (x == 2) {
    				Ramid = RTraverse;
    			}
    			x -= 1;
    			RTraverse = RTraverse.getLeft();
    		}
    		Ramid.setLeft(new TreeNode(Ramid, RTraverse.getRight().getValue()));
    		Traverse.setRight(RTraverse);
    		RTraverse.setRight(Ramid);
    		Ramid.setParent(RTraverse);
     
    		myTreeNode = new TreeNode(null, null);
    		myTreeNode = RTraverse;
    		x = Thanos(Traverse.getRight(), 1);
    		if(x >2) {
    		balance(RTraverse.getLeft());
    			}
    		}
    	}
     
    }


    package tree;
     
    public class TreeNode {
    	TreeNode parent;
    	String value;
    	TreeNode left;
    	TreeNode right;
     
    	public TreeNode getParent() {
    		return parent;
    	}
     
    	public void setParent(TreeNode parent) {
    		this.parent = parent;
    	}
     
    	public String getValue() {
    		return value;
    	}
     
    	public void setValue(String value) {
    		this.value = value;
    	}
     
    	public TreeNode getLeft() {
    		return left;
    	}
     
    	public void setLeft(TreeNode left) {
    		this.left = left;
    	}
     
    	public TreeNode getRight() {
    		return right;
    	}
     
    	public void setRight(TreeNode right) {
    		this.right = right;
    	}
     
     
    	public TreeNode(TreeNode parent, String value) {
     
    		this.value = value;
    		this.parent = parent;
    	}
     
     
    }

    package tree;
     
    import java.util.Scanner;
     
    /**
     * <p> </p>
     */
     
    public class Input {
    	private Scanner in = new Scanner(System.in);
    	public String input;
     
    	/**
    	 * <p> sets the users input to a variable and closes the scanner to prevent 
    	 * leakage.</p>
    	 */
    	public void setStringInput() {
    		//Variable to take the user input.
    		input = in.nextLine();
    		in.close();
    	}
     
    	/**
    	 * <p> returns the input fetched in  as a string.</p>
    	 * 
    	 */
    	public String getStringInput() {
    		//Return the user input as a string.
    		return input;
    	}
     
     
    }
    Last edited by johndoe123; November 28th, 2018 at 07:30 AM.

  2. #2
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    22,113
    Thanks
    52
    Thanked 2,369 Times in 2,323 Posts

    Default Re: Unbalance Tree to Balanced Tree

    The tree isnt balancing itself properly.
    Can you explain the algorithm for doing that so we can see if the code is following that algorithm?
    If you don't understand my answer, don't ignore it, ask a question.

  3. #3
    Member
    Join Date
    Sep 2018
    Location
    Virginia
    Posts
    284
    My Mood
    Cool
    Thanks
    0
    Thanked 38 Times in 36 Posts

    Default Re: Unbalance Tree to Balanced Tree

    This is not a new concept. You may want to read up on it. Red Black Tree

  4. #4
    Junior Member
    Join Date
    Nov 2018
    Posts
    11
    Thanks
    4
    Thanked 0 Times in 0 Posts

    Default Re: Unbalance Tree to Balanced Tree

    The first thing the program does it take read a file with words
    For example:
    apple
    bananas
    cookies
    donuts
    Then it takes in the words and creates an unbalanced tree. This part was done correctly and verified. The tree will look something like this
                               Node1
                                /  \
                               /    \   
                          Node2    apple
                             /  \     
                            /    \
                        Node3     bananas
                          /   \
                        /      cookies
                  Node4
                     /
                donuts
    After the creation of the tree I use the function balance to try balance the tree but I am getting confused about I should be pointing using the recursion

    --- Update ---

    Okay. Thank you for the feedback

  5. #5
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    22,113
    Thanks
    52
    Thanked 2,369 Times in 2,323 Posts

    Default Re: Unbalance Tree to Balanced Tree

    The posted code needs more class definitions to compile.

    to try balance the tree
    What is the algorithm for doing that? You need that before trying to write any code.
    If you don't understand my answer, don't ignore it, ask a question.

  6. #6
    Junior Member
    Join Date
    Nov 2018
    Posts
    11
    Thanks
    4
    Thanked 0 Times in 0 Posts

    Default Re: Unbalance Tree to Balanced Tree

    Quote Originally Posted by Norm View Post
    The posted code needs more class definitions to compile.


    What is the algorithm for doing that? You need that before trying to write any code.
    Im not sure I understand but the function is called balance. Inside this function is where I am doing the recursions.

  7. #7
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    22,113
    Thanks
    52
    Thanked 2,369 Times in 2,323 Posts

    Default Re: Unbalance Tree to Balanced Tree

    What are the steps the code in the balance method must take to solve the problem. That is what I call the algorithm.
    You need to do some design work before trying to write the code. Have you made a list of the steps balance must take?

    Note: There are two missing classes to be able to compile and execute the posted code.
    If you don't understand my answer, don't ignore it, ask a question.

  8. #8
    Junior Member
    Join Date
    Nov 2018
    Posts
    11
    Thanks
    4
    Thanked 0 Times in 0 Posts

    Default Re: Unbalance Tree to Balanced Tree

    Which classifications do you need?

  9. #9
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    22,113
    Thanks
    52
    Thanked 2,369 Times in 2,323 Posts

    Default Re: Unbalance Tree to Balanced Tree

    What is a classification?
    The missing classes:
    		Input userIn = new Input();
    		BalanceTree<String> newtree=new BalanceTree<String>();
    If you don't understand my answer, don't ignore it, ask a question.

  10. #10
    Junior Member
    Join Date
    Nov 2018
    Posts
    11
    Thanks
    4
    Thanked 0 Times in 0 Posts

    Default Re: Unbalance Tree to Balanced Tree

    Quote Originally Posted by Norm View Post
    What is a classification?
    The missing classes:
    		Input userIn = new Input();
    		BalanceTree<String> newtree=new BalanceTree<String>();
    Oh! I'm sorry I thought I uploaded it.

  11. #11
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    22,113
    Thanks
    52
    Thanked 2,369 Times in 2,323 Posts

    Default Re: Unbalance Tree to Balanced Tree

    What about the other class?
    If you don't understand my answer, don't ignore it, ask a question.

  12. #12
    Junior Member
    Join Date
    Nov 2018
    Posts
    11
    Thanks
    4
    Thanked 0 Times in 0 Posts

    Default Re: Unbalance Tree to Balanced Tree

    Quote Originally Posted by Norm View Post
    What about the other class?
    I'm currently not using it but I can include it if you would like

  13. #13
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    22,113
    Thanks
    52
    Thanked 2,369 Times in 2,323 Posts

    Default Re: Unbalance Tree to Balanced Tree

    I'm currently not using it
    The posted code uses it and won't compile without it.
    		BalanceTree<String> newtree=new BalanceTree<String>();
    Can you post your new code that does not use it?
    If you don't understand my answer, don't ignore it, ask a question.

  14. #14
    Junior Member
    Join Date
    Nov 2018
    Posts
    11
    Thanks
    4
    Thanked 0 Times in 0 Posts

    Default Re: Unbalance Tree to Balanced Tree

    Quote Originally Posted by Norm View Post
    The posted code uses it and won't compile without it.
    		BalanceTree<String> newtree=new BalanceTree<String>();
    Can you post your new code that does not use it?
    I posted the new code

  15. #15
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    22,113
    Thanks
    52
    Thanked 2,369 Times in 2,323 Posts

    Default Re: Unbalance Tree to Balanced Tree

    How do you execute the code? What is its current output?
    If you don't understand my answer, don't ignore it, ask a question.

  16. #16
    Junior Member
    Join Date
    Nov 2018
    Posts
    11
    Thanks
    4
    Thanked 0 Times in 0 Posts

    Default Re: Unbalance Tree to Balanced Tree

    Quote Originally Posted by Norm View Post
    How do you execute the code? What is its current output?
    There is no output I am trying to balance the tree. Until I balance the tree I cant properly search through it.

    --- Update ---

    I just need to balance the tree. This is why I said the output doesnt matter. My recursion is wrong.

  17. #17
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    Eastern Florida
    Posts
    22,113
    Thanks
    52
    Thanked 2,369 Times in 2,323 Posts

    Default Re: Unbalance Tree to Balanced Tree

    You should add code to print out the contents of the tree to verify that it is properly formed.

    If 4 values are added to the tree in the posted code, how many TreeNodes should the tree contain?
    When I print out the tree, it appears to have 7 TreeNodes. Is that the expected number?

    Do you have code to balance the tree that does not use recursion? Something for testing with while developing the recursive method.
    If you don't understand my answer, don't ignore it, ask a question.

  18. #18
    Member
    Join Date
    Sep 2018
    Location
    Virginia
    Posts
    284
    My Mood
    Cool
    Thanks
    0
    Thanked 38 Times in 36 Posts

    Default Re: Unbalance Tree to Balanced Tree

    According to the assignment, recursion isn't required. And you can implement binary tree algorithms without recursion. But if you don't print anything out, how do you know it's not working?

    Regards,
    Jim

Similar Threads

  1. (Binary Tree) Family tree - help with my addChild method
    By Pip_Squeak in forum What's Wrong With My Code?
    Replies: 5
    Last Post: March 26th, 2014, 07:52 AM
  2. Binary Search Tree inorder tree traversal
    By Maukkv in forum What's Wrong With My Code?
    Replies: 17
    Last Post: January 26th, 2013, 04:28 PM
  3. Balanced Binary Search Tree
    By D3158 in forum Object Oriented Programming
    Replies: 1
    Last Post: June 24th, 2011, 09:14 AM
  4. Left and Right rotation in a balanced binary tree problem
    By szuwi in forum Algorithms & Recursion
    Replies: 2
    Last Post: December 22nd, 2010, 06:20 PM
  5. Data Structures(Binary Search Tree to AVL Tree)ASAP
    By jfAdik in forum Algorithms & Recursion
    Replies: 2
    Last Post: April 5th, 2010, 03:58 AM

Tags for this Thread