根据先序和中序输出节点序列构造二叉树并输出其后序遍历的程序

postorder_output.c

/*
 * postorder_output.c
 *
 * Generates a binary tree according to the two outputs of preorder and
 * inorder traversal and outputs a sequence of nodes by postorder traversal.
 *
 * Copyright (C) 2012-10-25 liutos <[email protected]>
 */
#include <stdlib.h>
#include <string.h>
#include <stdio.h>

struct treeNode;
typedef struct treeNode *TreeNode;
typedef TreeNode Tree;

struct treeNode {
    char value;
    Tree left, right;
};

TreeNode make_node(char value, Tree left, Tree right)
{
    TreeNode node = malloc(sizeof(struct treeNode));

    node->value = value;
    node->left = left;
    node->right = right;

    return node;
}

/* Find the position of a character in a string. */
int find_position(char c, char *string)
{
    int i;

    for (i = 0; string[i] != '\0'; ++i) {
        if (string[i] == c) {
            return i;
        }
    }

    return -1;
}

char *safe_strndup(char *s, int n)
{
    char *str = strndup(s, n + 1);

    str[n] = '\0';

    return str;
}

Tree make_tree_by_prein(char *preseq, char *inseq)
/* Assumes that the `preseq' and `inseq' is correct completely. */
{
    if (NULL == preseq)
        return NULL;
    if ('\0' == preseq[1])
        return make_node(preseq[0], NULL, NULL);
    else {
        char root_value = *preseq;
        int position = find_position(root_value, inseq);
        char *left_pre;         /* The output in preorder of left subtree. */
        char *left_in;          /* The output in inorder of left subtree. */
        char *right_pre;        /* The output in preorder of right subtree. */
        char *right_in;         /* The output in inorder of right subtree. */

        left_pre = safe_strndup(preseq + 1, position);
        left_in = safe_strndup(inseq, position);
        right_pre = strdup(preseq + position + 1);
        right_in = strdup(inseq + position + 1);

        return make_node(root_value,
                         make_tree_by_prein(left_pre, left_in),
                         make_tree_by_prein(right_pre, right_in));
    }
}

void print_tree(Tree tree)
{
    if (tree != NULL) {
        print_tree(tree->left);
        print_tree(tree->right);
        printf("%c", tree->value);
    }
}

int main(int argc, char *argv[])
{
    print_tree(make_tree_by_prein("abdfgceh", "dbgfaceh"));
    putchar('\n');

    return 0;
}