Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > Describing a tree

Reply
Thread Tools

Describing a tree

 
 
Mok-Kong Shen
Guest
Posts: n/a
 
      07-20-2010

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
 
Reply With Quote
 
 
 
 
Malcolm McLean
Guest
Posts: n/a
 
      07-20-2010
On Jul 20, 3:10*pm, Mok-Kong Shen <(E-Mail Removed)> 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?
> (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.
 
Reply With Quote
 
 
 
 
Nick Keighley
Guest
Posts: n/a
 
      07-20-2010
On 20 July, 13:10, Mok-Kong Shen <(E-Mail Removed)> 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 */

#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?
 
Reply With Quote
 
Mok-Kong Shen
Guest
Posts: n/a
 
      07-20-2010
Richard Heathfield wrote:
> Mok-Kong Shen 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?

>
> 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"?...)
>
>> (I don't exactly know but have the impression that this might be
>> rather simple in Lisp.)

>
>
> 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
 
Reply With Quote
 
Malcolm McLean
Guest
Posts: n/a
 
      07-20-2010
On Jul 20, 4:24*pm, Mok-Kong Shen <(E-Mail Removed)> wrote:
>
> 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.


 
Reply With Quote
 
Ben Bacarisse
Guest
Posts: n/a
 
      07-20-2010
Mok-Kong Shen <(E-Mail Removed)> writes:
<snip>
> 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.

--
Ben.
 
Reply With Quote
 
Ersek, Laszlo
Guest
Posts: n/a
 
      07-20-2010
On Tue, 20 Jul 2010, Ben Bacarisse wrote:

> Mok-Kong Shen <(E-Mail Removed)> writes:
> <snip>


>> 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}};


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
 
Reply With Quote
 
Gene
Guest
Posts: n/a
 
      07-20-2010
On Jul 20, 8:10*am, Mok-Kong Shen <(E-Mail Removed)> 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?
> (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.



 
Reply With Quote
 
Mok-Kong Shen
Guest
Posts: n/a
 
      07-20-2010
Gene wrote:

> 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
 
Reply With Quote
 
Dann Corbit
Guest
Posts: n/a
 
      07-20-2010
In article <i243o2$jcb$03$(E-Mail Removed)-online.com>, mok-kong.shen@t-
online.de says...
>
> 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.)
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Describing pipelined hardware Jonathan Bromley VHDL 50 06-22-2006 03:23 PM
describing a file system in xml uvts_cvs@yahoo.com XML 0 03-11-2005 10:02 AM
What am I describing? Gloria Goitre Computer Support 5 02-12-2005 04:05 AM
syntax/notation used in describing c's grammar ben C Programming 4 08-20-2004 07:38 PM
B tree, B+ tree and B* tree Stub C Programming 3 11-12-2003 01:51 PM



Advertisments