Thread: 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!

Originally Posted by matsp

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.

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 ("%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.

Originally Posted by bbanelli

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.