C++ and Java, tree question
Author
Hello,
I'm a C++ programmer and I was wondering how you could ever implement a tree structure in a language without pointers? I can't inmagine that conceptually. It can be any kind of tree, kd bsp oct quad ect. And turning on pointers in C# is not what I mean ;)
Cheers,
Dolf
You can store a binary tree in an array as mentioned here:
http://en.wikipedia.org/wiki/Binary_tree#Methods_for_storing_binary_trees
Edit: Cool thing about doing that is you can do a level-order traversal by just walking the array. =)
http://en.wikipedia.org/wiki/Binary_tree#Methods_for_storing_binary_trees
Edit: Cool thing about doing that is you can do a level-order traversal by just walking the array. =)
Author
thanks, looks good
Edit: That's a cool extra option, but isn't the use of trees to be able to reduce the problem space? An array might be friendly on the cache though, I should time that ( Or did anyone else already do that? )
Edit: That's a cool extra option, but isn't the use of trees to be able to reduce the problem space? An array might be friendly on the cache though, I should time that ( Or did anyone else already do that? )
In C# you have reference types. So:
public class Node
{
public Node lch;
public Node rch;
public int value;
}
could be the node. Basically with reference types the assignment operator makes the lhs point to the instance of the rhs.
Node n = new Node();
Node m = n;
So modifying the instance that m references will modify the instance n is referring to.
public class Node
{
public Node lch;
public Node rch;
public int value;
}
could be the node. Basically with reference types the assignment operator makes the lhs point to the instance of the rhs.
Node n = new Node();
Node m = n;
So modifying the instance that m references will modify the instance n is referring to.
Quote:Original post by Dolf
I'm a C++ programmer and I was wondering how you could ever implement a tree structure in a language without pointers?
In the case of Java, variables don't hold objects, but rather hold references to objects. Basically, in Java, every non-primitive variable IS a pointer (but without pointer arithmetic).
Author
Ok cool.
What would you advise for tool development? Whats in demand? Java or C# or something else?
What would you advise for tool development? Whats in demand? Java or C# or something else?
To implement a tree, you need reference semantics. Pointers are one of the ways used by C and C++ to implement reference semantics (they also implement iteration semantics and option semantics, which makes them kind of ugly and dangerous and needlessly complicated). This means that you can implement trees with pointers, but you don't need pointers to implement trees. In fact, the whole manual memory management issue in C and C++ makes trees harder to implement than in other languages.
It is usually considered that the easiest way to create a tree is to use a recursive variant type with reference semantics. Objective Caml, among others, provides the required functionality to do so, as illustrated by this expression tree example:
The equivalent tree in C++ would look like:
As for storing in an array, it wastes memory if the tree is not balanced.
It is usually considered that the easiest way to create a tree is to use a recursive variant type with reference semantics. Objective Caml, among others, provides the required functionality to do so, as illustrated by this expression tree example:
type expression = | Value of int | Add of expression * expression | Subtract of expression * expression(* 10 - 20 + 30 *)let test = Add (Subtract (Value 10, Value 20), Value 30) (* Evaluation *)let rec eval = function | Value v -> v | Add (left, right) -> eval left + eval right | Subtract (left, right) -> eval left - eval rightlet _ = eval testThe equivalent tree in C++ would look like:
class expression{public: virtual ~expression() {} virtual int eval() const = 0;};typedef boost::shared_ptr<const expression> expression_ptr;class value : public expression{ int v;public: value(int v) : v(v) {} int eval() const { return v; }};class add : public expression{ expression_ptr left, right;public: add(expression_ptr left, expression_ptr right) : left(left), right(right) {} int eval() const { return left->eval() + right->eval(); }};class subtract : public expression{ expression_ptr left, right;public: subtract(expression_ptr left, expression_ptr right) : left(left), right(right) {} int eval() const { return left->eval() - right->eval(); }};expression_ptr p10(new value(10)), p20(new value(20)), p30(new value(30)), sub(new subtract(p10, p20)), test(new add(sub, p30));test -> eval();As for storing in an array, it wastes memory if the tree is not balanced.
Wrong, the equivalent C++ code would be http://www.boost.org/doc/libs/1_38_0/doc/html/variant/tutorial.html#variant.tutorial.recursive
As for how to do manual memory management in garbage collected language (which is quite often necessary since those languages are quite inefficient with locality etc.) you indeed allocate a big array of some primitive type like int, which is exactly the same thing as memory, and you can recreate C-style like code, with indexes in the array being equivalent to pointers.
This however ends up being less efficient than direct memory management, in particular due to the need to use serialization/deserialization to store elements in your array etc.
As for how to do manual memory management in garbage collected language (which is quite often necessary since those languages are quite inefficient with locality etc.) you indeed allocate a big array of some primitive type like int, which is exactly the same thing as memory, and you can recreate C-style like code, with indexes in the array being equivalent to pointers.
This however ends up being less efficient than direct memory management, in particular due to the need to use serialization/deserialization to store elements in your array etc.
Quote:Original post by ToohrVyk
As for storing in an array, it wastes memory if the tree is not balanced.
True, and you waste memory storing pointers (references) when the tree is balanced! Anyways, I always see pointers and references just different names (and potentially syntax) for the same concept. When he said "implement a tree structure in a language without pointers" I figured he was ruling out references too, since using a reference would be functionally equivalent to using pointers and an obvious choice.
Author
Pointers and references are pretty much the same ye. My question was about how you can program a tree in a higher level language than C++.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
