Describing a tree

[Mok-Kong Shen]

A possibly dumb question: Given a labeled or unlabeled tree
(in the sense of graphs), how could one best use C to describe it?
(I don't exactly know but have the impression that this might be
rather simple in Lisp.)

Thanks.

M. K. Shen

 

[Malcolm McLean]

A possibly dumb question: Given a labeled or unlabeled tree
(in the sense of graphs), how could one best use C to describe it?
(I don't exactly know but have the impression that this might be
rather simple in Lisp.)

An informal and possibly bug-ridden specification of Lisp in C

typedef struct cell
{
struct cell *next;
struct cell *child;
};

typedef struct leaf
{
struct cell *next; /* set to null to indicate this is a leaf */
void *symbol;
};

union conscell
{
struct cell;
struct leaf;
};

union conscell nil;

nil.leaf.next = 0;
nil.leaf.symbol = 0;

Basically you need two pointers for each node, and a hook to hang data
off for the leaves. You need some way of flagging a leaf, so here we
have the next pointer set to null. That means you need to set to "nil"
to indicate termination.

 

[Nick Keighley]

A possibly dumb question: Given a labeled or unlabeled tree
(in the sense of graphs), how could one best use C to describe it?

what form is it in now or how are you going to enter it?

/* tree.c */

#include <stdio.h>

typedef struct tree_tag
{
char *data;
struct tree_tag *left;
struct tree_tag *right;
} Tree;


void walk (Tree *tree)
{
if (tree != NULL)
{
printf ("%s ", tree->data);
walk (tree->left);
walk (tree->right);
}
}

int main (void)
{
Tree yggdrasil[] =
{
{"red", &yggdrasil[1], &yggdrasil[2]},
{"blue", &yggdrasil[3], &yggdrasil[4]},
{"black", 0, 0},
{"yellow", 0, 0},
{"green", 0, 0}
};

walk (yggdrasil);
return 0;
}

(I don't exactly know but have the impression that this might be
rather simple in Lisp.)

probably. But would you have to learn Lisp first? (not necessarily a
bad idea). If you like s-exprs why not write a parser for them in C?

 

[Mok-Kong Shen]

I find it hard to disagree with you.

What do you mean by "describe"? A data structure? A set of algorithms?

What do you mean by "best"? Most widely popular? Most space-efficient?
Most time-efficient? Most flexible? (And if you mean most flexible, what
do you mean by "flexible"?...)



Then why not do it in Lisp instead?

I meant one could in Lisp (if my poor knowledge about Lisp doesn't
betray me) write down the tree simply as a Lisp expression. Of course
one could then process it in any way one likes. To your last question
the answer is that I happen to be familiar a little bit more with C
than with Lisp, so it's basically an issue of convenience to hope that
similar simplicity were also possible in C.

M. K. Shen

 

[Malcolm McLean]

I meant one could in Lisp (if my poor knowledge about Lisp doesn't
betray me) write down the tree simply as a Lisp expression.

We can do this.

You simply write a C function that accepts a character string, and
returns a tree. The string contains a set of nested parentheses that
specify the tree and the labels at its leaves. You then enter the
trees in the C source file using an ordinary text editor. If the need
to quote strings becomes a nuisance, you can read in the strings as
data.

 

[Ben Bacarisse]

I meant one could in Lisp (if my poor knowledge about Lisp doesn't
betray me) write down the tree simply as a Lisp expression.

You can do this in C (modern C99 at least) like this:

typedef struct node {
const char *label;
struct node *left, *right;
} Node;

/* and then inside a function such as main: */

Node *my_tree =
(Node){"root", &(Node){"left", 0, 0}, &(Node){"right", 0, 0}};

This is not often done because C programs will typically have to process
trees (or graphs) that are supplied as input data, not expressed
literally in the code. It is trickier if the graph is not a tree, but
that is true for Lisp as well (and you said you had a tree anyway).

However, if language familiarity were not an issue, Lisp would the
natural choice.

 

[Ersek, Laszlo]

<snip>

You can do this in C (modern C99 at least) like this:

typedef struct node {
const char *label;
struct node *left, *right;
} Node;

/* and then inside a function such as main: */

Node *my_tree =
(Node){"root", &(Node){"left", 0, 0}, &(Node){"right", 0, 0}};

Or, in C89,

#include <stdlib.h>

struct node
{
const char *label;
struct node *left, *right;
};

static struct node *
node(const char *label, struct node *left, struct node *right)
{
struct node *ret;

ret = malloc(sizeof *ret);
if (0 == ret) {
abort();
}
ret->label = label;
ret->left = left;
ret->right = right;
return ret;
}

int
main(void)
{
struct node *root;

root = node(
"root",
node("left", 0, 0),
node("right", 0, 0)
);
return 0;
}

I think the relative order of two node() invocations is unspecified,
except if there is a (recursive) ancestor-descendant relationship between
the nodes constructed by said two invocations. For example, if we were to
modify node() so that it prints "label", the order of "right" and "left"
in the above would be unspecified. "root" would be printed in the end.

Since function invocations don't overlap, you could avoid malloc() if you
could ascertain a compile-time upper bound on the number of nodes:

#define NNODES ((size_t)10)

static struct node *
node2(const char *label, struct node *left, struct node *right)
{
static struct node nodes[NNODES];
static size_t used;
struct node *ret;

if (NNODES == used) {
abort();
}
ret = nodes + used++;
ret->label = label;
ret->left = left;
ret->right = right;
return ret;
}

Finally, I think there might be an environmental limit on how deep you can
nest the node() function calls... Yes, C89 5.2.4.1 "Translation limits"
states, "32 nesting levels of parenthesized expressions within a full
expression".

lacos

 

[Gene]

A possibly dumb question: Given a labeled or unlabeled tree
(in the sense of graphs), how could one best use C to describe it?
(I don't exactly know but have the impression that this might be
rather simple in Lisp.)

Thanks.

M. K. Shen

This is a brilliant question. Even in lisp there are many ways to do
it. Which you choose depends on design goals and requirements. Some
questions to consider:

0. Does the tree have special structure (like a search tree, priority
queue, or prefix tree)?
1. How important is space efficiency? (Is the tree large compared to
available memory?)
2. How many children per node?
3. Are children to be dynamically or statically identified/named?
4. If the number of children varies, how widely?
5. Is constant time access to parents required? Siblings?
6. Are the data represented exogenously with respect to the tree?
(I.e. is it already stored in another tree, so you only need to point
to it?) Or will they be endogenous?
7. Are tree nodes to be exogenous for some other data structure
(pointed to by it)?
8. Does the tree need to be persistent?
9. Is a human-readable representation required?
10. Do tree operations need to be atomic (in a multi-threading
environment)?
11. Do tree operations need to be transactions (in the database sense
of commit/rollbacck)?
12. Is it better to pre-allocate all tree storage or allocate on the
fly? Is the max number of nodes limited?
13. If the tree is ordered, do you need data ordinals?
14. If the tree is for data access, does it need to be self-height-
limiting or -balancing?
15. Do tree operations need to be undoable?

All these and others affect the "best" C representation. If you don't
have many such criteria, then that's a criterion in itself. It
alllows you can trade between simplicity and flexibility for future
new requirements.

If you narrow the question a bit, we can get to the details.

 

[Mok-Kong Shen]

This is a brilliant question. Even in lisp there are many ways to do
it. Which you choose depends on design goals and requirements. Some
questions to consider:

0. Does the tree have special structure (like a search tree, priority
queue, or prefix tree)?
1. How important is space efficiency? (Is the tree large compared to
available memory?)
2. How many children per node?
3. Are children to be dynamically or statically identified/named?
4. If the number of children varies, how widely?
5. Is constant time access to parents required? Siblings?
6. Are the data represented exogenously with respect to the tree?
(I.e. is it already stored in another tree, so you only need to point
to it?) Or will they be endogenous?
7. Are tree nodes to be exogenous for some other data structure
(pointed to by it)?
8. Does the tree need to be persistent?
9. Is a human-readable representation required?
10. Do tree operations need to be atomic (in a multi-threading
environment)?
11. Do tree operations need to be transactions (in the database sense
of commit/rollbacck)?
12. Is it better to pre-allocate all tree storage or allocate on the
fly? Is the max number of nodes limited?
13. If the tree is ordered, do you need data ordinals?
14. If the tree is for data access, does it need to be self-height-
limiting or -balancing?
15. Do tree operations need to be undoable?

All these and others affect the "best" C representation. If you don't
have many such criteria, then that's a criterion in itself. It
alllows you can trade between simplicity and flexibility for future
new requirements.

If you narrow the question a bit, we can get to the details.

Actually I first came to the issue from a rather humble goal: Simply
to describe something of the genre of natural trees, without any need
of processing.

M. K. Shen

 

[Dann Corbit]

A possibly dumb question: Given a labeled or unlabeled tree
(in the sense of graphs), how could one best use C to describe it?
(I don't exactly know but have the impression that this might be
rather simple in Lisp.)

The most generic way that I can imagine is a recursive skiplist of
skiplists (each skiplist at any level can contain skiplists).
In that way, the number of leaves for any node is arbitary.

Otherwise, we will have a kind of tree which is not generic (e.g. a
binary tree or a red-black tree or some other tree). A skiplist of
skiplists can be any kind of tree.

Abstract algorithms are much easier (for me) to code in C++ than in C.

With C99 you could use variant arrays which would be another approach
for generic behavior.

My skiplist of skiplists idea assumes that it is possible to order the
objects in some way. If this is not possible then a recursive linked
list of linked lists is another alternative.

So, my notion of a tree is a collection of nodes, each of which can have
zero or more ancestors and which also has a root node. The type of the
node should also be able to change at each level, if possible. In this
way we might describe an arbitrary object as a tree (e.g. a house is a
tree, with root object being house, which is a collection of rooms, each
room consists of a collection of properties and a collection of
contained items, etc.)

 

[Michael Angelo Ravera]

A possibly dumb question: Given a labeled or unlabeled tree
(in the sense of graphs), how could one best use C to describe it?
(I don't exactly know but have the impression that this might be
rather simple in Lisp.)

Thanks.

M. K. Shen

So, let's give an example:
The LISP structure (A (B C) D (E (F G) H)) consists of 4 elements. The
first and third of these are scalars, the second and fourth are lists.
The last element is a list consisting of a scalar, a two-element list,
and then a scalar,

I suppose that it would be possible in C to create a polyvalent and
variable argument function Construct_List to do the same thing that
LISP's CONS function does and the equivalent to <LISP>(CONS Z (A (B C)
D (E (F G) H)) )</LISP> would be
<C>
Z = Construct_List ('A', Construct_List ('B', 'C'), 'D',
Construct_List ('E', Construct_List ('F, 'G'), 'H'));
</C>

C has a great syntax for stuffing arrays. It's not as good at stuffing
lists, mainly because there is no native support for trees in C. There
are probably list and tree packages all over the place the same as
there is a standard library, but the lanaguage itself doesn't
contemplate trees. You (or the package implementor) has to provide
your own abstraction.

 

[Ersek, Laszlo]

On Tue, 20 Jul 2010, Dann Corbit wrote:

[snip]

Otherwise, we will have a kind of tree which is not generic (e.g. a
binary tree or a red-black tree or some other tree).

A binary tree can be made "generic", just don't call the two child
pointers "left" and "right"; call them "next_sibling" and "first_child".
This leads to arbitrary arity ("arbitrarity", lol). IIRC, Malcolm McLean's
first example in this thread was written like that.

(Sorry for using "lol"; couldn't resist.)

lacos

 

[Alan Curry]

You can do this in C (modern C99 at least) like this:

typedef struct node {
const char *label;
struct node *left, *right;
} Node;

/* and then inside a function such as main: */

Node *my_tree =
(Node){"root", &(Node){"left", 0, 0}, &(Node){"right", 0, 0}};

You don't need deep nesting to create a recursive structure. You can put the
nodes in an array, like this:

struct node {
const char *label;
const struct node *left, *right;
};

const struct node mytree[] = {
{"root", &mytree[1], &mytree[2]},
{"left", &mytree[3], 0},
{"right", 0, &mytree[4]},
{"leftleft", 0, 0},
{"rightright", 0, 0}
};

Which lets you get the whole thing statically allocated in readonly memory.
If you're generating a C representation of a tree that is originally
represented in some other form, this is the way to go. I don't recommend
writing it by hand though. It's too hard to make sure the links all point the
the right places.

 

[Ben Bacarisse]

You don't need deep nesting to create a recursive structure. You can put the
nodes in an array, like this:

Yes, I know. I should have been more clear. I was not saying this way
the best way and certainly not the only way (actually I am not even
saying it is a good way). I wanted only to dispel the idea that a tree
can be written as a Lisp expression but not as a C expression.

<snip static tree example>

 

[Nick Keighley]

On 20 July, 13:10, Mok-Kong Shen <[email protected]> wrote:

what form is it in now or how are you going to enter it?

/* tree.c */

#include <stdio.h>

typedef struct tree_tag
{
   char *data;
   struct tree_tag *left;
   struct tree_tag *right;
} Tree;

void walk (Tree *tree)
{
   if (tree != NULL)
   {
       printf ("%s ", tree->data);
       walk (tree->left);
       walk (tree->right);
   }
}

int main (void)
{
   Tree yggdrasil[] =
   {
       {"red", &yggdrasil[1], &yggdrasil[2]},
       {"blue", &yggdrasil[3], &yggdrasil[4]},
       {"black", 0, 0},
       {"yellow", 0, 0},
       {"green", 0, 0}
   };

   walk (yggdrasil);
   return 0;
}

Error E2063 tree1.c 27: Illegal initialization in function main
*** 1 errors in Compile ***

I'm surprised! It compiled and executed ok for me with an old Windows
compiler. And on gcc unless I stuck -pedantic on... ok fair cop

your example not compile here; afther some try in C i wrote
it in RosAsm [one assembly + debugger]

why not write all in assembly? it is 1000 times better than C ...

go forth and multiply

<snip>

 

[Nick Keighley]

"Mok-Kong Shen" <[email protected]> ha scritto nel messaggionews:[email protected]...

A possibly dumb question: Given a labeled or unlabeled tree
(in the sense of graphs), how could one best use C to describe it?
(I don't exactly know but have the impression that this might be
rather simple in Lisp.)

i think one tree like one tree of directory
every node could have nodes [in number if 0,1,2,3,4,5,6 ecc.
that are other directory so all with the use of malloc]

most other posts are describing binary (where their are only two
possible children of each node) you are describing more general n-ary
trees. Its trivial (well fairly easy to transform an n-arry tree into
a binary tree.

something like

         dir2  /--dir_B
        /     /
    dir1---dir3--dir_A
        \     \\
         dir4  \\---dir_D
                \---dir_C

each node has one branch pointing to its siblings (nodes having the
same parent) and the other to its children

typedef struct node {
       char          *Data;
       struct node **Nodes;

}Node;

where Nodes[0] is the node father [always 1]
Nodes[0]==0 only if that node is the root node

Nodes==0 means one error

but what about one structure like this

         dir2  /--dir_B
        /  |  /    |
    dir1---dir3--dir_A
        \  |  \\     \
         dir4  \\---dir_D
                \---dir_C

it is a tree? i say no,

it's not a tree, no

but in this case i would write that
using

typedef struct node {
       char         *Data;
       struct node **NodesInThisNode;
       struct node **NodesToThisNode;



}Node;

any good book on algorithms will discuss all this and more

 

[Nick Keighley]

Actually I first came to the issue from a rather humble goal: Simply
to describe something of the genre of natural trees,

"natural trees"!? You mean like The Larch? What properties natural
trees do you wish to describe? Phylogeny? Morphology? Leaf count?
Beetle count?

without any need of processing.

I think turning a natural treee into a computer science tree is
inevitably going to require some processing

 

[Ian Collins]

On 20 July, 13:10, Mok-Kong Shen<[email protected]> wrote:

A possibly dumb question: Given a labeled or unlabeled tree
(in the sense of graphs), how could one best use C to describe it?

what form is it in now or how are you going to enter it?

/* tree.c */

typedef struct tree_tag
{
char *data;
struct tree_tag *left;
struct tree_tag *right;
} Tree;

void walk (Tree *tree)
{
if (tree != NULL)
{
printf ("%s ", tree->data);
walk (tree->left);
walk (tree->right);
}
}

int main (void)
{
Tree yggdrasil[] =
{
{"red",&yggdrasil[1],&yggdrasil[2]},
{"blue",&yggdrasil[3],&yggdrasil[4]},
{"black", 0, 0},
{"yellow", 0, 0},
{"green", 0, 0}
};

walk (yggdrasil);
return 0;
}

Error E2063 tree1.c 27: Illegal initialization in function main
*** 1 errors in Compile ***

I'm surprised! It compiled and executed ok for me with an old Windows
compiler. And on gcc unless I stuck -pedantic on... ok fair cop

It's perfectly valid C.

 

[Ian Collins]

"Nick Keighley"<[email protected]> ha scritto nel messaggio
>>Error E2063 tree1.c 27: Illegal initialization in
function main

I'm surprised! It compiled and executed ok for me with an old Windows
compiler. And on gcc unless I stuck -pedantic on... ok fair cop

the C compiler not compile it due to the above error
but the C++ compiler compile it [i rename the file in tree1.cpp]

A decent C++ compile will whinge about (but still compile) the
assignments of string literals to char*. Alas, C compilers don't.

 

[Stefan Ram]

A possibly dumb question: Given a labeled or unlabeled tree
(in the sense of graphs), how could one best use C to describe it?

I wrote this once:

3
/ \
/ \
1 4
/ \
/ \
0 2

main.c

#include <stdio.h> /* printf, putchar */
#include <stdlib.h> /* EXIT_SUCCESS */
typedef struct tree
{ struct tree * left; int value; struct tree * right; } * TREE;
void print( TREE const tree )
{ if( tree ){ putchar( '(' ); print( tree->left );
printf( "%d", tree->value ); print( tree->right ); putchar( ')' ); }}
extern struct tree t1, t0, t2, t4; struct tree t3 =


{ &t1, 3, &t4 },


t1 ={ &t0, 1, &t2 }, t4 ={ 0, 4, 0 },


t0 ={ 0, 0, 0 }, t2 ={ 0, 2, 0 };



int main( void ){ print( &t3 ); putchar( '\n' ); return EXIT_SUCCESS; }

::std::cout

(((0)1(2))3(4))

You can actually see the tree in the source code. And this small
portable program even contains a full-blown tree dumper that dumps
the tree to stdout. The output format even is an S-expression, which
you should like. The grammar is

<tree> ::= [<entry>].
<entry> ::= '(' <tree> <number> <tree> ')'.
<number> ::= '0' | '1' | '2' | '3' | '4'.

Look how nicely and directly the grammar determinates the
structure of the function »print«!

[] --> if,
'(' <tree> ... --> { putchar( '(' ); ....