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

Discuss

Description

Given a binary tree, print the inorder and postorder of the tree.

There are three common ways to traverse a binary tree recursively: inorder, preorder, and postorder. Each way contains three steps:

1. Visit the root (V)
2. Traverse the left subtree recursively (L)
3. Traverse the right subtree recursively (R)

The difference of the three ways is the order of steps, inorder is LVR, preorder is VLR, and postorder is LRV. For example, the three traversal sequences of the tree below are as follows:

This problem will give you the inorder and preorder sequences to build a tree, and you have to write two recursive functions to print the inorder and postorder of the tree.

You will be provided with main.c and function.h. main.c contains the implementation of functions which build a tree by the inorder and preorder, and function.h contains the definition of tree node. You only need to implement inorder(Node *root) and postorder(Node *root) in function.c.

For OJ submission:

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

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

 

main.c

#include <stdio.h> #include <stdlib.h> #include "function.h" 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 inorder(root); printf("\n"); postorder(root); destroyTree(root);// clean up free(in); free(pre); return 0; } 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); } }

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); void inorder(Node *root); void postorder(Node *root);

Input

The input contains three lines. The first line is the number of nodes in the tree. The second line is the inorder and the third line is the preorder of the tree.

Output

The output contains two sequences of integers. The first sequence is the inorder and the second sequence is the postorder of the tree.

Notice that there is a space after every integer.

Sample Input  Download

Sample Output  Download

Partial Judge Code

10950.c

Partial Judge Header

10950.h

Tags

Discuss

Description

Give a prefix Boolean expression, which only has at most 4 variables ‘A’, ‘B’, ‘C’, and ‘D’, and 2 operators, AND ‘&’ and OR ‘|’, print its truth table.

 

For example, if input is "|&AC|AB", then result will be

A B C D output

0 0 0 0 0
0 0 0 1 0
0 0 1 0 0
0 0 1 1 0
0 1 0 0 1
0 1 0 1 1
0 1 1 0 1
0 1 1 1 1
1 0 0 0 1
1 0 0 1 1
1 0 1 0 1
1 0 1 1 1
1 1 0 0 1
1 1 0 1 1
1 1 1 0 1
1 1 1 1 1

Input

The input contains a sequences of prefix expression. It only has at most 4 variables ‘A’, ‘B’, ‘C’, and ‘D’, and 2 operators, AND ‘&’ and OR ‘|’. The length of prefix expression is shorter than 30.

Output

It has 5 variables 'A', 'B', 'C', 'D', and output, each variable is separated by a space.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Give a prefix expression, which only has 2 operators, ‘+’ and ‘-’,and positive integers. Print the result.

Input

The input contains a sequences of prefix expression. It contains operators, ‘+’ and ‘-’,and positive integers separated by a space. Expression is ended by 0. (0 is not the element.)

Output

The output is the result of the expression. (Without a newline symbol)

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

This is a partial judge problem (Judge Language :  C)

Please download the partial judge code and header.

Then, implement 2 functions : buildTree() and showPostorder()

You have to build the binary tree according to its inorder and preorder.

Next , print out the postorder of the binary tree!

 

 

 

Submit format:

#include <stdio.h>

#include <stdlib.h>

#include "function.h"

Node* buildTree(int* inorder, int* preorder, int inorder_start, int inorder_end){

        /*YOUR CODE HERE*/

}

void showPostorder(Node* root){
      /*YOUR CODE HERE*/

}

Input

There are 3 lines for inputs.

The first line contains an integer N , which indicates the number of nodes of the binary tree.

The second line is the inorder traversal of the binary tree

The third line is the preorder traversal of the binary tree

※Note that there are not duplicated integers in the binary tree

Output

Print out the postorder traversal of the binary tree.

Note that :

1.There is an whitespace between each integer. 

2.There is an whitespace after the last integer.

3.Threre is no need to add "\n" at last 

 

Sample Input  Download

Sample Output  Download

Partial Judge Code

11361.c

Partial Judge Header

11361.h

Tags

Discuss