最新消息:点击查看大S的省钱秘笈

求二叉树的后序遍历 C语言 数组实现

编程相关 Slyar 3451浏览 1评论

文章作者:姜南(Slyar) 文章来源:Slyar Home (www.slyar.com) 转载请注明,谢谢合作。

已知二叉树的前序遍历和后序遍历,求二叉树的后序遍历。算法很简单,由前序遍历的第一个元素可确定左、右子树的根节点,参照中序遍历又可进一步确定子树的左、右子树元素。如此递归地参照两个遍历序列,最终构造出二叉树。自己写了一段C语言的数组版,加了注释,应该很好理解。

由二叉树的前序遍历和中序遍历序列能唯一确定一棵二叉树。

前序遍历为:访问根节点、访问左子树、访问右子树;

中序遍历为:访问左子树、访问根节点、访问右子树。

后序遍历为:访问左子树、访问右子树、访问根节点。

#include 
#include 

char preord[100],inord[100];

void rebuild(int preleft,int preright,int inleft,int inright)
{
    int root,leftsize,rightsize;

    if(preleft<=preright&&inleft<=inright)
    {
        //在中序遍历中寻找根节点
        for(root=inleft;root<=inright;root++)
        {
            if(preord[preleft]==inord[root]) break;
        }

        //计算左右子树大小
        leftsize=root-inleft;
        rightsize=inright-root;

        //如果有左子树则递归重建左子树
        if(leftsize>0)
        {
            rebuild(preleft+1,preleft+leftsize,inleft,root-1);
        }

        //如果有右子树则递归重建右子树
        if(rightsize>0)
        {
            rebuild(preleft+leftsize+1,preright,root+1,inright);
        }

        //如果无子树则打印根节点
        printf("%c",inord[root]);
    }
}

int main()
{
    int length;
    scanf("%s%s",preord,inord);
    length=strlen(preord)-1;
    rebuild(0,length,0,length);
    return 0;
}

转载请注明:Slyar Home » 求二叉树的后序遍历 C语言 数组实现

发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

网友最新评论 (1)

  1. 顺序存储的二叉树左右子树交换如何写呢
    何伟8年前 (2012-12-24)回复