二叉树遍历

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
struct node{
    char c;
    node*left;
    node*right;
};
char pre[110];
char in[110];
node* find(int s1,int e1,int s2,int e2){
    int pos=-1;
    for(int i=s2;i<=e2;i++)
        if(pre[s1]==in[i]){
            pos=i;
            break;
        }
    node *root=(node*)calloc(1,sizeof(node));
    root->c=in[pos];
    if(pos==e2&&pos==s2)
        return    root;
    else{
        if(pos!=s2)
            root->left=find(s1+1,s1+pos-s2,s2,pos-1);
        if(pos!=e2)
            root->right=find(s1+pos-s2+1,e1,pos+1,e2);
        return root;
    }
}
void post(node*root){
    if(root==NULL)
        return;
    else{
        post(root->left);
        post(root->right);
        printf("%c",root->c);
    }
}
void freeT(node *root){
    if(root==NULL)
        return;
    else{
        freeT(root->left);
        freeT(root->right);
        free(root);
    }
}

int main(){
    while(scanf("%s",pre)!=EOF){
        scanf("%s",in);
        node *t=NULL;
        int pre_l=strlen(pre),in_l=strlen(in);
        t=find(0,pre_l-1,0,in_l-1);
        post(t);
        t->left=t->right=NULL;
        freeT(t);
        printf("\n");
    }
}

import java.util.Scanner;
public class Main{
    /*
    思路：递归
    一颗树的左子树的后序遍历+右子树的后序遍历+该树根节点的值为该树的后序遍历序列
    */
    private static int count = 0;//记录当前选择的是前序遍历序列中的第几个节点
    public static void main(String[] args){
        try(Scanner in = new Scanner(System.in)){
            String s1 = in.nextLine(),s2 = in.nextLine();
            char[] a = s1.toCharArray(),b = s2.toCharArray();
            System.out.println(helper(a,b,0,a.length));
        }
    }
    //以a[count]将位于[s,e)的b分成两半，即找到以a[count]为根节点的左右子树，再对其进行递归
    public static String helper(char[] a,char[] b,int s,int e){
        if(s >= e) return "";
        char c = a[count++];
        int i = s;
        while(i < e){
            if(b[i] == c) break;
            i++;
        }
        String l = helper(a,b,s,i),r = helper(a,b,i + 1,e),res = l + r + c;
        return res;
    }
}

#include<iostream>
using namespace std;

void postTra(char* pre,char* ord,int ordEnd){
    int i;
    if(*pre){
        i = 0;
        while(ord[i] && ord[i++] != *pre);
        --i;
        if(i){
            postTra(pre + 1,ord,i - 1);
        }
        if(i < ordEnd){
            postTra(pre + i + 1,ord + i + 1,ordEnd - i - 1);
        }
        cout << *pre;
    }
}

int main(void){
    char pre[27],ord[27];
    int i;
    while(cin >> pre){
        cin >> ord;
        i = 0;
        while(pre[i++]);
        postTra(pre,ord,i - 1);
        cout << endl;
    }
    return 0;
}

#include<iostream>
#include<cstring>
using namespace std;
//递归有点意思
typedef struct BNode
{
    char value;
    BNode *lchild,*rchild;
    BNode(int v):value(v),lchild(NULL),rchild(NULL){}
}BTree;

BTree * create(string s1,string s2)
{
    if(s1.size() == 0)
        return NULL;
    char temp = s1[0];
    int pos = s2.find(temp);
    BNode * root = new BNode(temp);
    root->lchild = create(s1.substr(1,pos), s2.substr(0,pos));
    root->rchild = create(s1.substr(pos + 1), s2.substr(pos + 1));
    
    return root;
}

void postOrder(BTree * root)//后序遍历
{
    if(!root)
        return;
    postOrder(root->lchild);
    postOrder(root->rchild);
    cout << root->value;
}

int main(void)
{
    string s1,s2;
    
    while(cin >> s1 >> s2)
    {
        BNode * root = create(s1, s2);
        postOrder(root);
        cout << endl;
    }
    return 0;
}

#include <stdio.h>
#include <string.h>
char pre[27];
char in[27];
char post[27];
void createpost(int preleft,int preright,int inleft,int inright,int postright) {
    if(preleft<=preright) {
        int father=inleft;
        while(in[father]!=pre[preleft])
            father++;
        post[postright]=in[father];
        createpost(preleft+1,preleft+father-inleft,inleft,father-1,postright-inright+father-1);
        createpost(preleft+father-inleft+1,preright,father+1,inright,postright-1);
    }
}
int main() {
    while(scanf("%s%s",pre,in)!=EOF) {
        int len=strlen(pre);
        createpost(0,len-1,0,len-1,len-1);
        post[len]='\0';
        printf("%s\n",post);
    }
    return 0;
}

小白 自己瞎写
#include<iostream>
(720)#include<algorithm>
#include<string>
using namespace std;

struct BiTree
{

	char data;
	BiTree *left;
	BiTree *Right;

	BiTree(int n) : data(n), left(NULL), Right(NULL) {}
};
void Build(BiTree *(&first),string x,string y,int a,int b,int c,int d)
{
	first = new BiTree(x[a]);
	if (a != b)
	{
		int loca=y.find(x[a]);
		int lengl = loca - c;
		int lengr = d - loca;
		if (loca > c)    //左树
		{
			Build(first->left, x, y, a + 1, a + lengl, c, loca - 1);
		}
		if (loca < d)
		{
			Build(first->Right, x, y, b - lengr + 1, b, loca + 1, d);
		}

	}

}
void ReOrder(BiTree *p)       //后序列
{
	if (p == NULL)  return;
	ReOrder(p->left);
	ReOrder(p->Right);
	cout << p->data;
}
int main()                        
{
	
	string a;
	string b;
	while (cin >> a>>b)
	{
		BiTree *first = NULL;
		Build(first, a, b, 0, a.size() - 1, 0, b.size() - 1);
		ReOrder(first);
		cout<< endl;
	}

	
}

	#include<stdio.h>
#include<stdlib.h>
#include<string.h>



	typedef struct BiTNode{
    char data;
    struct BiTNode *lchild;
    struct BiTNode *rchild;
}BiTNode,*BiTree;



	void BuildTreeFromOrder(char *a,char *b,int length){
    int index;
    if(length==0)
        return;
    for(index=0;a[0]!=b[index];index++);
    BiTNode *t=(BiTNode *)malloc(sizeof(BiTNode));
    t->data=a[0];
    BuildTreeFromOrder(a+1,b,index);
    BuildTreeFromOrder(a+index+1,b+index+1,length-index-1);
    printf("%c",t->data);
    free(t);
    return;
}



	int main(){
    char a[26],b[26];
    BiTree T;
    while(scanf("%s%s",a,b)!=EOF){
        BuildTreeFromOrder(a,b,strlen(a));
        printf("\n");
    }
}

#include<cstdio>
#include<string.h>
struct node
{
    char data;
    node *lchild;
    node *rchild;
};
char pre[30];
char in[30];

void postOrder(node *L)
{
    if(L==NULL) return;
    else{
        postOrder(L->lchild);
        postOrder(L->rchild);
        printf("%c",L->data);
    }
}
node *create(int preL,int preR,int inL,int inR){
    if(preL>preR){
        return NULL;
    }
    node *now=new node;
    now->data=pre[preL];
    int k;
    for(k=inL;k<=inR;k++){
        if(pre[preL]==in[k]){
            break;
        }
    }
    int numLeft=k-inL;
    now->lchild=create(preL+1,preL+numLeft,inL,k-1);
    now->rchild=create(preL+numLeft+1,preR,k+1,inR);
    return now;
}
int main()
{
    while(scanf("%s %s",pre,in)!=EOF){
            int m=strlen(pre);
            int n=strlen(in);
            node *root=create(0,m-1,0,n-1);
            postOrder(root);
            printf("\n");
    }
    return 0;
}

#include <iostream>
#include <string>

struct node
{
	char data;
	node *leftChild;
	node *rightChild;
	node(char c): data(c), leftChild(NULL), rightChild(NULL) {}
};

void create(node *&T, std::string &preStr, std::string &midStr,
			int preIndex, int midPreIndex, int midLastIndex)
{	
	T = new node(preStr[preIndex]);
	int index;
	for (int i = midPreIndex; i <= midLastIndex; i++)
	{
		if (midStr[i] == preStr[preIndex])
		{
			index = i;
			break;
		}
	}
	if (index != midPreIndex)
	{
		create(T->leftChild, preStr, midStr, preIndex + 1,
			midPreIndex, index - 1);
	}
	if (index != midLastIndex)
	{
		create(T->rightChild, preStr, midStr, preIndex + (index - midPreIndex) + 1,
			index + 1, midLastIndex);
	}
}

void postOrder(node *T)
{
	if (T != NULL)
	{
		postOrder(T->leftChild);
		postOrder(T->rightChild);
		std::cout << T->data;
	}
	return;
}

int main()
{
	std::string preStr;
	std::string midStr;
	while (std::cin >> preStr)
	{
		std::cin >> midStr;
		node *T = NULL;
		create(T, preStr, midStr, 0, 0, preStr.length() - 1);
		postOrder(T);
		std::cout << std::endl;
	}
	return 0;
}

#include <stdio.h>
#include <string.h>
void PreInCreateBT(char pre[],int pre_s,int pre_e, char in[],int in_s,int in_e){
	int key;
	if(in_s > in_e)
		return;
	if(in_s == in_e){
		printf("%c",in[in_s]);
		return;
	}
	for(int j=in_s;j<=in_e;j++){
		if(in[j] == pre[pre_s]){
			key = j;
			break;
		}
	}
	PreInCreateBT(pre,pre_s+1,pre_s+key-in_s, in,in_s,key-1);
	PreInCreateBT(pre,pre_s+key-in_s+1,pre_e, in,key+1,in_e);
	printf("%c",in[key]);
}
int main(){
	char pre[100];
	char in [100];
	while(scanf("%s %s",pre,in)!=EOF){
		PreInCreateBT(pre,0,strlen(pre)-1,in,0,strlen(in)-1);
		printf("\n");
	}
	return 0;
} 

#include<iostream>
#include<string>
#include<algorithm>

using namespace std;
struct tree{
    char c;
    tree * lc;
    tree * rc;
};

tree * create(string a,string b){   //分别为前序，中序
    tree * node=(tree *)malloc(sizeof(tree));
    node->c=a[0];
    if(a.length()==1||b.length()==1){      //长度等于1，到达终结点
        node->lc=node->rc=NULL;
    }
    else{       //长度大于1，继续递归
        int loc=b.find(a[0],0); //找到中序的树根节点位置
        if(loc==0){     //根节点在中序第一位，说明无左孩子，右孩子继续递归
            node->lc=NULL;
            node->rc=create(string(a,1,a.length()-1),string(b,1,b.length()-1));
        }else if(loc==b.length()-1){    //根节点在最后一位，说明无右孩子，左孩子递归
            node->rc=NULL;
            node->lc=create(string(a,1,a.length()-1),string(b,0,b.length()-1));
        }else{
            node->lc=create(string(a,1,loc),string(b,0,loc));//左孩子递归
            node->rc=create(string(a,loc+1,a.length()-1-loc),string(b,loc+1,b.length()-1-loc));//右孩子递归
        }
    }
    return node;
}

//void NLR(tree * a){ //输出前序序列
//    cout<<a->c;
//    if(a->lc!=NULL)
//        NLR(a->lc);
//    if(a->rc!=NULL)
//        NLR(a->rc);
//}
//void LNR(tree * a){ //输出中序序列
//    if(a->lc!=NULL)
//        LNR(a->lc);
//    cout<<a->c;
//    if(a->rc!=NULL)
//        LNR(a->rc);
//}
void LRN(tree * a){ //输出后序序列
    if(a->lc!=NULL)
        LRN(a->lc);
    if(a->rc!=NULL)
        LRN(a->rc);
    cout<<a->c;
}

int main(){
    string nlr,lnr;
    cin>>nlr;
    cin>>lnr;
    tree * head=create(nlr,lnr);
//    NLR(head);
//    cout<<endl;
//    LNR(head);
//    cout<<endl;
    LRN(head);
    return 0;

}

	

#include<iostream>
#include<algorithm>
using namespace std;
void Post(string str1,string str2)
{
    if(str1.length()==0)    return;
    int root=str2.find(str1[0]);
    Post(str1.substr(1,root),str2.substr(0,root));
    Post(str1.substr(root+1),str2.substr(root+1));
    cout<<str1[0];
}
int main()
{
    string str1,str2;
    while(cin>>str1>>str2)
    {
        Post(str1,str2);
        cout<<endl;
    }
}