由前序序列与中序序列实现后序遍历

2024-06-19 14:43:18 浏览数 (2)

二叉树是一种特殊的树,二叉树只有两个分支,分别是该节点的左儿子和右儿子。 前序遍历:就是先遍历根节点,然后再访问左子树与右子树。遍历子树的时候同样也是先遍历根节点然后在遍历他的左子树与右子树。 中序遍历:先遍历左子树,在遍历根节点,最后遍历右子树。 后序遍历:先遍历左子树与右子树,在遍历根节点。 因为有这样的特点所以可以通过中序序列与后序或前列序列来确定一个二叉树。 一个二叉树的前序序列为abdecf 后序序列为dbeacf 由前序序列的特点我们知道前序序列第一个节点一定是该树的根节点,这样在中序序列中寻找与根节点相同的点,以根节点在中序序列的位置为界限,记为l1,左边就是左子树的中序遍历,右边就是右子树中序遍历,此时根节点在中序序列中的位置,就是前序序列中遍历完左子树加上根节点的最后一个位置,记为l2,此时,在先序序列中除去第一个节点(因为第一个节点是根节点,不属于子树),一直到l,包括l都是左子树,而且是左子树的前序序列。 使用上述两个序列来还原二叉树。 这时可以看出a是树的根节点,在bde与dbe分别是左子树的前序序列和中序序列,cf就是右子树的先序序列和中序序列,这样再以新生成的前序序列与中序序列再次进行找根节点并且分割左右子树的操作,这样直到两颗子树都只有一个节点时,此时说明这个节点是叶子节点也就是遍历完成。 这样一直进行下去,直到左子树和右子树都只剩下一个节点(这时子树就是叶子节点,将其输出后,这个方向的子树就全部遍历完全)。

代码语言:javascript复制
void BTree::builtTree(char *s1,char *s2,int len)//s1是前序序列,s2是后序序列,len是两个序列的长度,s1的长度一定等于s2的长度
{
    int l=0;
    if(len==0)//此时该子树只有一个元素即为叶子结点就可以停止现在的递归
    {
        return ;
    }
    for(;l<len;l  )//l恰好记录着根节点在中序遍历的位置,从而可以判断出左子树,右子树的长度
    {
        if(s2[l]==*s1)//如果恰好遍历子树是只有一个节点,那么在l=0时就会停止,l还是0此时就说明可以停止了
        {
            break;
        }
    }

    builtTree(s1 1,s2,l);//此次递归为左子树递归
    builtTree(s1 l 1,s2 l 1,len-l-1);//此次递归为右子树递归
       cout<<*s1;//因为我要实现的是后序遍历,所以输出s1在后面,中序的话在左子树与右子树的中间,前序在二者之前
}

0 人点赞