String as the name of bin. tree node/root + inorder traversal question

This is a discussion on String as the name of bin. tree node/root + inorder traversal question within the C Programming forums, part of the General Programming Boards category; Greetings to all, I have a binary tree, in which data must be entered manually. Here is my code: Code: ...

  1. #1
    Registered User bbanelli's Avatar
    Join Date
    Nov 2007
    Location
    Croatia, Zagreb
    Posts
    5

    String as the name of bin. tree node/root + inorder traversal question

    Greetings to all,

    I have a binary tree, in which data must be entered manually. Here is my code:

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    typedef struct cell_tag {
            char label[20];
            struct cell_tag *leftchild;
            struct cell_tag *rightchild;
            } celltype;
    
    typedef celltype *node;
    typedef celltype *BTREE;
    
    //I suppose the problem lies in several lines below?
    
    celltype *insert (char *temp){
         celltype *cvor = (celltype*) malloc (sizeof (celltype) );
         cvor -> label[20] = temp[20];
         if (temp[0] == '0'){
           cvor->leftchild = NULL;
           cvor->rightchild = NULL;
           }
         return cvor;
    }      
    
    //insert recursive function; program accepts data and does next left child; "0" makes an
    //empty child and "switches" to right child, recursively
    
    void ucitavanje (celltype *BTREE) {
         char temp[20];
         printf ("\nUpisite ime lijevog djeteta od %s: ",BTREE->label);
         gets (temp);
    
    //... or somewhere here?
    
         BTREE -> leftchild = (celltype*) insert (temp);
         if (temp[0] != '0')
           ucitavanje (BTREE->leftchild);
         printf("\nUpisite ime desnog djeteta od %s: ",BTREE->label);
         gets (temp);
         BTREE -> rightchild = (celltype*) insert (temp);
         if (temp[0] != '0')
           ucitavanje (BTREE->rightchild);
         exit(0);
    }
    
    int main(void){
        celltype TREE;
        printf("Upisite oznaku korijena vaseg stabla:");
        gets(TREE.label);
        ucitavanje(&TREE);
        return 0;
    }
    Please ignore printf's, there are on Croatian but are of no particular relevance, it only says to enter name of left/right child.

    So, what's the problem? Well, my output is right only for root. Here's how it looks:

    Code:
    Upisite oznaku korijena vaseg stabla: Chief Executive
    
    Upisite ime lijevog djeteta od Chief Executive: Pero
    
    Upisite ime lijevog djeteta od (L>: blablabla
                                   ^^^
    Upisite ime lijevog djeteta od (L>: yadayadayada
                                   ^^^
    Upisite ime lijevog djeteta od (L>: 0
                                   ^^^
    Upisite ime desnog djeteta od (L>: 0
                                  ^^^
    OTOH, when I use single characters and get them via getch or gets(&variable), it works perfectly. I'm a bit confused on that one, so any help would be appreciated.

    Also, I would like to "play" a bit with pre/post/inorder traversals, so I visited, as recommended in FAQ

    http://eternallyconfuzzled.com/tuts/..._tut_bst1.aspx

    Eh, now, point is - I must enter my data for binary tree *manually*, meaning - in the program itself.

    For example:

    Code:
    struct jsw_node *jsw_insert_r ( struct jsw_node *root, int data ) {
      if ( root == NULL )
        root = make_node ( data );
      else if ( root->data == data )
      return root;
      else {
        int dir = root->data < data;
        root->link[dir] = jsw_insert_r ( root->link[dir], data );
     }
    return root;
    }
    
    int jsw_insert ( struct jsw_tree *tree, int data )  {
      tree->root = jsw_insert_r ( tree->root, data );
      return 1;
    }
    makes a great code for me, but I simply fail to make any progress towards modifying it to operationally resemble my original code - namely to make it accept data for left/right child from my keyboard.

    I thought on building my program entirely based on that code, however, since upper code has somehow different "philosophy" than mine, I can't seem to find out how to insert data manually. Any help about that one?

    TIA!

  2. #2
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Code:
         cvor -> label[20] = temp[20];
    This sets element 21 of a 20 element array to element 21 of another array. Did you perhaps want to use strcpy(cvor->label, temp)?

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  3. #3
    Registered User bbanelli's Avatar
    Join Date
    Nov 2007
    Location
    Croatia, Zagreb
    Posts
    5
    Quote Originally Posted by matsp View Post
    Code:
         cvor -> label[20] = temp[20];
    This sets element 21 of a 20 element array to element 21 of another array. Did you perhaps want to use strcpy(cvor->label, temp)?
    Thx, it works perfectly. Me happy! Me also ashamed for such an error.

    BTW, out of curiosity and for academic purpose only, could this be done without strcpy. No matter what I attempt to do with cvor -> label[20] = temp[20]; (I don't want to copy/paste my attempts, I've bared enough shame already ), compiler reports incompatible types in assignment.

  4. #4
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Not really, you could of course use a for-loop [or other loop/inline code] to copy the elements of one array to the other - but it's pretty pointless to do that when strcpy() works. There is no "copy this array" in C - it has to be done by either multiple manual copies [in a loop for example] or my calling some function that does it for you. In the case of strings, strcpy() is efficient and does the right job.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  5. #5
    Registered User bbanelli's Avatar
    Join Date
    Nov 2007
    Location
    Croatia, Zagreb
    Posts
    5
    Thanks for explanation, matsp.

    Now, inorder "problem" has been solved.

    Code:
    void inorder (celltype *BTREE) {
          char temp = '0';
          if(BTREE -> leftchild != NULL) inorder(BTREE -> leftchild);
          if (strncmp (BTREE->label,&temp,1) != 0) //if statement is used because program uses '0' to indicate there is no left/right child
          printf ("&#37;s\t",BTREE->label);
          if(BTREE -> rightchild != NULL) inorder(BTREE -> rightchild);
    }
    Now, any ideas (it's 2PM at my place now, so perhaps I'm not fresh on ideas right now ) what condition or how, in general, could I print nodes in inorder traversal, but without children? Here's an example:

    Code:
                   A
                 /   \
                B     C
               /     /
              F      D
               \       \
                J       E
                       / \
                      G   H
    So, instead of printing F J B A D G E H C, program should print F B A D E C, i.e. inorder traversal without children.

    TIA, once again.

  6. #6
    Registered User bbanelli's Avatar
    Join Date
    Nov 2007
    Location
    Croatia, Zagreb
    Posts
    5
    Quote Originally Posted by bbanelli View Post
    Now, any ideas (it's 2PM at my place now, so perhaps I'm not fresh on ideas right now ) what condition or how, in general, could I print nodes in inorder traversal, but without children? Here's an example:

    Code:
                   A
                 /   \
                B     C
               /     /
              F      D
               \       \
                J       E
                       / \
                      G   H
    So, instead of printing F J B A D G E H C, program should print F B A D E C, i.e. inorder traversal without children.

    TIA, once again.
    Here's the solution:

    Code:
    void inorder (celltype *BTREE) {
        	int b = 0;
        	if(BTREE->leftchild)
        	{
        	    	if(BTREE->leftchild->label[0]!='0') 
        	    	{
        	    	    	b++;
        	    	    	inorder(BTREE -> leftchild);
        	    	}
        	}
        	if(BTREE->rightchild)
        	{
        	    	if(BTREE->rightchild->label[0]!='0') b+=2;
        	}
        	if(BTREE->label[0]!='0' &&  b>0) printf ("%s\t",BTREE->label);
        	if(b>1) inorder(BTREE -> rightchild);
    }
    Special thanks to Simargl from hr.comp.programiranje.c for providing the code.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 0
    Last Post: 11-04-2006, 11:07 AM
  2. RicBot
    By John_ in forum C++ Programming
    Replies: 8
    Last Post: 06-13-2006, 07:52 PM
  3. Calculator + LinkedList
    By maro009 in forum C++ Programming
    Replies: 20
    Last Post: 05-17-2005, 01:56 PM
  4. InOrder traversal : show tree
    By sballew in forum C Programming
    Replies: 4
    Last Post: 12-17-2001, 10:38 PM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 11:45 PM

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