Binary trees

[NewOrder]

2 things that i dont understand:

class BTree{
	private	Node head;
	public void add(int info){
		Node node=new Node(info);
		if(head==null){
			head=node;
			return;
		}
		
		Node current=head;
		while (true) { // what does this mean? where is the true value derived from?
			if(info<current.info){// to what number does the current.info refers to?
				if (current.left==null) {
					current.left=node;// i dont get this? why does it have to equal to node?
					return;
				}
				else
					current = current.left;
			}
			else {
				if(info>current.info){
					if (current.right==null) {
						current.right=node;
						return;
					}
					else
						current = current.right;
				}
			}
		}
		
		
			
	}

thats part of an algorithm that creates a binary tree. the things that i dont understand are mentioned in the code

[bops]

while (true) { // what does this mean? where is the true value derived from?

while(true) means that the loop will continue forever until it is broken by either a break statement or a return statement. You can see later in your code that you have return; which will break the loop and end the function. while(statement) means that while "statement" is true do the following. while(true) means while true is true (true will always be true) do the following.

Node current=head;
		while (true) { // what does this mean? where is the true value derived from?
			if(info<current.info){// to what number does the current.info refers to?

As you can see from this statement Node current=head;, current will be the same as head. So current.info will return the same as head.info. A Node I am assuming has a field named info which will contain the value that you are comparing.

current.left=node;// i dont get this? why does it have to equal to node?

You are a little confused about Java syntax here, this statement doesn't say that something must be equal to something. It is an assignment. It is giving current.left the value of node, since this is a binary tree it is setting the left child of the head node (since current is head) to the Node "node". In Java one '=' means give something a value, whereas two of them, '==' means compare these two value and retur true if they are the same, false otherwise.

[NewOrder]

i thought i got the idea..

if right side is bbigger than nod. then add the node.. which contains the information (number. wiith the left side it is vice versa.

but this confuses me a bit
(info<current.info)
what does current.info holds?

[NewOrder]

i understand now

what does current.info contain?
if(info<current.info)

[NewOrder]

class Node{
		int info;
		public Node(int info) {
			super();
			this.info = info;
		}
		Node left;
		Node right;
	}

here is my node. what does current.info stores?
if(info<current.info){

[cale.macdonald]

info is just a integer value contained by the node. So the if statement just checks if the supplied number (info) is less than the current nodes info value

[NewOrder]

so info is an integer ..lets say the method is called twice

tree.add(5);
tree.add(6);

where is teh 5 saved and how is it compared to the 6?

[cale.macdonald]

Lets take this scenario, it might be easier to understand.

If you add 12 to the tree (nothing in it) 12 will become the root (head) of the tree
Then lets say you add the number 5. According to the algorithm, it will go into the while loop, then it will come to the first compare statement and check if (5 < 12) ... it is so it will go into that code block. Since current (in the code) is the root node and it does not have any children, current.left == null is true, therefore it is then added into that position. At this point your tree will look something like:

12
   /  \
  5   (null)

Now assuming you enter the number 15. It will go into the other code block since 15 < 12 is false. At this point it will be added to the right node of the root node, so your tree will look like:

12
   /  \
  5   15

If you now insert the number 6 it will go into the while do the check if 6 < 12, which it is and then carry on. However current.left is not null therefore it will assign current to the node (5). It will then come back into the loop (did not hit the break statement) and then do the check if 6 < 5. It is not so it will go into the else case. Now assigning the right value of the current node (5) to be 6.

So your tree will now look like this:

12
        /    \
    5           15
 /     \     /     \
(null)  6   (null) (null)

*sorry about the crappy diagram, but you should get an idea.

The best way is to learn binary trees is to get a piece of paper and draw out how you think a tree should look (just use a simple case like I did). Then grab a debugger and step through the code or use output statement to track what the program is doing.

Hope that helps

[NewOrder]

mac,

is converting , binary tree to linklist and vice versa useful to know in the real world.

i am trying to memorize now a monstruous code, and i have being wondering that question

i understand how the binary tree work. so the current.info is the 12. the first piece that goes in, and the info is the second?

mmmm.. i think i might understand.

current is the head.. the head obtains the value first..12, then what happens, is the second value comes it, it sees that the head is being full and goes inside the loop for an evaluation.. 5<12..etc

am i right?

[vaibhav1983]

This is basically inserting an element in a BST(Binary Search Tree).

Answers to your queries are
1. true is used to keep running the loop endlessly. Its for setting the infinite loops.

2. current.info refers to the number stored in teh current node that we are examining. Suppose in the BST traversal you are currently at the left node of the root the it points to the number stored in the left node of the root.

3.current.left = node
This is set because if the left node of the current node is null and the node is less than the current node then it can be assigned as the left node. (Basic rule for BST)

If you are still not clear then we can sure keep a skype session. :)

[NewOrder]

another question. is it useful to remember how to convert a binary to link list?

the process seems to be long.

i know how to eliminate nodes and connect them back through binary tree.

but how important is to remember the conversion from the link to binary and vice versa

[vaibhav1983]

another question. is it useful to remember how to convert a binary to link list?

the process seems to be long.

i know how to eliminate nodes and connect them back through binary tree.

but how important is to remember the conversion from the link to binary and vice versa

Sure you can make a link list from Binary Trees.

You can do an inorder traversal of Binary tree and construct a Link List from it.

For converting a link list to binary tree, I'll have to dig a bit :)

[JamesCherrill]

For converting a link list to binary tree, I'll have to dig a bit

It's just like tree to list, ie iterate thru the list and add each element to the tree.

is it useful to remember how to convert a binary to link list?

You certainly do not have to learn the code by heart, but any competent programmer would know about it at the level of "do an inorder traversal of Binary tree and construct a Link List from it." and know how to write (or find) the code to do that.

[NewOrder]

the problem is that i have that code. and i dont understand what the last part of it does.
as i can see the code simply concentrates on removing nodes and joining the nodes underneath together. am i right?

public class BTree{
    Node head;
    public void add(Person info){ // create the tree
        Node unit=new Node(info);
        if(head==null)
            head=unit;
        else{
            Node current=head;
            while (true) {
                if(unit.info.age<current.info.age){
                    if(current.left==null){
                        current.left=unit;
                        return;
                    }
                    else
                        current=current.left;
                }
                else{
                    if(current.right==null){
                        current.right=unit;
                        return;
                    }
                    else
                        current=current.right;
                }
            }
        }
    }


    public void print(){
        print(head);
    }
    private void print(Node unit) {
        if(unit==null)
            return;
        print(unit.left);
        unit.info.print();
        print(unit.right);
    }




    public void remove(Person p){ //remove head
        Node left;
        Node right;
        if(head.info.age==p.age){
            left=head.left;
            right=head.right;
            if(left==null&&right==null)
                head=null;
            if(left!=null){
                head=left;
                addUnit(right);
            }
            else{
                head=right;
            }
        }
        else{
            remove(head, p);
        }
    }





    public void remove(Node unit,Person p){//remove nodes
        if(unit==null)
            return ;
        Node left;
        Node right;
        remove(unit.left,p);
        if(unit.left!=null)
            if(unit.left.info.age==p.age){
                right=unit.left.right;
                unit.left=unit.left.left;
                addUnit(right);
            }
        if(unit.right!=null)
            if(unit.right.info.age==p.age){
                left=unit.right.left;
                unit.right=unit.right.right;
                addUnit(left);
            }
        remove(unit.right,p);
    }





    private void addUnit(Node unit){ //
        Node current=head;
        if(unit==null)
            return;
        while (true) {
            if(unit.info.age<current.info.age){
                if(current.left==null){
                    current.left=unit;
                    return;
                }
                else
                    current=current.left;
            }
            else{
                if(current.right==null){
                    current.right=unit;
                    return;
                }
                else
                    current=current.right;
            }
        }
    }



    public LinkedList toLinkList(){ //what does this function do?
        LinkedList list=new LinkedList();
        toLL(head,list);
        return list;
    }
    private void toLL(Node unit,LinkedList list){// what does this function do?
        if(unit== null)
            return;
        toLL(unit.left,list);
        list.add(unit.info);
        toLL(unit.right, list);
    }
}
class Node{
    Person info;
    public Node(Person info){
        this.info=info;
    }
    Node left;
    Node right;
}

a continuation.. link list code:

class Unit{
    Person info;
    public Unit(Person info){
        this.info=info;
    }
    Unit next;
}

public class LinkedList{
    Unit head;
    public void add(Person info){
        Unit unit=new Unit(info);
        if(head==null)
            head=unit;
        else{
            Unit current=head;
            while(current.next!=null)
                current=current.next;
            current.next=unit;
        }
    }
    public void print(){
        print(head);
    }
    private void print(Unit unit){
        if(unit==null)
            return;
        unit.info.print();
        print(unit.next);
    }
    public void remove(Person obj){
        if(head!=null){
            while(head.info.equals(obj)){
                head=head.next;
                if(head==null)
                    return;
            }
            
            Unit current=head;
            while(current.next!=null){
                if(current.next.info.equals(obj))
                    current.next=current.next.next;
                else
                current=current.next;
            }
            
        }    
    }
    public BTree ToBTree(){
        BTree btree=new BTree();
        if(head==null)
            return null;
        Unit current=head;
        while(current!=null){
            btree.add(current.info);
            current=current.next;
        }
        return btree;
    }
}

person class

public 
class Person{

    String name;
    int age;
    public Person(String n,int age){
        this.name=n;
        this.age=age;
    }
    public void print(){
        System.out.println(name+" "+age);
    }
    @Override
    public boolean equals(Object arg0) {
        Person p=(Person)arg0;
//        return this.name.equals(p.name);
        return this.age==p.age;
    }
}

[JamesCherrill]

LinkedList toLinkList(){ //what does this function do?

Read the code. It returns the current object converted to a LinkedList. It does this by starting a recursive traversal of the tree using toLL.

private void toLL(Node unit,LinkedList list){// what does this function do?

Read the code. It calls toLL for the left node, adds the current node's info to the linked list, calls toLL for the right node. This recursively traverses the tree adding all the infos to the linked list

ps: Did you finish the chess program?

[NewOrder]

lol. i couldnt debugg the chess program.

i set the condition if(chesspiece==null).. or something like that. but the program ignored the condition

i did finish doing it (i added castling, pawn promotion, everything), but that bug made the program impossible to run. i am going to try to debugg it ..

not now though