Thread: 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.

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.

Originally Posted by laserlight

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.

Can a node only have 1 child? How do you get siblings?

Originally Posted by NeonBlack

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.

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.

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.

Originally Posted by iMalc

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