Attached is a C program traveselter.c. This is a solution to the problem of constructing a binary tree from the inorder and preorder listing of the nodes. It has the recursive function void list_inorder(struct Node * root) which lists the nodes of the tree in-order. Rewrite this function so that it is iterative. Hint: Implement a stack and you may assume it can hold a maximum of 100 items. You have to decide what will be in an item of the stack, and design a structure for it. I suggest that one member of an item is a pointer to a tree node. #include #include struct Node { int val; struct Node * left; struct Node * right; }; struct Node * create_node(char val); void destroy_node(struct Node * root); void destroy_tree(struct Node * root); void list_preorder(struct Node * root); struct Node * create_tree(char pre_order[], int pre_first, int pre_last, char in_order[], int in_first, int in_last); void list_inorder(struct Node * root) { if (root==NULL) return; list_inorder(root->left); printf(" %c",root->val); list_inorder(root->right); } void main() { char pre_order[12] = {'Y','F','H','Z','B','G','C','D','Q','A','K','M'}; char in_order[12] = {'Z','H','B','F','G','C','Y','D','K','A','M','Q'}; struct Node * root= create_tree(pre_order,0,11,in_order,0,11); printf("Pre-order: "); list_preorder(root); printf("\n"); printf("In-order: "); list_inorder(root); printf("\n"); destroy_tree(root); } struct Node * create_tree(char pre_order[], int pre_first, int pre_last, char in_order[], int in_first, int in_last) { if (pre_first>pre_last) return NULL; if (in_first>in_last) return NULL; struct Node * root = create_node(pre_order[pre_first]); int k; for (k=in_first; in_order[k]!=pre_order[pre_first]; k++); int left_size=k-in_first; int right_size=in_last-k; root->left=create_tree(pre_order,pre_first+1,pre_first+left_size,in_order,in_first,k-1); root->right=create_tree(pre_order,pre_first+left_size+1,pre_first+left_size+right_size,in_order,k+1,k+right_size); return root; } struct Node * create_node(char val) { struct Node * node = (struct Node *) malloc(sizeof(struct Node)); node->val = val; node->left = NULL; node->right = NULL; return node; } void destroy_node(struct Node * root) { free(root); } void destroy_tree(struct Node * root) { if (root!=NULL) { destroy_tree(root->left); destroy_tree(root->right); destroy_node(root); } } void list_preorder(struct Node * root) { if (root==NULL) return; printf(" %c",root->val); list_preorder(root->left); list_preorder(root->right); }
Attached is a C program traveselter.c. This is a solution to the problem of constructing a binary tree from the inorder and preorder listing
of the nodes. It has the recursive function
void list_inorder(struct Node * root)
which lists the nodes of the tree in-order. Rewrite this function so that it is iterative.
Hint: Implement a stack and you may assume it can hold a maximum of 100 items. You have to decide what will be in an item of the stack,
and design a structure for it. I suggest that one member of an item is a pointer to a tree node.
#include <stdlib.h>
#include <stdio.h>
struct Node {
int val;
struct Node * left;
struct Node * right;
};
struct Node * create_node(char val);
void destroy_node(struct Node * root);
void destroy_tree(struct Node * root);
void list_preorder(struct Node * root);
struct Node * create_tree(char pre_order[], int pre_first, int pre_last, char in_order[], int in_first, int in_last);
void list_inorder(struct Node * root)
{
if (root==NULL) return;
list_inorder(root->left);
printf(" %c",root->val);
list_inorder(root->right);
}
void main()
{
char pre_order[12] = {'Y','F','H','Z','B','G','C','D','Q','A','K','M'};
char in_order[12] = {'Z','H','B','F','G','C','Y','D','K','A','M','Q'};
struct Node * root= create_tree(pre_order,0,11,in_order,0,11);
printf("Pre-order: ");
list_preorder(root);
printf("\n");
printf("In-order: ");
list_inorder(root);
printf("\n");
destroy_tree(root);
}
struct Node * create_tree(char pre_order[], int pre_first, int pre_last, char in_order[], int in_first, int in_last)
{
if (pre_first>pre_last) return NULL;
if (in_first>in_last) return NULL;
struct Node * root = create_node(pre_order[pre_first]);
int k;
for (k=in_first; in_order[k]!=pre_order[pre_first]; k++);
int left_size=k-in_first;
int right_size=in_last-k;
root->left=create_tree(pre_order,pre_first+1,pre_first+left_size,in_order,in_first,k-1);
root->right=create_tree(pre_order,pre_first+left_size+1,pre_first+left_size+right_size,in_order,k+1,k+right_size);
return root;
}
struct Node * create_node(char val)
{
struct Node * node = (struct Node *) malloc(sizeof(struct Node));
node->val = val;
node->left = NULL;
node->right = NULL;
return node;
}
void destroy_node(struct Node * root)
{
free(root);
}
void destroy_tree(struct Node * root)
{
if (root!=NULL) {
destroy_tree(root->left);
destroy_tree(root->right);
destroy_node(root);
}
}
void list_preorder(struct Node * root)
{
if (root==NULL) return;
printf(" %c",root->val);
list_preorder(root->left);
list_preorder(root->right);
}
Trending now
This is a popular solution!
Step by step
Solved in 4 steps with 1 images
