Question

enum {FALSE=0, TRUE};

#define MAXBUFF 1024
#define SMALLBUFF 10

/* The LinkNode type is used as an element of a linked list
** implementation of a stack of tree nodes.
*/

typedef struct link_t LinkNode;
typedef LinkNode *LinkNodePtr;

/* The TreeNode type is used as an element of a binary "parse" tree.
** Tree nodes are created while parsing the RPN expression and
** stored on a stack until it's time to place them.
*/

typedef struct tree_t TreeNode;
typedef TreeNode *TreeNodePtr;

/* The tree is a representation of an algebraic relationship. Here
is the parse tree for 3*(2+5). Or "2 5 + 3 *" in RPN.

+-----+
| |
+-----+ * +-------+
| | | |
| +-----+ |
| |
| |
v v
+--+--+ +--+--+
| | | |
| 3 | +-----+ + +-----+
| | | | | |
+-----+ | +-----+ |
| |
v v
+-+-+ +-+-+
| | | |
| 2 | | 5 |
| | | |
+---+ +---+

*/

struct link_t {
TreeNodePtr treeNode;
LinkNodePtr next;
};

struct tree_t {
char *value;
TreeNodePtr left;
TreeNodePtr right;
};

int list_len(LinkNodePtr list);
LinkNodePtr list_node_new(TreeNodePtr aNode);
void list_node_free(LinkNodePtr node, int freeAll);
void list_free(LinkNodePtr curr);
LinkNodePtr list_push_head(LinkNodePtr head, TreeNodePtr aNode);
TreeNodePtr list_pop_head(LinkNodePtr *head);
int get_operator(char *value, char **valid_operators);

TreeNodePtr tree_node_new(char *value);
void tree_node_free(TreeNodePtr aNode);
int tree_size(TreeNodePtr root);
void tree_free(TreeNodePtr root);
TreeNodePtr tree_add_node(TreeNodePtr op, TreeNodePtr left, TreeNodePtr right);
size_t tree_sprintf(TreeNodePtr root, char *buffer, size_t n);
TreeNodePtr parse_RPN(char *input, char **valid_operators);

typedef void (*visitfunc)(char *value, void *addr, void *parent_addr, void *obj);
void tree_visit(TreeNodePtr root, visitfunc visit, void *obj);

#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include "impl.h"

const char *LEFTPAREN = "(";
const char *RIGHTPAREN = ")";

int list_len(LinkNodePtr curr) {
/*
** Return the number of nodes in a linked list.
**
** Arguments: ListNodePtr curr (a pointer to a node in a list)
**
** Returns: The number of additional nodes in the list.
*/
  
return -1;
}

void list_print(LinkNodePtr head) {
/*
** Utility to help with debugging.
**
** print the list to stdout.
*/
  
char *bbuff = malloc(MAXBUFF);
  
if (head) {
printf("%lx: ", (unsigned long)head);
if (bbuff) {
strcpy(bbuff,"");
tree_sprintf(head->treeNode, bbuff, MAXBUFF);
printf("%s\n", bbuff);
free(bbuff);
list_print(head->next);
} else {
fprintf(stderr, "Ack no bbuff memory!\n");
}
}
}

void list_node_free(LinkNodePtr node, int freeAll) {
/*
** Free the memory owned by a ListNodePtr.
*/
  
}

void list_free(LinkNodePtr curr) {
/*
** free the entire list.
*/

}

LinkNodePtr list_node_new(TreeNodePtr aNode) {
/*
** Create a new listNode
**
** aNode is now owned by the list.
*/
  
return NULL;
}

LinkNodePtr list_push_head(LinkNodePtr head, TreeNodePtr aNode) {

/*
** push a new value onto the head of a list.
**
** Arguments:
**
** ListNodePtr head can be NULL.
**
** TreeNodePtr aNode is owned by the list after this call.
**
** Returns: new head pointer successful, NULL if not.
*/
  
return NULL;
}

TreeNodePtr list_pop_head(LinkNodePtr *head) {
/*
** Pop the "head" of a list. Deletes the
** old head node. The returned char * is now
** owned by the caller.
**
** Argument: Pointer to the head node pointer.
** This function modifies the head node
** so it needs a pointer to the pointer.
**
** Returns TreeNodePtr from the old head node.
** The TreeNodePtr is relinquised (not freed)
** by the list. Ownership is transferred
** to the caller.
*/
  
return NULL;
}

int get_operator(char * value, char * *valid_operators) {
/*
** Check to see if value is a valid operator.
**
** If it is, return the index in the valid_operators array.
**
** If it isn't, return -1.
*/

return -1; // not found
}

TreeNodePtr tree_node_new(char * value) {
/*
** Create a new tree Node. value
** is owned by caller. copy is made
*/
  
return NULL;
}

void tree_node_free(TreeNodePtr aNode) {
/*
** Free the memory of a single TreeNode
*/
  
}

int tree_size(TreeNodePtr root) {
/*
** get the total number of nodes in the parse tree structure.
**
*/
  
return -1;
}

void tree_free(TreeNodePtr root) {
/*
** free the entire tree data structure
*/

}

TreeNodePtr tree_add_node(TreeNodePtr op, TreeNodePtr left, TreeNodePtr right) {
/*
** attach left and right subtrees to a TreeNode.
*/
  
return NULL;
}

size_t tree_sprintf(TreeNodePtr root, char *buffer, size_t n) {
/*
** Recursively call this function to append each
** leaf and node to the accumulating string
** that represents the full tree.
*/
  
return 0;
}

void tree_visit(TreeNodePtr root, visitfunc visit, void *obj) {
/*
** given a 'visitfunc visit' and a pointer (void *obj)
** visit every node in the tree pointed to by root.
** at every node, call the function visit with four
** arguments:
**
** char *value: the value of the node
** TreeNodePtr: node (a pointer to the node itself, as a void *)
** TreeNodePtr parent_addr (a pointer to the node's parent, as a void *,
** pass a NULL pointer if it's the root node)
** void *obj: (the void * pointer passed as the last argument
** to this function).
*/

}

void tree_printf(TreeNodePtr root) {
/*
** Utility to help with debugging.
**
** print the tree to stdout.
*/

char big_buffer[MAXBUFF];
strcpy(big_buffer, "");
tree_sprintf(root, big_buffer, MAXBUFF);
printf("%s\n", big_buffer);
}

TreeNodePtr parse_RPN(char *input, char **valid_operators) {
/*
** Create a tree data structure that represents an algebraic
** representation of an given RPN expression: input.
**
** Inputs:
** char *input; A string of characters to be interpreted as RPN
** char **valid_operators; The characters that represent operators
**
** Returns:
** a TreeNodePtr that points to the root of the resulting tree.
*/

return NULL;
}

Answer 1

#include <iostream>

using namespace std;

#include <conio.h>

struct tree

{

    tree *l, *r;

    int data;

}*root = NULL, *p = NULL, *np = NULL, *q;

void create()

{

    int value,c = 0;   

    while (c < 7)

    {

        if (root == NULL)

        {

            root = new tree;

            cout<<"enter value of root node\n";

            cin>>root->data;

            root->r=NULL;

            root->l=NULL;

        }

        else

        {

            p = root;

            cout<<"enter value of node\n";

            cin>>value;

            while(true)

            {

                if (value < p->data)

                {

                    if (p->l == NULL)

                    {

                        p->l = new tree;

                        p = p->l;

                        p->data = value;

                        p->l = NULL;

                        p->r = NULL;

                        cout<<"value entered in left\n";

                        break;

                    }

                    else if (p->l != NULL)

                    {

                        p = p->l;

                    }

                }

                else if (value > p->data)

                {

                    if (p->r == NULL)

                    {

                        p->r = new tree;

                        p = p->r;

                        p->data = value;

                        p->l = NULL;

                        p->r = NULL;

                        cout<<"value entered in right\n";

                        break;

                    }

                    else if (p->r != NULL)

                    {

                        p = p->r;

                    }

                 }

             }

        }

        c++;

    }

}

void inorder(tree *p)

{

    if (p != NULL)

    {

        inorder(p->l);

        cout<<p->data<<endl;

        inorder(p->r);

    }

}

void preorder(tree *p)

{

    if (p != NULL)

    {

        cout<<p->data<<endl;

        preorder(p->l);

        preorder(p->r);

    }

}

void postorder(tree *p)

{

    if (p != NULL)

    {

        postorder(p->l);

        postorder(p->r);

        cout<<p->data<<endl;

    }

}

int main()

{

    create();

    cout<<"printing traversal in inorder\n";

    inorder(root);

    cout<<"printing traversal in preorder\n";

    preorder(root);

    cout<<"printing traversal in postorder\n";

    postorder(root);

    getch();

}