www.webdeveloper.com
Results 1 to 8 of 8

Thread: Data Tree

  1. #1
    Join Date
    Jul 2003
    Location
    New York City
    Posts
    2,771

    Data Tree

    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?

  2. #2
    Join Date
    Jan 2004
    Location
    Melbourne, Australia
    Posts
    5,298
    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.

    Regards.

  3. #3
    Join Date
    Jul 2003
    Location
    New York City
    Posts
    2,771
    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" ?

  4. #4
    Join Date
    Jan 2004
    Location
    Melbourne, Australia
    Posts
    5,298
    I don't really understand your question. We are seeing the same question from such a different perspective.

    Regards.

  5. #5
    Join Date
    Jul 2003
    Location
    New York City
    Posts
    2,771
    Erm, basically, I'm still confused as to how I would do this, in say an Object Oriented enviroment.

  6. #6
    Join Date
    Jan 2004
    Location
    Melbourne, Australia
    Posts
    5,298
    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?

    Regards.

  7. #7
    Join Date
    Jul 2003
    Location
    The City of Roses
    Posts
    2,503
    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?)

    (Example tree)
    Code:
          D
       /     \
      B       F
     / \     / \
    A   C   E   G
    So, to find the smallest value in the tree (which would be the left-most node) would work something like this (psuedo code)
    Code:
    p = root
    while (p->left != NULL)
    	p = p->left
    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.

    Here is another tree algorithm that returns the next inorder node.
    Code:
    if (p->right != NULL)
    	p = p->right
    	while (p->left != NULL)
    		p = p->left
    	return p
    
    if (p->parent == NULL)
    	return NULL  // we're done
    
    if (p->parent->left == p)  // p is a left subtree
    	return p->parent
    
    while (p->parent != NULL && p->parent->right == p)  // while p is a right subtree
    	p = p->parent
    return p->parent
    With this algorithm we get

    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 07:54 AM.
    for(split(//,'))*))91:+9.*4:1A1+9,1))2*:..)))2*:31.-1)4131)1))2*:3)"'))
    {for(ord){$i+=$_&7;grep(vec($s,$i++,1)=1,1..($_>>3)-4);}}print"$s\n";

  8. #8
    Join Date
    Jul 2003
    Location
    New York City
    Posts
    2,771
    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.

Thread Information

Users Browsing this Thread

There are currently 1 users browsing this thread. (0 members and 1 guests)

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
HTML5 Development Center



Recent Articles