首页 > 试题广场 > 二叉树遍历
[编程题]二叉树遍历
  • 热度指数:11901 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 64M,其他语言128M
  • 算法知识视频讲解
二叉树的前序、中序、后序遍历的定义: 前序遍历:对任一子树,先访问跟,然后遍历其左子树,最后遍历其右子树; 中序遍历:对任一子树,先遍历其左子树,然后访问根,最后遍历其右子树; 后序遍历:对任一子树,先遍历其左子树,然后遍历其右子树,最后访问根。 给定一棵二叉树的前序遍历和中序遍历,求其后序遍历(提示:给定前序遍历与中序遍历能够唯一确定后序遍历)。

输入描述:
两个字符串,其长度n均小于等于26。
第一行为前序遍历,第二行为中序遍历。
二叉树中的结点名称以大写字母表示:A,B,C....最多26个结点。


输出描述:
输入样例可能有多组,对于每组测试样例,
输出一行,为后序遍历的字符串。
示例1

输入

ABC
BAC
FDXEAG
XDEFAG

输出

BCA
XEDGAF
#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;
    }
}

发表于 2018-09-25 19:49:46 回复(12)
               根       左          右
前序        F  | D   X   E  | A   G
                    左       根    右
中序        X   D   E |  F |  A   G
                    左          右     根
后序                     |             | F
               递归          递归
#include<stdio.h>
#include<string.h>
char pre[26];
char in[26];
char post[26];
        /**三个low和high分别是pre,in和post的起止位置*/
void Post(int low1,int high1,int low2,int high2,int low,int high)
{
    if(low>high) return ;
    char c=pre[low1];
    post[high]=c;   /**把pre[]第一个字符赋给post[]最后一个位置*/
    int k=0;
    while(in[low2+k]!=c)    /**找到pre[]第一个字符在in[]中的位置*/
        k++;
    Post(low1+1,low1+k,low2,low2+k-1,low,low+k-1);
    Post(low1+k+1,high1,low2+k+1,high2,low+k,high-1);
    return ;
}

int main()
{
    while(scanf("%s",pre)!=EOF)
    {
        scanf(" %s",in);
        int len=strlen(pre);
        Post(0,len-1,0,len-1,0,len-1);
        printf("%s",post);
        printf("\n");
    }
    return 0;
}
编辑于 2017-03-05 15:43:10 回复(5)
#include <iostream>
#include <cstring>
using namespace std;



typedef struct BinaryTree
    {
    char data;
    BinaryTree* lchild;
    BinaryTree* rchild;
}BinaryTree;

void RebuildTree(BinaryTree* &Tree,char* pre,char* in,int len)
    {
    Tree = (BinaryTree*)malloc(sizeof(BinaryTree));
    if(Tree!=NULL)
        {
        if(len<=0)
            {//递归截止条件
            Tree = NULL;
            return ;
        }
        int index = 0;
        while(index<len&&*(pre)!=*(in+index))
            {//寻找当前的root结点(包含子树)
            index++;
        }
        Tree->data = *(pre);
        RebuildTree(Tree->lchild,pre+1,in,index);//去掉root结点
        RebuildTree(Tree->rchild,pre+1+index,in+1+index,len-(index+1));//去掉左边和根节点
    }
    return ;
}

void PostOrderTravese(BinaryTree* Tree)
    {//后序遍历输出
    if(Tree==NULL)
        return;
    PostOrderTravese(Tree->lchild);
    PostOrderTravese(Tree->rchild);
    printf("%c",Tree->data);
}


int main()
{
    char pre[101];
    char in[101];
    while(scanf("%s %s",pre,in)!=EOF)
        {
        BinaryTree* tree;
        int length = strlen(pre);
        RebuildTree(tree,pre,in,length);    
        PostOrderTravese(tree);
        cout<<endl;
    }
    return 0;
}

发表于 2016-08-18 16:59:36 回复(0)
//已知先序和中序就能够唯一确定二叉树,最后再后序遍历输出
//感觉递归十分精妙!
#include<iostream>
#include<cstdio>
#include<string>

using namespace std;

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

void PostOrder(TreeNode* root){
    if(root == NULL){
        return;
    }
    PostOrder(root->leftChild);
    PostOrder(root->rightChild);
    cout<<root->data;
    return;
}

TreeNode* Build(string str1,string str2){
    if(str1.size()==0){
        return NULL;
    }
    char c = str1[0];
    int position = str2.find(c);
    TreeNode* root = new TreeNode(c);
    root->leftChild = Build(str1.substr(1,position),str2.substr(0,position));
    root->rightChild = Build(str1.substr(position+1),str2.substr(position+1));
    return root;
}

int main(){
    string str1,str2;
    while(cin>>str1>>str2){
        PostOrder(Build(str1,str2));
        cout<<endl;
    }
    return 0;
}

发表于 2020-02-16 11:04:03 回复(0)
#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");
    }
}

发表于 2018-02-25 16:43:06 回复(0)

小手顶一下啊

package com.speical.first;

import java.util.Scanner;

/**
 * 前序中序构建二叉树
 * 
 * 后序遍历
 * 二分法的思想,很优雅的实现
 * @author Special
 * @time 2018/02/09 11:35:18
 */
public class Pro209 {
    static String preStr;
    static String inStr;
    static int index;
    static class Node{
        char value;
        Node left, right;

        public Node(char value) {
            this.value = value;
        }
    }

    public static Node buildBT(int low, int high) {
        Node node = null;
        if(low <= high) {
            char ch = preStr.charAt(index++);
            node = new Node(ch);
            int point = inStr.indexOf(ch);
            node.left = buildBT(low, point - 1);
            node.right = buildBT(point + 1, high);
        }
        return node;
    }

    public static void postOrder(Node node) {
        if(node != null) {
            postOrder(node.left);
            postOrder(node.right);
            System.out.print(node.value);
        }
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner input = new Scanner(System.in);
        while(input.hasNext()) {
            preStr = input.nextLine();
            inStr = input.nextLine();
            Node root = null;
            index = 0;
            root = buildBT(0, preStr.length() - 1);
            postOrder(root);
            System.out.println();
        }
    }

}
发表于 2018-02-09 12:02:24 回复(0)
优雅一些,直接输出
#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;
}

发表于 2017-09-15 20:26:02 回复(0)
//============================================================================
// Name        : 2017-05-22-08.cpp
// Author      : 
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

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

string s1,s2;

struct node{
	char value;
	node* left;
	node* right;
};

node* newNode(char _v){
	node* pnode = new node;
	pnode->value = _v;
	pnode->left=NULL;
	pnode->right=NULL;
	return pnode;
}

node* createTree(int l1,int r1,int l2,int r2,node* parent, bool isLeft){
	if(r1-l1<0 || r2-l2<0){
		return NULL;
	}
	if(parent==NULL){
		parent = newNode(s1[l1]);
		int ppos = s2.find(s1[l1]);
		createTree(l1+1,l1+ppos-l2,l2,ppos-1,parent,true);
		createTree(l1+ppos-l2+1,r1,ppos+1,r1-l1+l2,parent,false);
	}else{
		if(isLeft){
			parent->left = newNode(s1[l1]);
			parent = parent->left;
			int ppos = s2.find(s1[l1]);
			createTree(l1+1,l1+ppos-l2,l2,ppos-1,parent,true);
			createTree(l1+ppos-l2+1,r1,ppos+1,r1-l1+l2,parent,false);
		}else{
			parent->right = newNode(s1[l1]);
			parent = parent->right;
			int ppos = s2.find(s1[l1]);
			createTree(l1+1,l1+ppos-l2,l2,ppos-1,parent,true);
			createTree(l1+ppos-l2+1,r1,ppos+1,r1-l1+l2,parent,false);
		}
	}

	return parent;
}

void postorder(node* root){
	if(root == NULL){
		return;
	}
	postorder(root->left);
	postorder(root->right);
	cout<<root->value;
}

int main() {
	while(cin>>s1>>s2){
		node* root = createTree(0,s1.length()-1,0,s2.length()-1,NULL,1);
		postorder(root);
		cout<<endl;
	}
	return 0;
}


发表于 2017-05-22 21:48:12 回复(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;
}

编辑于 2020-03-13 00:32:03 回复(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;
	}

	
}

发表于 2020-03-06 17:19:38 回复(0)
按传统的结构体做的,分治+递归,每次取前序的第一位,在中序中找到它,并把中序以它为切割点分成两半
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;

struct TreeNode{
    char data;
    TreeNode* leftChild;
    TreeNode* rightChild;
};

int search(string str, char ch){
    for(int i=0; i<str.length();i++){
        if(ch==str[i])
            return i;
    }
    return -1;
}

//分治+递归,每次取前序的第一位,在中序中找到它,并把中序以它为切割点分成两半
TreeNode* Create(string PreO, string InO){
    if(PreO.length()==0)
        return NULL;
    TreeNode* root = new TreeNode;
    char ch =PreO[0];//取当前前序第一个ch
    root->data = ch;//赋值

    int pos = search(InO, ch);//在中序遍历中找到这个ch,并返回位置
    int leftNumber = pos;//有i个节点在它左边
    int rightNumber = InO.length()-pos -1;//有InO.length()-pos-1个节点在它右边
    string leftInO = InO.substr(0,leftNumber);//从InO[0]到InO[pos-1]
    string rightInO = InO.substr(pos+1);//InO[pos+1]到结尾
    string leftPreO = PreO.substr(1,leftNumber);
    string rightPreO = PreO.substr(pos+1);

    root->leftChild = Create(leftPreO, leftInO);
    root->rightChild = Create(rightPreO, rightInO);

    return root;
}

//后序遍历
void PostOrder(TreeNode* root){
    if(root==NULL)
        return ;
    PostOrder(root->leftChild);
    PostOrder(root->rightChild);
    cout<<root->data;
    return ;
}

int main(){
    string pre,in;
    while(cin>>pre){
        cin>>in;
        TreeNode* root = new TreeNode;
        root = Create(pre,in);
        PostOrder(root);
        cout<<endl;
    }
    return 0;
}


编辑于 2020-02-26 09:30:55 回复(0)
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define N 26
typedef struct bnode{
    char letter;
    struct bnode *leftc;
    struct bnode *rightc;
}bnode,*btree;
void buildtree(btree *,char *,char *);                                   
void leftstr(char *,char *,char *);
void rightstr(char *,char *,char *);
void printlast(btree);
int main(){
    char a[N],b[N];
    btree *T,t;
    t=NULL;
    T=&t;
    scanf("%s%s",a,b);
    buildtree(T,a,b);
    printlast(*T);
    free(*T);
    return 0;
}
void buildtree(btree *T,char *a,char *b){
    if(a[0]!='\0'){
        char lefta[N],righta[N];
        char leftb[N],rightb[N];
        *T=(btree)malloc(sizeof(bnode));
        (*T)->letter=a[0];
        (*T)->leftc=NULL;
        (*T)->rightc=NULL;
        strncpy(leftb,b,sequence(a[0],b));
        leftb[sequence(a[0],b)]='\0';
        strncpy(rightb,b+sequence(a[0],b)+1,strlen(b)-sequence(a[0],b)-1);
        rightb[strlen(b)-sequence(a[0],b)-1]='\0';
        leftstr(a,b,lefta);
        rightstr(a,b,righta);
        buildtree(&((*T)->leftc),lefta,leftb);
        buildtree(&((*T)->rightc),righta,rightb);
    }
}
int sequence(char a,char *b){
    int i=0;
    while(b[i]!=a){
        i++;
    }
    return i;
}
void leftstr(char *a,char *b,char *lefta){
    int s,j=1,i=0,k=0;
    s=sequence(a[0],b);
    while(k<s){
        while(a[j]!=b[i]){
            i++;
        }
        if(i<s){
            lefta[k]=a[j];
            k++;
        }
        j++;
        i=0;
    }
    lefta[k]='\0';
}
void rightstr(char *a,char *b,char *righta){
    int s,j=1,i,k=0;
    s=sequence(a[0],b);
    i=s+1;
    while(k<strlen(b)-s-1){
        while(a[j]!=b[i]){
            i++;
            if(i==strlen(b))break;
        }
        if(i!=strlen(b)){
            righta[k]=a[j];
            k++;
        }
        j++;
        i=s+1;
    }
    righta[k]='\0';
}
void printlast(btree T){
    if(T!=NULL){
        printlast(T->leftc);
        printlast(T->rightc);
        printf("%c",T->letter);
    }
}
发表于 2020-01-04 22:30:50 回复(1)
#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");     } }


发表于 2019-02-17 22:49:18 回复(0)
#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;
}

发表于 2019-01-20 09:04:40 回复(0)
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;
    }
}


编辑于 2019-01-13 21:47:14 回复(0)
fat头像 fat
#include<iostream>
#include<string.h>
using namespace std;

int Post(char *pre,char *in,char *post,int len)//前,中,后序和序列长度
{
    if (len < 0)
        return 0;
    int    index = 0;//用于指向中序遍历根节点的下标
    post[len]= *pre;
    while (*pre != in[index])//找中序遍历根节点
        index++;
    Post(pre+1, in, post, index-1); //将左子树作为递归中新的树,子树中前中后序长度一致,起点不同,用指针确定新的起点
    Post(pre+index+1, in + index + 1, post + index, len - index - 1); //将右子树作为递归中新的树,同上
    return 0;
}

int main()
{
    char pre[27],in[27],post[27];
    while (cin >>pre>>in)
    {
        Post(pre, in, post, strlen(pre)-1);
        post[strlen(pre)] = '\0';
        cout << post<<endl;
    }
}


发表于 2019-01-07 18:57:54 回复(0)
#include<iostream>
#include<string>

using namespace std;

class TreeNode{
public:
    char val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(char v){
        val = v;
        left = NULL;
        right = NULL;
    }
};

TreeNode* createTree(string s1,string s2){
    TreeNode *t = new TreeNode(s1[0]);
    int curr = s2.find(s1[0]);
    if (curr > 0)
    {
        t->left = (createTree(s1.substr(1,curr),s2.substr(0,curr)));
    }
    if (curr < s2.size() - 1)
    {
        t->right = (createTree(s1.substr(curr+1),s2.substr(curr+1)));
    }
    return t;
}
void postOrder(TreeNode *root){
    if (root){
        postOrder(root->left);
        postOrder(root->right);
        cout << root->val;
    }
}
int main(){
    string s1 = "";
    string s2 = "";
    while(cin >> s1 >> s2){
            TreeNode *root = createTree(s1,s2);
             postOrder(root);
    }
    

    return 0;

}

发表于 2018-05-30 14:21:18 回复(0)
#include <stdio.h>
#include <string.h>
struct Node{
    Node *lchild;
    Node *rchild;
    char c;
}Tree[500];
int u;
Node *create()
{
    Tree[u].rchild=Tree[u].lchild=NULL;
    return &Tree[u++];
}
void PostOrder(Node *r){
    if(r->lchild)
        PostOrder(r->lchild);
    if(r->rchild)
        PostOrder(r->rchild);
    printf("%c",r->c);
}
char str1[30],str2[30];
Node *build(int s1,int e1,int s2,int e2)
{
    Node *ret=create();
    ret->c=str1[s1];
    int rootidx;
     for(int i=s2;i<=e2;++i)
     {
         if(ret->c==str2[i]){
             rootidx=i;break;
         }
     }
     if(rootidx!=s2)
         ret->lchild=build(s1+1,s1+rootidx-s2,s2,rootidx-1);
    if(rootidx!=e2)
        ret->rchild=build(s1+rootidx-s2+1,e1,rootidx+1,e2);
    return ret;
}
int main()
{
    while(scanf("%s",str1)!=EOF){
        scanf("%s",str2);
        u=0;
        int l1=strlen(str1);
        int l2=strlen(str2);
        Node *T=build(0,l1-1,0,l2-1);
        PostOrder(T);
        printf("\n");
    }
    return 0;
}
运行时间:3ms
占用内存:384k
发表于 2018-01-14 23:46:30 回复(0)

#include<iostream>
#include<cstdio>
using namespace std;
struct Node{
char val;
Node*left=NULL;
Node*right=NULL;
};
string sa;
string sb;
void buildTree(Node *& r,int ai,int aj,int bi,int bj){  //ai ,aj, bi,bj 表示子树分别在两个字符串的左右位置
if(ai>aj||bi>bj){
return;     //终止条件
}
if(ai==aj&&bi==bj){   //相等时表明只有一个节点,可以直接就挂上去,然后return
r=new Node;
r->val=sa[ai];
r->left=r->right=NULL;
return;
}
else{
r=new Node;
r->val=sa[ai];
r->left=r->right=NULL;
int tmp=0;
for(int i=bi;i<=bj;i++){
if(sa[ai]== sb[i]){
tmp=i-bi;
break;
}
}
buildTree(r->left,ai+1,ai+1+tmp-1,bi,bi+tmp-1);  //这个地方要仔细了
buildTree(r->right,ai+1+tmp-1+1,aj,bi+tmp-1+2,bj);
}
}
void postTraverse(Node* &r){
if(r!=NULL){
postTraverse(r->left);
postTraverse(r->right);
cout<<r->val;
}
}
int main(){
while(cin>>sa>>sb){
int n=sa.length();
Node*root=NULL;
buildTree(root,0,n-1,0,n-1);
postTraverse(root);
cout<<endl;
}
}
发表于 2017-08-19 13:12:07 回复(0)
通过的代码总体思路是根据前、中序建立一个二叉树,之后使用递归输出二叉树的后序。
二叉树前序遍历是根左右、中序遍历是左根右、后序遍历是左右根。
生成二叉树时,使用递归生成,初始时传入的树根root是空树(NULL),还需要传入整棵树的前、中序遍历及其长度(因为程序中没有修改遍历结果,所以 要通过长度控制左、右子树的范围),create中的if是处理特殊情况,如果前、中序长度不等或者为空,是无法建树的,仅有一个节点时也就不用再递归 了,while是用于在中序中找到根节点,这样就能确定左、右子树的范围。
 
#include<stdio.h>
#include<string.h>
#include<malloc.h>
 
typedef struct TreeInfo{
    char data;
    struct TreeInfo *left;
    struct TreeInfo *right;
}Tree;
 
Tree *create(Tree *root , char *preOrder , int preLen, char *inOrder , int inLen){
    if(preLen != inLen || preLen < 1) return root;//前、中序长度不等或者为空
    if(root == NULL){
        root = (Tree *)malloc(sizeof(Tree));
        root->data = preOrder[0];
        root->left = root->right = NULL;
    }
    if(preLen == 1) return root;//前、中序仅有一个字符
    int i = 0;
    while(i < preLen){
        if(preOrder[0] == inOrder[i]) break;
        ++i;
    }
    root->left = create(root->left , preOrder + 1 , i , inOrder , i);
    root->right = create(root->right , preOrder + (1 + i) , preLen - 1  - i , inOrder + (i + 1) , inLen - i - 1);
    return root;
}
 
void displayPostOrder(Tree *root){
    if(root == NULL) return ;
    displayPostOrder(root->left);
    displayPostOrder(root->right);
    printf("%c" , root->data);
}
 
int main(){
    char preOrder[27] , inOrder[27];
    while(fscanf(stdin , "%s %s" , preOrder , inOrder) != EOF){
        Tree *root = create(NULL , preOrder , strlen(preOrder) , inOrder , strlen(inOrder));
        displayPostOrder(root);
        printf("\n");
    }
}

编辑于 2017-06-22 15:53:09 回复(0)