Description

Given a binary tree, print the sum of nodes in the tree.

This problem will give you the inorder and preorder sequences to build a tree, and you have to write a function to count the sum of nodes in the tree. To solve this problem, you can write a recursive function to traverse the tree and sum up the data of nodes.

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 Sum(Node *root) and print the sum 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 printf("%d", Sum(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); int Sum(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 is the sum of nodes in the tree.

Sample Input  Download

Sample Output  Download

Partial Judge Code

10962.c

Partial Judge Header

10962.h

Tags

Discuss

Description

Please create a binary search tree, and support insert operation. Please ignore the repeat number and print out the tree with preorder, inorder and postorder sequence. (The root node is greater than the node in the left subtree and smaller than the node in the right subtree.)

Pre-order:

1. Check if the current node is empty / null.
2. Display the data part of the root (or current node).
3. Traverse the left subtree by recursively calling the pre-order function.
4. Traverse the right subtree by recursively calling the pre-order function

In-order:

1. Check if the current node is empty / null.
2. Traverse the left subtree by recursively calling the in-order function.
3. Display the data part of the root (or current node).
4. Traverse the right subtree by recursively calling the in-order function.

Post-order:

1. Check if the current node is empty / null.
2. Traverse the left subtree by recursively calling the post-order function.
3. Traverse the right subtree by recursively calling the post-order function.
4. Display the data part of the root (or current node).

Input

The input contains two lines. The first line is a integer n (n<=8000) , and the second line is a sequence S, where S contain n non-negative integer number. (The first number in the sequence S is the root.) 

Output

Please print out the tree with preorder, inorder and postorder.(total three line)

Each line has '\n' in the end.

Sample Input  Download

Sample Output  Download

Partial Judge Code

11349.c

Partial Judge Header

11349.h

Tags

Discuss