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

11360.c

Partial Judge Header

11360.h

Tags

Add Tag

Discuss