王道数据结构课后代码题p150 15.设有一棵满二叉树(所有结点值均不同)，已知其先序序列为 pre，设计一个算法求其后序序列post。（c语言代码实现）

序列为 pre，设计一个算法求其后序序列post。（c语言代码实现）"/>

王道数据结构课后代码题p150 15.设有一棵满二叉树(所有结点值均不同)，已知其先序序列为 pre，设计一个算法求其后序序列post。（c语言代码实现）

 对一般二叉树，仅根据先序或后序序列，不能确定另一个遍历序列。但对满二叉树，任意一个结点的左、右子树均含有相等的结点数，同时，先序序列的第一个结点作为后序序列的最后个结点。

本题代码如下

void pretopost(char *pre,int l1,int h1,char post[],int l2,int h2)
{int half = 0;if (h1 >= l1){post[h2] = pre[l1];//后序最右端等于先序最左端half = (h1 - l1) / 2;pretopost(pre, l1 + 1, l1 + half, post, l2, l2 + half - 1);//转换左子树pretopost(pre, l1 + half + 1, h1, post, l2 + half, h2 - 1);//转换右子树}
}

完整测试代码

#include<stdio.h>
void pretopost(char *pre,int l1,int h1,char post[],int l2,int h2)
{int half = 0;if (h1 >= l1){post[h2] = pre[l1];//后序最右端等于先序最左端half = (h1 - l1) / 2;pretopost(pre, l1 + 1, l1 + half, post, l2, l2 + half - 1);//转换左子树pretopost(pre, l1 + half + 1, h1, post, l2 + half, h2 - 1);//转换右子树}
}
int main()
{char *pre = "ABDECFG";char post[10];pretopost(pre, 0, 6, post, 0, 6);printf("后序序列为：");for (int i = 0; i <= 6; i++)printf("%c", post[i]);return 0;
}