Name this tree

This is a discussion on Name this tree within the C Programming forums, part of the General Programming Boards category; Is there a name for a "tree" of this sort: Code: typedef struct _qnode { void *data; struct _qnode *parent; ...

  1. #1
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300

    Name this tree

    Is there a name for a "tree" of this sort:

    Code:
    typedef struct _qnode {
    	void *data;
    	struct _qnode *parent;
    	struct _qnode *child;
    	struct _qnode *prev_sibling;
    	struct _qnode *next_sibling;
    } qnode;
    It is not exactly a graph.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,451
    Quote Originally Posted by MK27
    It is not exactly a graph.
    It can be seen as a vertex with up to four edges in a graph, but I guess that you are looking for a name that is more specific.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by laserlight View Post
    It can be seen as a vertex with up to four edges in a graph, but I guess that you are looking for a name that is more specific.
    Yeah, I suppose it is just a graph with some "implementation specific" details thrown in.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  4. #4
    Registered User NeonBlack's Avatar
    Join Date
    Nov 2007
    Posts
    435
    Can a node only have 1 child? How do you get siblings?
    I copied it from the last program in which I passed a parameter, which would have been pre-1989 I guess. - esbo

  5. #5
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by NeonBlack View Post
    Can a node only have 1 child? How do you get siblings?
    The child is the head of a linked list of siblings (hence prev sib, next sib), so in a strict sense, yes you only have one connected child, in another sense, no, you traverse thru "child" into a list of children, and you can return to the parent from any child in the list. You can only have one parent, which means it narrows down to a tree (unlike a graph).

    So that is a specific idea that may or may not be a common practice; if it is, it may or may not have possibilities (or limitations) I haven't thought of that someone else has. You could do a filesystem this way maybe.
    Last edited by MK27; 03-06-2010 at 11:07 AM.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  6. #6
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,236
    This data structure defines a tree where each parent may have an arbitrary number of children. The parent points to one of its children, as well as its own parent. The children themselves are organized in a circular linked list.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  7. #7
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,295
    My first thought was a grid rather than a tree. From each node you can go up, down, left or right.
    For node M for example, parent = H, child = R, prev_sibling = L, next_sibling = N
    Code:
    A---B---C---D---E
    |   |   |   |   |
    F---G---H---I---J
    |   |   |   |   |
    K---L---M---N---O
    |   |   |   |   |
    P---Q---R---S---T
    However that isn't quite correct because for L and N to be siblings they'd have to have the same parent, instead of G and I respectively.

    By making L and N's parent also H, I believe you do indeed end up with about what brewbuck posted. However I'd expect that rather than a circular linked list, the parent would point to the first child and that child's prev_sibling would be NULL, and this would be the beginning of a doubly-linked list of siblings. Of course without further info there's no wrong answer here.
    In this case both the parent/child and sibling lists are "doubly-linked" or linked in both directions. I'm more used to a tree with only across and down links which is the same but using a singly-linked list for both parts. Either one can represent an N-ary tree.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  8. #8
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by iMalc View Post
    However I'd expect that rather than a circular linked list, the parent would point to the first child and that child's prev_sibling would be NULL, and this would be the beginning of a doubly-linked list of siblings.
    Yeah, by having the null ends you can do a traversal parent->children->(children's children, back thru parent)->"uncle"->"nephews", etc. Going thru the children's children until you reach a null child you can cover the tree, but you have to leave a crumb trail or some marker -- like a wormhole
    Last edited by MK27; 03-06-2010 at 12:42 PM.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Binary Tree Search
    By C++Newbie in forum C++ Programming
    Replies: 7
    Last Post: 04-05-2011, 01:17 AM
  2. Interpreter.c
    By moussa in forum C Programming
    Replies: 4
    Last Post: 05-28-2008, 05:59 PM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21