Assignment 8 : Solution
The program
#include <stdio.h>
#include <string.h>
#define MAX_SIZE 100
typedef struct _node {
char label;
struct _node *L;
struct _node *R;
} node;
node *gentree ( char *inlist , char *prelist )
{
node *head;
char *inp, *prep, ch;
if ((strlen(inlist)==0)||(strlen(prelist)==0)) return(NULL);
head = (node *)malloc(sizeof(node));
head->label = prelist[0];
inp = strchr(inlist,prelist[0]);
if (inp == NULL) {
free(head);
fprintf(stderr, "Malformed expression(s)...\n");
return(NULL);
}
*inp = '\0';
prelist++;
prep = prelist + strlen(inlist);
ch = *prep;
*prep = '\0';
head->L = gentree(inlist,prelist);
*prep = ch;
inp++;
head->R = gentree(inp,prep);
return(head);
}
void printtree ( node *root )
{
if (root == NULL) return;
printf("Node : %c, ",root->label);
printf("Left child : ");
if (root->L == NULL) printf("NULL, ");
else printf(" %c, ",root->L->label);
printf("Right child : ");
if (root->R == NULL) printf("NULL.\n");
else printf(" %c.\n",root->R->label);
printtree(root->L);
printtree(root->R);
}
int main ()
{
char inlist[MAX_SIZE], prelist[MAX_SIZE];
node *root;
printf("Inorder listing : "); scanf("%s",inlist);
printf("Preorder listing : "); scanf("%s",prelist);
root = gentree(inlist,prelist);
printtree(root);
}
Output
Inorder listing : GDHBAECF
Preorder listing : ABDGHCEF
Node : A, Left child : B, Right child : C.
Node : B, Left child : D, Right child : NULL.
Node : D, Left child : G, Right child : H.
Node : G, Left child : NULL, Right child : NULL.
Node : H, Left child : NULL, Right child : NULL.
Node : C, Left child : E, Right child : F.
Node : E, Left child : NULL, Right child : NULL.
Node : F, Left child : NULL, Right child : NULL.
Inorder listing : abcdefghijkl
Preorder listing : abcdefghijkl
Node : a, Left child : NULL, Right child : b.
Node : b, Left child : NULL, Right child : c.
Node : c, Left child : NULL, Right child : d.
Node : d, Left child : NULL, Right child : e.
Node : e, Left child : NULL, Right child : f.
Node : f, Left child : NULL, Right child : g.
Node : g, Left child : NULL, Right child : h.
Node : h, Left child : NULL, Right child : i.
Node : i, Left child : NULL, Right child : j.
Node : j, Left child : NULL, Right child : k.
Node : k, Left child : NULL, Right child : l.
Node : l, Left child : NULL, Right child : NULL.
Inorder listing : abcdefghijkl
Preorder listing : lkjihgfedcba
Node : l, Left child : k, Right child : NULL.
Node : k, Left child : j, Right child : NULL.
Node : j, Left child : i, Right child : NULL.
Node : i, Left child : h, Right child : NULL.
Node : h, Left child : g, Right child : NULL.
Node : g, Left child : f, Right child : NULL.
Node : f, Left child : e, Right child : NULL.
Node : e, Left child : d, Right child : NULL.
Node : d, Left child : c, Right child : NULL.
Node : c, Left child : b, Right child : NULL.
Node : b, Left child : a, Right child : NULL.
Node : a, Left child : NULL, Right child : NULL.
Inorder listing : abcdefghijkl
Preorder listing : badcfehgjilk
Node : b, Left child : a, Right child : d.
Node : a, Left child : NULL, Right child : NULL.
Node : d, Left child : c, Right child : f.
Node : c, Left child : NULL, Right child : NULL.
Node : f, Left child : e, Right child : h.
Node : e, Left child : NULL, Right child : NULL.
Node : h, Left child : g, Right child : j.
Node : g, Left child : NULL, Right child : NULL.
Node : j, Left child : i, Right child : l.
Node : i, Left child : NULL, Right child : NULL.
Node : l, Left child : k, Right child : NULL.
Node : k, Left child : NULL, Right child : NULL.
Inorder listing : cbafedihglkj
Preorder listing : abcdefghijkl
Node : a, Left child : b, Right child : d.
Node : b, Left child : c, Right child : NULL.
Node : c, Left child : NULL, Right child : NULL.
Node : d, Left child : e, Right child : g.
Node : e, Left child : f, Right child : NULL.
Node : f, Left child : NULL, Right child : NULL.
Node : g, Left child : h, Right child : j.
Node : h, Left child : i, Right child : NULL.
Node : i, Left child : NULL, Right child : NULL.
Node : j, Left child : k, Right child : NULL.
Node : k, Left child : l, Right child : NULL.
Node : l, Left child : NULL, Right child : NULL.
Inorder listing : abcdefghijkl
Preorder listing : bcdefghijkla
Malformed expression(s)...
Malformed expression(s)...
Malformed expression(s)...
Malformed expression(s)...
Malformed expression(s)...
Malformed expression(s)...
Node : b, Left child : NULL, Right child : d.
Node : d, Left child : NULL, Right child : f.
Node : f, Left child : NULL, Right child : h.
Node : h, Left child : NULL, Right child : j.
Node : j, Left child : NULL, Right child : l.
Node : l, Left child : NULL, Right child : NULL.
Inorder listing : bcdefghijkla
Preorder listing : abcdefghijkl
Node : a, Left child : b, Right child : NULL.
Node : b, Left child : NULL, Right child : c.
Node : c, Left child : NULL, Right child : d.
Node : d, Left child : NULL, Right child : e.
Node : e, Left child : NULL, Right child : f.
Node : f, Left child : NULL, Right child : g.
Node : g, Left child : NULL, Right child : h.
Node : h, Left child : NULL, Right child : i.
Node : i, Left child : NULL, Right child : j.
Node : j, Left child : NULL, Right child : k.
Node : k, Left child : NULL, Right child : l.
Node : l, Left child : NULL, Right child : NULL.
Inorder listing : hdibjekalfmcngo
Preorder listing : abdhiejkcflmgno
Node : a, Left child : b, Right child : c.
Node : b, Left child : d, Right child : e.
Node : d, Left child : h, Right child : i.
Node : h, Left child : NULL, Right child : NULL.
Node : i, Left child : NULL, Right child : NULL.
Node : e, Left child : j, Right child : k.
Node : j, Left child : NULL, Right child : NULL.
Node : k, Left child : NULL, Right child : NULL.
Node : c, Left child : f, Right child : g.
Node : f, Left child : l, Right child : m.
Node : l, Left child : NULL, Right child : NULL.
Node : m, Left child : NULL, Right child : NULL.
Node : g, Left child : n, Right child : o.
Node : n, Left child : NULL, Right child : NULL.
Node : o, Left child : NULL, Right child : NULL.
Inorder listing : ABCDEFGHIJKLMN
Preorder listing : HGFEDCBAIJKLMN
Node : H, Left child : G, Right child : I.
Node : G, Left child : F, Right child : NULL.
Node : F, Left child : E, Right child : NULL.
Node : E, Left child : D, Right child : NULL.
Node : D, Left child : C, Right child : NULL.
Node : C, Left child : B, Right child : NULL.
Node : B, Left child : A, Right child : NULL.
Node : A, Left child : NULL, Right child : NULL.
Node : I, Left child : NULL, Right child : J.
Node : J, Left child : NULL, Right child : K.
Node : K, Left child : NULL, Right child : L.
Node : L, Left child : NULL, Right child : M.
Node : M, Left child : NULL, Right child : N.
Node : N, Left child : NULL, Right child : NULL.
Inorder listing : ABCDEFGHIJKLMN
Preorder listing : GABCDEFNMLKJIH
Node : G, Left child : A, Right child : N.
Node : A, Left child : NULL, Right child : B.
Node : B, Left child : NULL, Right child : C.
Node : C, Left child : NULL, Right child : D.
Node : D, Left child : NULL, Right child : E.
Node : E, Left child : NULL, Right child : F.
Node : F, Left child : NULL, Right child : NULL.
Node : N, Left child : M, Right child : NULL.
Node : M, Left child : L, Right child : NULL.
Node : L, Left child : K, Right child : NULL.
Node : K, Left child : J, Right child : NULL.
Node : J, Left child : I, Right child : NULL.
Node : I, Left child : H, Right child : NULL.
Node : H, Left child : NULL, Right child : NULL.