文章

52

粉丝

68

获赞

22

访问

11.6k

头像
二叉树(北京邮电大学) 题解:先序建树,中序递归锁定

#include <bits/stdc++.h>
using namespace std;

struct tnode{
    char val;
    tnode *left,*right;
    tnode():val(' '),left(nullptr),right(nullptr){}
    tnode(char c):val(c),left(nullptr),right(nullptr){}
};

tnode* buildTree(string preOrder,string inOrder){
    if(preOrder.empty()||inOrder.empty())return nullptr;
    tnode *root=new tnode();
    root->val=preOrder[0];
    int mid=inOrder.find(preOrder[0]);
    root->left=buildTree(preOrder.substr(1,mid),inOrder.substr(0,mid));
    root->right=buildTree(preOrder.substr(mid+1),inOrder.substr(mid+1));
    return root;
}

void postOrder(tnode *root){
    if(root==nullptr)return;
    postOrder(root->left);
    postOrder(root->right);
    cout<<root->val;
}

int main(){
    string a,b;
    while(cin>>a>>b){
        postOrder(buildTree(a,b));
        cout<<endl;
    }
}

 

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发