Example
Typically we represent an anary tree (one with potentially unlimited children per node) as a binary tree, (one with exactly two children per node). The "next" child is regarded as a sibling. Note that if a tree is binary, this representation creates extra nodes.
We then iterate over the siblings and recurse down the children. As most trees are relatively shallow - lots of children but only a few levels of hierarchy, this gives rise to efficient code. Note human genealogies are an exception (lots of levels of ancestors, only a few children per level).
If necessary back pointers can be kept to allow the tree to be ascended. These are more difficult to maintain.
Note that it is typical to have one function to call on the root and a recursive function with extra parameters, in this case tree depth.
struct node
{
struct node *next;
struct node *child;
std::string data;
}
void printtree_r(struct node *node, int depth)
{
int i;
while(node)
{
if(node->child)
{
for(i=0;i<depth*3;i++)
printf(" ");
printf("{\n"):
printtree_r(node->child, depth +1);
for(i=0;i<depth*3;i++)
printf(" ");
printf("{\n"):
for(i=0;i<depth*3;i++)
printf(" ");
printf("%s\n", node->data.c_str());
node = node->next;
}
}
}
void printtree(node *root)
{
printree_r(root, 0);
}
