九度OJ——1078二叉树遍历

AI那点小事

发布于 2020-04-18 19:55:05

3080

发布于 2020-04-18 19:55:05

题目描述：二叉树的前序、中序、后序遍历的定义：前序遍历：对任一子树，先访问跟，然后遍历其左子树，最后遍历其右子树；中序遍历：对任一子树，先遍历其左子树，然后访问根，最后遍历其右子树；后序遍历：对任一子树，先遍历其左子树，然后遍历其右子树，最后访问根。给定一棵二叉树的前序遍历和中序遍历，求其后序遍历（提示：给定前序遍历与中序遍历能够唯一确定后序遍历）。输入：两个字符串，其长度n均小于等于26。第一行为前序遍历，第二行为中序遍历。二叉树中的结点名称以大写字母表示：A，B，C….最多26个结点。输出：输入样例可能有多组，对于每组测试样例，输出一行，为后序遍历的字符串。样例输入： ABC BAC FDXEAG XDEFAG 样例输出： BCA XEDGAF

AC代码（在自己机器上跑通过，放到oj上布置为什么就是runtime error，求大佬解释）

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

class BinaryTree{
    private:
        char data;
        BinaryTree* lchild;
        BinaryTree* rchild;
    public:
        //初始化树结点函数 
        void Set(char ch){
            this->data = ch;
            this->lchild = this->rchild = NULL;
        }

        //创建树节点
        BinaryTree* create(char ch){
            BinaryTree* node = new BinaryTree;
            node->Set(ch);
        }

        BinaryTree* Pre_InOrder(char* pre,char* in ,int size){
            if(!pre || !in || size == 0){
                return NULL;
            }
            int root_index = 0;
            BinaryTree* root; 
            for(int i = 0 ; i < size ; i++){//寻找根结点的在中序序列的位置 
                if(in[i] == pre[0]){
                    root_index = i;
                    break;
                }
            }
            if(root_index == size){//先序序列与中序序列不符合 
                return NULL; 
            }
            root = root->create(in[root_index]); 
            if(root_index > 0){
                root->lchild = this->Pre_InOrder(pre+1,in,root_index);
            }
            if(size-root_index > 0){
                root->rchild = this->Pre_InOrder(pre+root_index+1,in+root_index+1,size-root_index-1);
            }
            return root;
        }

        //后序遍历
        void PostOrderTravelsal(BinaryTree* root){
            if(root == NULL){
                return;
            }
            this->PostOrderTravelsal(root->lchild);
            this->PostOrderTravelsal(root->rchild);
            cout<<root->data;
        } 
};

int main()
{
    char pre[1000],in[1000];
    int len;
    BinaryTree* root;

    while(scanf("%s%s",pre,in) != EOF){
        len = strlen(pre);
        root = root->Pre_InOrder(pre,in,len);
        root->PostOrderTravelsal(root);
        printf("\n");
    }
    return 0;
}