Is there a name for a "tree" of this sort:
It is not exactly a graph.Code:typedef struct _qnode { void *data; struct _qnode *parent; struct _qnode *child; struct _qnode *prev_sibling; struct _qnode *next_sibling; } qnode;
Is there a name for a "tree" of this sort:
It is not exactly a graph.Code:typedef struct _qnode { void *data; struct _qnode *parent; struct _qnode *child; struct _qnode *prev_sibling; struct _qnode *next_sibling; } qnode;
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
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.Originally Posted by MK27
Look up a C++ Reference and learn How To Ask Questions The Smart WayOriginally Posted by Bjarne Stroustrup (2000-10-14)
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
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
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 12:07 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
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); //}
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
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.Code:A---B---C---D---E | | | | | F---G---H---I---J | | | | | K---L---M---N---O | | | | | P---Q---R---S---T
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"
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 01: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