Tree problem

This is a discussion on Tree problem within the C Programming forums, part of the General Programming Boards category; First of all, hello everyone! I've been learning C and so far I've understood everything quite well. Now I'm stuck ...

  1. #1
    Registered User ndrez's Avatar
    Join Date
    Mar 2011
    Posts
    5

    Question Tree problem

    First of all, hello everyone!

    I've been learning C and so far I've understood everything quite well. Now I'm stuck at this seemingly easy assignment. I'm supposed to write a program that asks the user to input 10 elements of a tree and their parent codes. The program would then print the entire tree.
    Example:

    Input:

    Value of the 1st element: aaa
    Parent value: 0
    Value of the 2nd element: bbb
    Parent value: 1
    Value of the 3rd element: ccc
    Parent value: 1
    Value of the 4th element: ddd
    Parent value: 3
    Value of the 5th element: eee
    Parent value: 1
    Value of the 6th element: fff
    Parent value: 0
    Value of the 7th element: ggg
    Parent value: 6
    Value of the 8th element: hhh
    Parent value: 6
    Value of the 9th element: iii
    Parent value: 1
    Value of the 10th element: jjj
    Parent value: 0

    Output:

    Root
    ...aaa
    .....bbb
    .....ccc
    .......ddd
    .....eee
    .....iii
    ...fff
    .....ggg
    .....hhh
    ...jjj
    I have written several different codes, but they all only work in specific situations. Also there should not be any "fancy" commands. Just pointers, loops ands such things. Any ideas where should I start?

  2. #2
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,551
    Post the code for your best attempt so far.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  3. #3
    Registered User
    Join Date
    Sep 2008
    Location
    Toronto, Canada
    Posts
    1,832
    Hold the inputted values in arrays. For 0, print 3 dots. For 1 print 5 dots... looks like printing N*2+3 dots. Except that some have different indents... could be your typo.

  4. #4
    Registered User ndrez's Avatar
    Join Date
    Mar 2011
    Posts
    5
    Right now what I have is:

    Code:
    #include <stdio.h>
    #define max_n 50
    /**/
    /**/
    /**/
    int main()
    {
        int i;
        struct
           {
            char value[10][max_n];
            int parent[10];
           }
        element;
        element.parent[0]=0;
        for (i=0; i < 10; i++)
        {
          printf("%d. element value: ", i+1);
          scanf("%s", &element.value[i]);
          if (i==0) printf("1. parent code: 0\n");
          else
          {
                  printf("Parent code: ");
                  scanf("%d", &element.parent[i]);
                  if(element.parent[i]>i) printf("Such parent does not exist yet!\n");
          }
          puts("");
        }
        puts("Root");
        printf("  %s\n", element.value[0]);
        for(i=1; i<10; i++)
        {
                 /* ?????? */
        }
        
    }
    As you may see in the example, the values should be sorted before printing them out.

  5. #5
    Registered User ndrez's Avatar
    Join Date
    Mar 2011
    Posts
    5
    I've made some progress. The program even works a bit, if the elements are in correct order. Still, I need something to sort the values somehow and when the last parent happens to be 9, the program crashes.
    Code:
    #include <stdio.h>
    #define max_n 50
    /**/
    /**/
    
    int main()
    {
        int i, n, x[10];
        char space[10][10]={" ", "  ", "   ", "    ", "     ", "      ", "       ", "        ", "         "};
        struct
           {
           char value[10][max_n];
           int parent[10];
           }
        element;
        element.parent[0]=0;
        for (i=0; i < 10; i++)
        {
          printf("%d. element value: ", i+1);
          scanf("%s", &element.value[i]);
          if (i==0) printf("1. parent code: 0\n");
          else
          {
                  printf("Parent code: ");
                  scanf("%d", &element.parent[i]);
                  if((element.parent[i]>i)||(element.parent[i]<0)||(element.parent[i]>9))
                   {
                    printf("Wrong parent!\n");
                    element.parent[i]=i;
                   }
          }
          puts("");
        }
        puts("Root");
    
        for(i=0; i<10; i++)
        {
         if(element.parent[i]==0) x[i]=0;
          for(n=1; n<9; n++)
          {
         if((element.parent[i]==n)&&(!(element.parent[i]==element.parent[i-1]))) x[i]=x[i-1]+1;
          else if ((element.parent[i]==n)&&(element.parent[i]==element.parent[i-1])) x[i]=x[i-1];
         }
        }
         for(i=0; i<10; i++)
        {
        printf("%s%s\n", space[x[i]], element.value[i]);
    }
        getch();
    }
    Any help would be appreciated.

  6. #6
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,551
    You need a loop to do something like
    parent = element.parent[parent];

    Until you get to parent == 0


    For each time around the loop, you increase the amount of indentation.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  7. #7
    Registered User
    Join Date
    Nov 2008
    Posts
    119
    Why don't you use a tree struct to store your tree? A struct that holds the data and a pointer to a struct of it's type for the children.

  8. #8
    Registered User ndrez's Avatar
    Join Date
    Mar 2011
    Posts
    5
    OK, while some time has passed, I haven't had time to complete this. Now I was given a second chance with this assignment. I've figured out by my self how to do it on paper and now I need some help to put it in code.
    First, I must find an element whose parent is 0 (the root), remember its position in the array (let it be x) and then print it.
    Then, I must find an element whose parent code is x, remember its position in the array (let it be y) and then print it (with 1 leading space).
    Then, I must find an element whose parent code is y, remember its position in the array (let it be z) and then print it (with 2 leading spaces).
    ......and so on (until the counter is 10?)
    If there are no more children, the program would go back one step and search for the next child, until there are no more branches/children left.

    I tried to write the program using these instructions, but I ended up with horrific amount of nested loops and messed it all up. What I need is some advice how to position the loops correctly and whether it is more useful to print the values out right away or later.

  9. #9
    Registered User ndrez's Avatar
    Join Date
    Mar 2011
    Posts
    5
    bump

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Binary Tree Search
    By C++Newbie in forum C++ Programming
    Replies: 7
    Last Post: 04-05-2011, 01:17 AM
  2. Undirected graph and Binary Tree problem
    By arafat21 in forum C Programming
    Replies: 3
    Last Post: 05-02-2008, 05:52 AM
  3. AVL tree balancing problem
    By sweets in forum C++ Programming
    Replies: 4
    Last Post: 05-06-2004, 12:17 PM
  4. Tutorial review
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 03-22-2004, 08:40 PM
  5. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21