Print a n-ary tree in C

user_13701963 0
Viewed 1031
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct _Tree 
{ 
    struct _Tree *child;     
    struct _Tree *next; 
    char name[50];
}Tree; 

Tree* memoryTree(char nombre_fichero[50]);
Tree*add(Tree*raiz, char name_root[50], char name_newnode[50]);
Tree*addSibling(char dato[50], Tree*top);
void PrintSiblings(Tree*root);

int main()
{
    char name_temp[50];
    char name_root[50];
    char name_newnode[50];

    Tree*Root; Root = NULL;

    Root = memoryTree("A");

    add(Root, "A", "1");
    add(Root, "A", "2");
    add(Root, "A", "3");
    add(Root, "1", "1.1");
    add(Root, "1.1", "1.1.1");
    add(Root, "1.1.1", "1.1.1.1");
    add(Root, "2", "2.1");
    add(Root, "2", "2.2");
    add(Root, "2", "2.3");
    add(Root, "2.3", "2.3.1");

    /* I'm printing it here for the moment in order to verify my new nodes addittions*/
    Tree*Temp = Root;

    while(Temp->child != NULL)
    {

        Tree*piv = Temp;

        if(piv->child != NULL)
        {
            while(piv != NULL)
            {
                if(piv->child)
                {
                    printf("\nRoot: %s\n", piv->name);
                    printf("Names:");
                    PrintSiblings(piv->child);
                    printf("\n");   
                }                                                   
                piv = piv->next;
            }
        }

        printf("\n");
        Temp = Temp->child;     
    }
        system("pause");
    system("cls");
    return 1;
}


void PrintSiblings(Tree*top)
{
    if(top==NULL)
    {
        //printf("\nNO HAY HERMANOS\n");

    }else
    {
        while(top!=NULL)
        {
            printf("->%s",top->name);
            top=top->next;
        }
    }
}

Tree*memoryTree(char node_name[50])
{
    Tree*root;
    root  = (Tree*)malloc(sizeof(Tree));

    if(root != NULL)
    {    
        root->child = NULL;
        strcpy(root->name, node_name);
        root->next = NULL;
    }

 return root;
}

Tree*add(Tree*root, char name_root[50], char name_newnode[50])
{
    if (root == NULL)
    {
        return NULL;
    }
    else
    {
        if(strcmp(root->name, name_root) == 0)
        {
            //If a child-node is already added, then we add it as a Sibling
            if(root->child == NULL)
            {
                root->child = memoryTree(name_newnode);
            }
            else
            {
                root->child->next = addSibling(name_newnode, root->child->next);
            }

            return root;
        } 
        else
        {
            Tree *found;
            /*Search in Siblings*/
            if((found=add(root->next,name_root,name_newnode)) != NULL)
            {
                return root;
            }
            else
            {
                Tree *found2;     
                if((found2 = add(root->child,name_root,name_newnode)) != NULL)
                {
                    return root;
                }
            }           


        }
    }

}

Tree*addSibling(char new_node[50], Tree*top)
{
    Tree*newN, *aux;    
    newN = memoryTree(new_node);
    if(top==NULL)
    {
        top = newN;
    }
    else
    {
        aux=top;
        while(aux->next != NULL)
        {
            aux = aux->next;
        }

        aux->next = newN;
    }   
    return top;
}

This method is only printing until the 3rd child (I think I might need to implement a recursive function but I'm was not able to do so)

Spacing is not truly necessary at all. I was just trying to print it like:

A. 1,2,3..

  1. 1.1,1.2,..

  2. 2.1, 2.2,

[...]

2.2 2.2.1, 2.2.2,...

My Output is:

Root: A
Names:->1->2->3


Root: 1
Names:->1.1

Root: 2
Names:->2.1->2.2->2.3


Root: 1.1
Names:->1.1.1


Root: 1.1.1
Names:->1.1.1.1

The output should print the "2.3" node as well as its siblings ("2.3.1")

Do have any ideas on how to get this done correctlty?

tree c
1 Answers

Since you build up your tree recursively in add(), the simplest approach seems to be a recursive printing function instead of your iterative loop. The one I came up with outputs:

> ./a.out
Node: A
Children:
    Node: 1
    Children:
        Node: 1.1
        Children:
            Node: 1.1.1
            Children:
                Node: 1.1.1.1
    Node: 2
    Children:
        Node: 2.1
        Node: 2.2
        Node: 2.3
        Children:
            Node: 2.3.1
    Node: 3
>

I reworked your code to simplify it and address some style issues:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct _Tree 
{
    struct _Tree *child;
    struct _Tree *next;
    char name[50];
} Tree; 

Tree *memoryTree(const char *node_name)
{
    Tree *root = malloc(sizeof(Tree));

    if (root != NULL)
    {
        root->child = NULL;
        strcpy(root->name, node_name);
        root->next = NULL;
    }

    return root;
}

Tree *addSibling(const char *node_name, Tree *node)
{
    Tree *new_node = memoryTree(node_name);

    if (node == NULL)
    {
        node = new_node;
    }
    else
    {
        Tree *aux = node;

        while (aux->next != NULL)
        {
            aux = aux->next;
        }

        aux->next = new_node;
    }

    return node;
}

Tree *add(Tree *node, const char *name_root, const char *node_name)
{
    if (node == NULL)
    {
        return NULL;
    }

    if (strcmp(node->name, name_root) == 0)
    {
        node->child = addSibling(node_name, node->child);

        return node;
    }
    
    Tree *found;
    /* Search in Siblings */
    if ((found = add(node->next, name_root, node_name)) != NULL)
    {
        return found;
    }

    if ((found = add(node->child, name_root, node_name)) != NULL)
    {
        return found;
    }

    return NULL;
}

void printTabs(int count)
{
    for (int i = 0; i < count; i++)
    {
        putchar('\t');
    }
}

void printTreeRecursive(Tree *node, int level)
{
    while (node != NULL)
    {
        printTabs(level);
        printf("Node: %s\n", node->name);

        if (node->child != NULL)
        {
            printTabs(level);
            printf("Children:\n");
            printTreeRecursive(node->child, level + 1);
        }

        node = node->next;
    }
}

void printTree(Tree *node)
{
    printTreeRecursive(node, 0);
}

int main()
{
    Tree *root = memoryTree("A");

    add(root, "A", "1");
    add(root, "A", "2");
    add(root, "A", "3");
    add(root, "1", "1.1");
    add(root, "1.1", "1.1.1");
    add(root, "1.1.1", "1.1.1.1");
    add(root, "2", "2.1");
    add(root, "2", "2.2");
    add(root, "2", "2.3");
    add(root, "2.3", "2.3.1");

    printTree(root);

    return 1;
}
user_57712690
Related