EXPRESSION TREE program

CodeProject

#include<stdio.h>

#include<stdlib.h>

#define MAX 255

struct tree_node

{

       struct tree_node *left,*right;

       char c;

};

typedef struct tree_node TNODE;
 

struct tree

{

       TNODE *root;

};

struct tree btree;

void in_order_print(TNODE *node,TNODE *root);

/*********************************** EXP TREE FUNCTIONS *********************************/

struct tlist

{

    struct tree_node *node;     //a subtree root address is stored here

    struct tlist *prev;         //previous element in stack

};

struct tstack

{

    struct tlist *top;          //stack top pointer

    struct tlist *start;        //stack base pointer

};

void tpush(struct tstack *top,struct tree_node *node);

void tpop(struct tstack *top, struct tree_node **node);

void tpush(struct tstack *stk, struct tree_node *node)

{

    struct tlist *temp;

    temp = (struct tlist*)malloc(1*sizeof(struct tlist));

    temp->node = node;

    temp->prev = stk->top;

    stk->top = temp;

}

void tpop(struct tstack *stk,struct tree_node **node)

{

    struct tlist *temp;

    *node = stk->top->node;

    temp = stk->top;

    stk->top = temp->prev;

    free(temp);

}

struct tree_node* buildExpTree(char *str);

//function to convert infix to postfix expression

char* to_postfix(char *str);

struct tree_node* buildExpTree(char *str)

{

    struct tstack stk;

    struct tree_node *temp=NULL;

    str = to_postfix(str);  //see post for postfix conversion in blog

    //create a stack

    stk.start = (struct tlist*)malloc(1*sizeof(struct tlist));

    stk.top = stk.start;

    stk.start->prev = NULL;

    stk.top->prev = NULL;

    while(*str != '\0')

    {

        //create a tree with its root as temp

        temp = (struct tree_node*)malloc(1*sizeof(struct tree_node));

        //if *str is operand create a tree as single node only

        if( isalnum(*str) )

        {

            temp->left = NULL;          //no left and right childs

            temp->right = NULL;

        }

        //if operator is encountered pop previous 2 trees and make them current tree's childs

        else

        {

            tpop(&stk,&(temp->right));

            tpop(&stk,&(temp->left));

        }

        //now push current trees address

        tpush(&stk,temp);

              temp->c = *str++;

    }

    return temp;

}

void in_order_print(TNODE *node,TNOE *root)

{

       if(node->left)

              in_order_print(node->left,root);

        

       if(node == root)

              printf("[%c] ",node->c);

       else

              printf("%c ",node->c);

       if(node->right)

              in_order_print(node->right,root);

}

int main()

{

       char str[MAX];

       printf("\nEnter Expression string: ");

       gets(str);

       btree.root=buildExpTree(str);
       printf("\nIN ORDER TREE: ");

       in_order_print(btree.root,btree.root);

       printf("\n\n");
       return 0;

}