-----------------------------------

TheZsterBunny

Sat Jan 29, 2005 10:29 pm


Binary Trees

-----------------------------------

Howdy.

I've spent a few days thinking about this, but I can't seem to think of a way to get around the data protection issues. My add function works correctly, but I can't think of a way to actually add the value.

Any suggestions? I'm not really working on data protection at the mo.

-Z


public class TestTree
{
    static BinaryTree oak;
    public static void main (String 


-----------------------------------

Hikaru79

Sat Jan 29, 2005 11:13 pm



-----------------------------------

Bnode should be the class that can instantiate it's "left" and "right" nodes. When I get back home, I'll post my code too. Basically, your Bnode has to be in charge of more than it is. A good breakdown of methods for Bnode is:

public class TreeNode {

private int value;
private TreeNode left, right;

public TreeNode (int value){

	this.value = value;
	left = right = null;

}

public int getValue () {
	return value;
}

public TreeNode getLeft () {
	return left;
}

public TreeNode getRight () {
	return right;
}

public TreeNode compare (int value) {
	if (value >= left.getValue()){
	return left;
}
	return right;
}

public void setSubNode (TreeNode node, int value){
	node = new TreeNode (value);
}

}

I'm writing this from memory, and without a compiler available (not on my computer) so be forgiving of any errors I might have made.

EDIT: Oh, wow. "TreeNode" seems to be taken by the standard Java library. I guess "Bnode" was a better name for it after all. Just do a replace when you try that code. It shouldn't make a difference (you're not importing javax.swing) but still, change it to Bnode.


-----------------------------------

Andy

Sun Jan 30, 2005 2:03 pm



-----------------------------------

u can do btrees without pointers???? Oooo rite u can just pass an object through... psh thats gay.. go learn pointers and c++


-----------------------------------

Hikaru79

Sun Jan 30, 2005 3:39 pm



-----------------------------------

u can do btrees without pointers????

Pointers? In Java? Heaven forbid ;)

Hey, Zbunny, here's a great guide to Binary Trees in Java specifically. A great read =) http://cslibrary.stanford.edu/110/BinaryTrees.pdf  (skip past the C++ part. It does it in Java too in the second half)


-----------------------------------

rizzix

Sun Jan 30, 2005 3:47 pm



-----------------------------------

u can do btrees without pointers???? Oooo rite u can just pass an object through... psh thats gay.. go learn pointers and c++

jeez only a little kid would brag about pointers  :lol:


-----------------------------------

md

Sun Jan 30, 2005 3:53 pm



-----------------------------------

pointers rock! Although I must admit then can become confusing... The problem with Java is that you deal with objects, but without all the pointers; which I find makes it easy to forget what's what.


-----------------------------------

rizzix

Sun Jan 30, 2005 4:00 pm



-----------------------------------

well once u get used to it.. u'll realise its a different frame of thought.. i can tell you this only because i started of with java and then learnt c++. i've noticed its harder the other way around: i.e for a c++ programmer to think in java.

i believe this is only true because of the abstaction and dynamism absent in c++.. similarly its harder for a java programmer (or a c++ programmer for that matter) to think completely dynamically using any scripting language. 

for ex: i know a couple of perl programmers who think out programming solution that include the concept of dynamically generating code on the fly to solve a perticular problem. this is sortof impossible in java.. and quite impossible in c++. we just dont, and hence have a little hard time comming up with such dynamic but effecient solutions without some thought.


-----------------------------------

wtd

Sun Jan 30, 2005 4:56 pm



-----------------------------------

u can do btrees without pointers????

Pointers? In Java? Heaven forbid ;)

Java has pointers.  It couldn't do what it does without them.

What Java doesn't do is allow you to arbitrarily manipulate pointers to inappropriately access memory.


-----------------------------------

Andy

Mon Jan 31, 2005 10:19 am



-----------------------------------


jeez only a little kid would brag about pointers  :lol:

hey! pointers are the coolest things in c++


-----------------------------------

wtd

Mon Jan 31, 2005 1:53 pm



-----------------------------------


jeez only a little kid would brag about pointers  :lol:

hey! pointers are the coolest things in c++

No.

Templates are.


-----------------------------------

Hikaru79

Mon Jan 31, 2005 10:24 pm



-----------------------------------

u can do btrees without pointers????

Pointers? In Java? Heaven forbid ;)

Java has pointers.  It couldn't do what it does without them.

I know =P I was being sarcastic. That's why I pasted a link all about Pointers in Java the line right after what you qouted ;)


-----------------------------------

McKenzie

Tue Feb 01, 2005 9:25 am



-----------------------------------

Dynamic code impossible in C++??? Oh, it's ill advised but far from impossible.
Solution #1 - The hard way -
Although preprocessor macros are used mainly for simple functions they can in fact also be used to dynamically generate code. (no where near as easily as a scripting language)
Solution #2 - The insane way -
I've only ever seen this done once. Because you can easily break into assembly from C or C++ you can generate any code you want on the fly.  In assemble code and data are the same.  Whatever you point the IP register at it will try to run.
--------
As for the real conversation. I don't agree that it is better to go from Java to C++ instead of the reverse. I think it's just different. If you learn pointers properly in C++ the first time then when you learn Java you have a better understanding what's going on "under the hood."  For example I think it is easier for a C++ programmer to understand problems like "Why can my Method change my Point parameter, but not my int parameter?" Andy, the main difference is that you can't do pointer arithmetic in Java and you don't have to use & and * to manipulate your pointers.


-----------------------------------

wtd

Tue Feb 01, 2005 2:07 pm



-----------------------------------

I've only ever seen this done once. Because you can easily break into assembly from C or C++ you can generate any code you want on the fly.  In assemble code and data are the same.  Whatever you point the IP register at it will try to run.

CPUs with the "NX bit" and more conservative operating systems will get uppity if you try to run code on the heap.  ;)


-----------------------------------

rizzix

Tue Feb 01, 2005 2:15 pm



-----------------------------------

Dynamic code impossible in C++??? Oh, it's ill advised but far from impossible.
Solution #1 - The hard way -
Although preprocessor macros are used mainly for simple functions they can in fact also be used to dynamically generate code. (no where near as easily as a scripting language)
Solution #2 - The insane way -
I've only ever seen this done once. Because you can easily break into assembly from C or C++ you can generate any code you want on the fly.  In assemble code and data are the same.  Whatever you point the IP register at it will try to run.
--------
As for the real conversation. I don't agree that it is better to go from Java to C++ instead of the reverse. I think it's just different. If you learn pointers properly in C++ the first time then when you learn Java you have a better understanding what's going on "under the hood."  For example I think it is easier for a C++ programmer to understand problems like "Why can my Method change my Point parameter, but not my int parameter?" Andy, the main difference is that you can't do pointer arithmetic in Java and you don't have to use & and * to manipulate your pointers.

hmm ur solution #1 is still static. i.e it is dynamic but only at compile time.. i'm talking about runtime.. ur solution #2 although it theoretically seems possible.. it would require precompiled code to which u can "point  to", just like dlls. but the problem here is that you'd need to know the memory addr etc of this precomipled stuff. once again this requires that all address are fixed. which means its not really all that dynamic anymore. 

even if it were possible (your solution #2 i.e) it's not portable solution at all.


as far as java goes.. yea you cannot do pointer arithmetic at all. hence its not called a pointer in java but a reference (also because they dont truely behave like aliases either).

and as far as learning c++ before java: i know a lot of kids who have done this.. and they are completely confused. specially when it comes to poper OOP. but those that learn Ruby, Java, smalltalk before c++, have their oop concepts solid.


-----------------------------------

McKenzie

Tue Feb 01, 2005 4:21 pm



-----------------------------------

With solution #2 you don't use pre-compiled code. You actually change the executable code as it is running. I've seen it done back when I was taking assembly.  I wasn't arguing that it SHOULD be done, just that it could. I think you're right about #1 though. 
-----
As for which to learn first I remain unconvinced. I am teaching Java this year however but this is a matter of trying to sync with the Universities.


-----------------------------------

TheZsterBunny

Mon Feb 07, 2005 10:18 pm



-----------------------------------

right, moving back on topic.

Finally understood the mistake in my code. calling by value, rather than reference. well, something to that extent.

Still working on the del function, however.


public class BTest
{
    static BTree oak;
    public static void main (String [] args)
    {
        oak = new BTree ();
        oak.add (new BNode (1));
        oak.add (new BNode (5));
        oak.add (new BNode (9));
        oak.add (new BNode (7));
        oak.add (new BNode (2));
        oak.add (new BNode (6));
        oak.add (new BNode (8));
        oak.add (new BNode (3));
        oak.add (new BNode (-4));
        oak.displayAll ();
    }
}
class BTree
{
    BNode root;

    public BTree ()
    {
        root = null;
    }


    public void add (BNode leaf)
    {
        if (root == null)
            root = leaf;
        else
            append (leaf, root);

    }


    public void del (BNode toPrune)
    {

    }


    public void displayAll ()
    {
        if (root != null)
            deeplook (root);
    }


    public void showPath (int value)
    {
        String path = "base";
        BNode tmp = root;
        while (tmp != null && tmp.val != value)
        {
            if (tmp.val > value)
            {
                tmp = tmp.l;
                path += ";left";
            }
            else
            {
                tmp = tmp.r;
                path += ";right";
            }
        }
        if (tmp.val == value)
            System.out.println (value + " @ " + path);
        else
            System.out.println (value + " not found");
    }


    private void append (BNode leaf, BNode branch)
    {
        if (branch.val > leaf.val)
            if (branch.l == null)
                branch.l = leaf;
            else
                append (leaf, branch.l);
        else
            if (branch.r == null)
                branch.r = leaf;
            else
                append (leaf, branch.r);
    }


    private void deeplook (BNode branch)
    {
        if (branch.l != null)
            deeplook (branch.l);
        //        System.out.print (branch.val);
        showPath (branch.val);
        if (branch.r != null)
            deeplook (branch.r);
    }
}

class BNode
{
    BNode l, r;
    int val;
    public BNode (int value)
    {
        val = value;
        l = r = null;
    }
}


-Z 

--edit-- 
maybe next time i'll attach it ^_^