Binary Trees

[TheZsterBunny]

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

Java:

public class TestTree {     static BinaryTree oak;     public static void main (String [] args)     {         oak = new BinaryTree (50);         oak.add (5);         oak.displayAll ();     } } class BinaryTree {     BNode root = null;     public BinaryTree (int value)     {         root = new BNode (value);     }     public void add (int value)     {         BNode tmp = root;         while (tmp != null)         {             tmp = next (value, tmp);         }         tmp = new BNode (value);     }     private BNode next (int value, BNode node)     {         if (value < node.val)         {             return node.l;         }         else         {             return node.r;         }     }     public void del (int value)     {         BNode tmp = root;         while (tmp != null || tmp.val == value)         {             tmp = next (value, tmp);         }         if (tmp.val == value)         {             add (tmp.l.val);             add (tmp.r.val);             tmp = null;         }     }     private void deepLook (BNode look)     {         if (look.l != null)         {             deepLook (look.l);         }         System.out.println (look.val);         if (look.r != null)         {             deepLook (look.r);         }     }     public void displayAll ()     {         BNode tmp = root;         deepLook (tmp);     } } class BNode {     int val;     BNode l, r;     public BNode (int value)     {         val = value;         l = r = null;     } }

[Hikaru79]

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:

Java:

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]

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

[Hikaru79]

Andy wrote:

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]

Andy wrote:

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

[md]

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]

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]

Hikaru79 wrote:

Andy wrote:

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]

rizzix wrote:

jeez only a little kid would brag about pointers

hey! pointers are the coolest things in c++

[wtd]

Andy wrote:

rizzix wrote:

jeez only a little kid would brag about pointers

hey! pointers are the coolest things in c++

No.

Templates are.

[Hikaru79]

wtd wrote:

Hikaru79 wrote:

Andy wrote:

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]

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]

McKenzie wrote:

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]

McKenzie wrote:

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]

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.