I'm trying to create a tree using C and print its tree traversals(preorder,inoreder,postorder) so i decided to start creating a tree first. My program accepts a characters in preorder but it doesn't print the data I entered. Could someone help me?

#include<stdio.h>
#define MAXNODES 26
void push();
void pop();
char TOP();
typedef struct node{
       char n;
       struct node*next;
       }NODE;
NODE *T[MAXNODES];
NODE *S;
void create(){
       NODE *p,*new,*q;
       int i,s,r;
       char m;
       clrscr();
       i=s=0;
       printf("Enter nodes in preorder;");
       m=getche();
       while(m!='\n'){
        if((m<48 || m>57) && (m<65 || m>90) && (m<97 || m>122))
          m=getche();
        else{
         while (T[s]!=NULL)
               s++;
         new=(NODE*)malloc(sizeof(NODE));
         if (new==NULL){
             printf("List is full!");
             getch();
             return;
             }
         r=0;
         do{
             p=T[r];
             q=p->next;
             r++;
             }while (r<MAXNODES && p!=NULL && p->n!=m);
         if (r==MAXNODES) {
            new->n=m;
            T[s]=new;
            new->next=NULL;
            }
         else
            free(new);

         if (i>=1){
            new=(NODE*)malloc(sizeof(NODE));
            if(new==NULL){
               printf("List is full!");
               getch();
               return;
               }
            new->n=m;
            p=q=T[s-i];
            while (p!=NULL){
             q=p;
             p=p->next;
            }
            q->next=new;
            new->next=NULL;
           }
           i++;
           m=getche();
       }
    }
}

 char leftmost_child(char m){
    NODE*p,*q;
    int i=0;
    for (i=0;i<MAXNODES;i++){
         p=q=T[i];
         p=p->next;
         if(p->n == m){
        q=p->next;
        if (q!=NULL)
            return (q->n);
        else
            return ('');
         }
       }
  }

char right_sibling(char m){
    NODE *p,*q;
    int i=0;
    for(i=0;i<MAXNODES;i++){
           p=q=T[i];
           p=p->next;
           if (p->n !=m && p->next!=NULL){
             q=p->next;
             while(q->n !=m && q!=NULL)
            q=q->next;
             if (q!=NULL){
            if (q->next !=NULL)
                return (q->n);
            else
                return ('');
             }
           }
     }
    }

 char root(){
       NODE*p,*q;
       int i, j;
       char m;
       for(i=MAXNODES-1;i>=0;i--){
        p=q=T[i];
        p=p->next;
        if (i!=0){
             if (T[i]!=NULL && p->next!=NULL){
             p=T[i];
             p=p->next;
             while (p->next !=NULL){
               m=p->n;
               q=T[j];
               q=q->next;
               j=0;
               while (j<i && q->n !=m)
                j++;
               if (j<i)
                   return (p->n);
            }
            }
           else{
             p=T[i];
             p=p->next;
             if(T[i]!=NULL && p->next!=NULL)
                  return(p->n);
             else
                  return('');
          }
        }
      }
     }
 void preorder(){
       char c;
       S=NULL;
       clrscr();
       printf("PREORDER: ");
       c=root();
       while(1){
      if (c!=''){
          printf("%c",c);
          push(c);
          c=leftmost_child(c);
      }
     else{
         if (S==NULL)
        return;
         c=right_sibling(TOP());
         pop();
         }
       }
   }

 void push(char o){
    NODE*new,*p;
    p=S;
    new=(NODE*)malloc(sizeof(NODE));
    if(new==NULL){
         printf("List is full!");
         getch();
         return;
         }
    new->n=o;
    if(S==NULL){
         S=new;
         new->next=NULL;
         }
    else if(S!=NULL){
         p=p->next;
         S=new;
         new->next=p;
         }
     }

 void pop(){
      NODE*p;
      p=S;
      if(S!=NULL){
        p=p->next;
        S=p->next;
        free(p);
        }
      }

char TOP(){
       NODE *t;
       t=S;
       if (S==NULL)
       return;
       else{
       t=t->next;
       return (t->n);
       }
}

void makenull(){
     int i=0;
     for(i=0;i<MAXNODES;i++)
     T[i]=NULL;
}

main(){
     char ans='Y';
     makenull();
     while ((ans=='Y') || (ans=='y')) {
         create();
         clrscr();
         printf("Enter another node?Y\N");
         scanf("%c",&ans);
         }
     if(T!=NULL)
         preorder();

     getch();
}

I'm not a tree hugger or any way expert in the use of trees. However, when I do venture into the forest I usually use a node with at least two, and often three node pointers.

struct node
{
    //non-node pointer member variable(s) here
 
   //node pointer member variables here
   node * rightChild;
   node * leftChild;
};

That's using C++ struct syntax, which you can modify to your own needs in C. A leaf is any node where both rightChild and leftChild are NULL. Hopefully you recognize that a tree with only 1 child pointer as a member variable is basically a list, though if you stayed in the tree analagy you might call it a branch or a twig instead.

I've seen both stacks and node pointers to parent nodes to assist with backtracking and thus traversing the tree. Using stacks decreases the size of each node, since there is one less pointer per node, which is helpful if the tree is large.

BTW, if malloc() returns NULL I believe that means that the computer doesn't have the memory to hold another new node, not that the tree is full.

Atually i'd like to say that u were trying to create a tree but as u declared the structure :

typedef struct node{
       char n;
       struct node*next;
       }NODE;

u'l actually end up creating a linear linked list that's because u are taking only one pointer in the definition...!!...it would be much easier if u try

typedef struct node{
       char n;
       struct node*right,*left;
       }NODE;

and then create a tree using RECURSION...!!
HOPE THIS HELPS U :)

Edited 5 Years Ago by ankitcuul: n/a

This article has been dead for over six months. Start a new discussion instead.