Description

In this assignment, you have to find the maximum value in a binary tree.

The idea of solving this problem is to find the maximum value in the left sub-tree, find maximum in the right sub-tree, compare it with the root data and select the one that gives the maximum value. Like this,

max{root, max of left subtree, max of right subtree}

main.c

#include <stdio.h> #include <stdlib.h> #include "function.h" int idxSearch(int arr[], int strt, int end, int value) { int i; for (i = strt; i <= end; i++) { if (arr[i] == value) return i; } } Node* newNode(int val) { Node *node = (Node *)malloc(sizeof(Node));; node->data = val; node->left = node->right = NULL; return (node); } Node* constructTree(int inorder[], int preorder[], int inorder_start, int inorder_end) { static int preorder_idx = 0; if(inorder_start > inorder_end) return NULL; Node *tree_node = newNode(preorder[preorder_idx++]); if(inorder_start == inorder_end) return tree_node; int inorder_idx = idxSearch(inorder, inorder_start, inorder_end, tree_node->data); tree_node->left = constructTree(inorder, preorder, inorder_start, inorder_idx-1); tree_node->right = constructTree(inorder, preorder, inorder_idx+1, inorder_end); return tree_node; } void destroyTree(Node *root) { if(root != NULL) { destroyTree(root->left); destroyTree(root->right); free(root); } } int main(void) { int *in, *pre, n, i; scanf("%d", &n);// get the size of tree in = (int *) malloc(n * sizeof(int));//allocate space for inorder pre = (int *) malloc(n * sizeof(int));// allocate space for preorder for(i=0; i<n; i++)// read in inorder scanf("%d", &in[i]); for(i=0; i<n; i++)// read in pre-order scanf("%d", &pre[i]); Node *root = constructTree(in, pre, 0, n-1);// construct trr printf("%d\n", maxValue(root));// print the max value of the tree destroyTree(root);// clean up free(in); free(pre); return 0; }

function.h

#include <stdlib.h> typedef struct treeNode { int data; struct treeNode *left; struct treeNode *right; } Node; int idxSearch(int arr[], int strt, int end, int value); Node* newNode(int val); Node* constructTree(int inorder[], int preorder[], int inorder_start, int inorder_end); void destroyTree(Node *root); int maxValue(Node *tree);

 

        All other function are provided. You only need to implement the function maxValue,

        int maxValue(Node *root)

        which gets the pointer of the tree root and returns the maximum value.

 

       You will be provided with main.c and function.h, and asked to implement function.c.

        For OJ submission:

        Step 1. Submit only your maxValue into the submission block. (Please choose C compiler)

        Step 2. Check the results and debug your program if necessary.

Input

The first line will have a number N with the number of tree node, second and third line are inorder and preorder of a tree respectively.

Notice that all the values are different.

Output

The maximum of a binary tree.

Sample Input  Download

Sample Output  Download

Partial Judge Code

10949.c

Partial Judge Header

10949.h

Tags

Add Tag

Discuss