文章

25

粉丝

364

获赞

8

访问

207.4k

头像
二叉树遍历(C)
P1401 华中科技大学/中国科学院2017机试题
发布于2021年1月29日 11:49
阅读数 8.0k

递归,模拟由中序序列和先序序列生成二叉树以及后序遍历二叉树

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

//后序遍历
//pre先序序列,mid后序序列
//start中序序列起始位置,end中序序列终止位置
//根结点在先序序列中的位置
void PostorderTraversal(char *pre, char *mid, int start, int end, int *p)
{
    char tmp;
    int m;

    if (pre[*p] != '\0' && start <= end)
    {
        tmp=pre[(*p)++];
        for (int i = start; i <= end; i++) //在中序遍历序列找到当前根的位置
        {
            if (mid[i] == tmp)
            {
                m = i;
                break;
            }
        }
        PostorderTraversal(pre,mid,start,m-1,p);//遍历左子树
        PostorderTraversal(pre,mid,m+1,end,p);//遍历左子树
        printf("%c",tmp);//访问根结点
    }
}

int main()
{
    char pre[27], mid[27];
    int len,p;

    while (scanf("%s\n%s", pre, mid) != EOF)
    {
        len=strlen(pre);
        p=0;
        PostorderTraversal(pre,mid,0,len-1,&p);
        printf("\n");
    }...
登录查看完整内容


登录后发布评论

暂无评论,来抢沙发