C语言解答

#include <stdio.h>
#include <string.h>
void build(char *pre,char *in,int len){
	if (len<=0)
	{
		return ;
	}
	int pos=strchr(in,*pre)-in;
	build(pre+1,in,pos);
	build(pre+pos+1,in+pos+1,len-pos-1);
	printf("%c",*pre);

}
int main(){
	char pre[1000],in[1000];
//	freopen("1.txt","r",stdin);
	while (scanf("%s %s",pre,in)!=EOF)
	{
		build(pre,in,strlen(pre));
		printf("\n");
	}
//	fclose(stdin);
	return 0;
}

C++解答

#include<cstdio>
#include<iostream>
#include<string>
using namespace std;

struct BT
{
	char data;
	BT *lchild,*rchild;
};

BT *build(string preorder,string inorder)
{
	BT *root;
	int p;
	if(!preorder.length())
		root=NULL;
	else
	{
		root=new BT;
		root->data=preorder[0];
		p=inorder.find(root->data);
		root->lchild=build(preorder.substr(1,p),inorder.substr(0,p));
		root->rchild=build(preorder.substr(1+p),inorder.substr(p+1));
	}
	return root;
}

void postorder(BT *root)
{
	if(root)
	{
		postorder(root->lchild);
		postorder(root->rchild);
		putchar(root->data);
	}
}

int main()
{
	string preorder,inorder;
	BT *root;
	while(cin>>preorder>>inorder)
	{
		root=build(preorder,inorder);
		postorder(root);
		printf("\n");
	}
	return 0;
}

Java解答

import java.util.Scanner;

public class Main {
	public static void main(String args[]) {
		Scanner jin = new Scanner(System.in);
		while (jin.hasNext()) {
			String pre = jin.next(), mid = jin.next();
			Node root = new Node(pre);
			root.build(pre, mid);
			root.post();
			System.out.println();
		}
	}
}

class Node {
	char entry;
	Node lson;
	Node rson;

	public Node(String pre) {
		entry = pre.charAt(0);
		lson = null;
		rson = null;
	}

	public void build(String pre, String mid) {
		if (pre.length() > 1) {
			int p = mid.indexOf(entry);
			String lmid = mid.substring(0, p);
			String rmid = mid.substring(p + 1);
			String lpre = pre.substring(1, 1 + lmid.length());
			String rpre = pre.substring(1 + lmid.length());
			if (lpre.length() > 0) {
				lson = new Node(lpre);
				lson.build(lpre, lmid);
			}
			if (rpre.length() > 0) {
				rson = new Node(rpre);
				rson.build(rpre, rmid);
			}
		}
	}

	public void post() {
		if (lson != null)
			lson.post();
		if (rson != null)
			rson.post();
		System.out.print(entry);
	}
}

Python解答

# -*- coding: utf-8 -*-
import sys

class BTree:
    '''
    Represent a no in a binary tree.
    '''
    def __init__(self, c='/0', l=None, r=None):
        '''
        Initializes the node's data
        '''
        self.e = c
        self.left = l
        self.right = r
        
def preorderTraverse(bt):
    '''
    返回前序遍历结果
    '''
    if bt:
        return '%s%s%s' % (bt.e, preorderTraverse(bt.left), preorderTraverse(bt.right))
    return ''
def inorderTraverse(bt):
    '''
    返回中序遍历结果
    '''
    if bt:
        return '%s%s%s' % (inorderTraverse(bt.left), bt.e, inorderTraverse(bt.right))
    return '';
def postorderTraverse(bt):
    '''
    返回后序遍历结果
    '''
    if bt:
        return '%s%s%s' % (postorderTraverse(bt.left), postorderTraverse(bt.right), bt.e)
    return ''
def printBTree(bt, depth):
    '''
    递归打印这棵二叉树，*号表示该节点为NULL
    '''
    '''
    if not bt:
        ch = '*'
    else:
        ch = bt.e
    '''
    #ch=(lambda x: (x and x.e) or '*')(bt)
    ch = bt.e if bt else '*'
    if(depth > 0):
        print '%s%s%s' % ((depth - 1) * '  ', '--', ch)
    else:
        print ch
    if not bt:
        return
    printBTree(bt.left, depth + 1)
    printBTree(bt.right, depth + 1)
def buildBTreeFromPreIn(preo, ino):
    '''
    根据前序和中序遍历结果重构这棵二叉树
    '''
    if(preo == '' or ino == ''):
        return None
    pos = ino.find(preo[0])
    if(pos < 0):
        return None        
    return BTree(preo[0], buildBTreeFromPreIn(preo[1:pos + 1], ino[0:pos]), buildBTreeFromPreIn(preo[pos + 1:], ino[pos + 1:]))
   
for line in sys.stdin:
      preo,ino = line.split()
      #print preo,ino
      bt = buildBTreeFromPreIn(preo, ino)
      print postorderTraverse(bt)