Okay, now this may be an irritatingly simple issue, but I've had no formal education in programming and am a bit confused on this. I've had some instances where I've found a data tree to be the best method of dealing with information, as the heirarchal data is important. So now, be it from a Database or an XML file or whatever, how could I store this tree within the system? I need to be able to easily transverse the tree and edit, remove, add nodes. So would I store this infromation in a multi-dimensional array? Or as a number of Objects?
I'm asking here because it's not really specific to a language. Wow could I store this tree so that I can work with it? I don't think storing it as a string would make sense. Am I not making sense? Or am I looking at this the wrong way?
In an Object-Oriennted environment, you would normally create one heirarchical object that branches out to its members. It would work in a similar way to a multi-dimensional array but with a plethora of extra functionality and performance benefits. You would write methods to traverse the tree and manage its nodes.
Make sense? If you have eny experience with Java, you could take a look at the few premade Tree-like objects.
See, an Object Oriented approach was making the most sense to me. But still, OOP is something I still have a bit of a problem incorporating into programming I do (since my post "programming" experience is PHP, which doesn't force the Object Oriented approach). Admittedly the most OO I've used is as I learn Java, but I'm still confused as to how I would be able to maintain the heirarchal data. How would I be able to maintain that "This object's parent is such-and-such object" ?
I don't really understand your question. We are seeing the same question from such a different perspective.
Erm, basically, I'm still confused as to how I would do this, in say an Object Oriented enviroment.
Its a very complex subject with no real "best" approach. It's the sort of thing you will find alot of books on, however. I don't really have what it takes to teach OO Data Structures.
The most appropriate answer would depend on the actual context of the question. Are you referring to a HTTP -- stateless -- environment?
Basically, a tree node would consist of a grouped structure with three (optionally four) pointers/references. One for the data, two for the left and right subtrees, and an optional fourth referring to the parent (there are of course other variations, but this is the most basic). Exactly how this structure of pointers is grouped is language dependant. For example, C has its struct keyword. Perl traditionally uses hashes. (Anyone else know how PHP implements objects?)
So, to find the smallest value in the tree (which would be the left-most node) would work something like this (psuedo code)
/ \ / \
A C E G
p starts off as a pointer to node D. The first time through the loop p (currently node D) is replaced with the pointer value that is node D's left subtree, making p now a pointer to B. And so forthe until p points to a node that has no left subtree.
p = root
while (p->left != NULL)
p = p->left
Here is another tree algorithm that returns the next inorder node.
With this algorithm we get
if (p->right != NULL)
p = p->right
while (p->left != NULL)
p = p->left
if (p->parent == NULL)
return NULL // we're done
if (p->parent->left == p) // p is a left subtree
while (p->parent != NULL && p->parent->right == p) // while p is a right subtree
p = p->parent
inorder(A) returns B
inorder(B) returns C
inorder(c) returns D
inorder(G) returns NULL
For emphasis on modular programming, it's good to wrap the whole thing up in an abstract data type (ADT). That means that whatever part of your program that uses the tree should have no knowledge of the inside workings. That means no concept of subtrees, no concept of nodes, not concept of a root. The only thing anyone else should know is that we can insert, retrieve, and delete data from the tree. How it does it: don't know, don't care.
To get a lot more detailed information I'd recommend The Art of Computer Programming. These books will make up for any lack of formal training. It covers all the fundamental data structures and other not so fundamental data structures that even college graduates may not have seen, as well as all the formal mathematics involved.
Though this book can be some very heavy reading. If it seems to be too much you could start with Algorithms in (insert language here). This book has editions for several different languages, but this link is the one for Java. Note, however, that the actual code in this book is there to demonstrate a particular algorithm, not teach you good programming skills. The structure and style of the code probably should not be followed. There once was an edition of this book in psuedo code, but unfortunately it's no longer in print.
Anyways, if you do opt for the second book keep in mind that the former is the bible for the given subject, and I'd recommend you do get it eventually regardless where you start.
Last edited by Jeff Mott; 06-27-2005 at 08:54 AM.
Thank you very much. This is starting to make much more sense to me now!
And I'll also take a look at those books as well, thanks.
Users Browsing this Thread
There are currently 1 users browsing this thread. (0 members and 1 guests)