文章

5

粉丝

7

获赞

9

访问

1.1k

头像
二叉树(北京邮电大学) 题解:
P1561 北京邮电大学机试题
发布于2025年3月23日 16:47
阅读数 160

二刷后,思路更清晰

#include <iostream>

using namespace std;

typedef struct node
{
    char data;
    struct node *lchild,*rchild;
}*Tree;

void CreateTree(Tree &T,string pre,string in)
{
    //初始化根节点
    T=new node;
    //初始化左、右子树
    T->lchild=T->rchild=NULL;
    T->data=pre[0];

    //判断是否只有根节点一个节点,若是,则直接返回
    if(pre.size()==1)
    {
        return;
    }

    //找出根节点在中序遍历序列中的位置下标(用for可以,简单点用find函数
    int mid=in.find(pre[0]);

    //判断该树是否有左子树
    if(mid!=0)
    {
        //有左子树
        CreateTree(T->lchild,pre.substr(1,mid),in.substr(0,mid));
    }

    if(mid!=pre.size()-1)
    {
        //如果有右子树
        CreateTree(T->rchild,pre.substr(mid+1),in.substr(mid+1));
    }
}

void postOrder(Tree T)
{
    if(T!=NULL)
    {
        //如果树不为空
        postOrder(T->lchild);
        postOrder(T->rchild);
        cout<<T->data;
    }
}

int main()
{
    string pre,in;
    while(cin>>pre>>...
登录查看完整内容


登录后发布评论

暂无评论,来抢沙发