C语言解答

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct BTNode{
	char data;
	struct BTNode *left,*right;
}BTNode,*BTree;
void build(BTree *t,char *pre,char *in,int len){
	if (len<=0)
	{
		*t=NULL;
		return;
	}
	int pos=strchr(in,pre[0])-in;
	*t=(BTNode *)malloc(sizeof(BTNode));
	(*t)->data=*pre;
	build(&(*t)->left,pre+1,in,pos);
	build(&(*t)->right,pre+pos+1,in+pos+1,len-pos-1);
}
void postorder(BTree t){
	if (t)
	{
		postorder(t->left);
		postorder(t->right);
		printf("%c",t->data);
	}
}
void clean(BTree *t){
	if (*t)
	{
		clean(&(*t)->left);
		clean(&(*t)->right);
		free(*t);
	}
}
int main(){
	BTree root;
	char pre[30],in[30];
//	freopen("1.txt","r",stdin);
	while (scanf("%s %s",pre,in)!=EOF)
	{
		build(&root,pre,in,strlen(pre));
		postorder(root);
		clean(&root);
		printf("\n");
	}
//	fclose(stdin);
	return 0;
}

C++解答

#include <stdio.h>
#include <string.h>
void run(char a[],char b[])
{
	int i,n,j;
	char c[33],d[33];
	n=strlen(a)-1;
	if(n<=0)
	{
		printf("%s",a);
		return;
	}
	i=0;
	while(b[i]!=a[0])
		i++;
	for(j=0;j<i;j++)
	{
		c[j]=a[j+1];
		d[j]=b[j];
	}
	c[i]=0;
	d[i]=0;
	run(c,d);
	for(j=0;j<n-i;j++)
	{
		c[j]=a[j+i+1];
		d[j]=b[j+i+1];
	}
	c[n-i]=0;
	d[n-i]=0;
	run(c,d);
	printf("%c",a[0]);
}
int main()
{
	char a[33],b[33];
	scanf("%s",a);
	while(strcmp(a,"")!=0)
	{
		scanf("%s",b);
		run(a,b);
		printf("\n");
		strcpy(a,"");
		scanf("%s",a);
	}
	return 0;
}

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:]))

Alist = []
for line in sys.stdin:
      a = line.split()[0]
      Alist.append(a)
      if len(Alist) == 2:
         preo,ino = Alist[0],Alist[1]
         bt = buildBTreeFromPreIn(preo, ino)
         print postorderTraverse(bt)
         Alist=[]