由先序和后序确定严格二叉树
若二叉树BT的每个结点，其左右子树均为空，或者其左右子树都不为空，这种二叉树称为“严格二叉树”。由严格二叉树的先序序列和后序序列可以唯一确定一棵二叉树。
思想：由题可知，严格二叉树没有单分支结点。先序的第一个结点为根结点。先序的第二个结点为根结的左子树的根结点。由后序遍历左右根可知，可以用先序的第二个结点为根结的左子树的根结点的这个结点将树划分为左右子树两个部分。左部分为根结点的左子树，右部分为根结点的右子树。
代码：
void creatBTree(BiTree &BT,ElemType *preDates,int prestart,int preend,ElemType *postDates,int poststart,int postend){
//preDates先序序列，prestart先序起始下标，preend终止下标
//postDates后序序列 ,poststart后序起始下标，postend终止下标
//非法输入时，结束操作
if(prestart>preend){
BT=NULL;
return;
}
BT = (BiTNode*)malloc(sizeof(BiTNode));//创建根结点
BT->data=preDates[preStart];//先序系列的第一个元素是根结点
if(prestart==preend){//叶节点
BT->lchild=NULL;
BT->rchild=NULL;
} else{
//处理非叶结点
int i;//辅助变量
//在后序系列中找到左子树根结点
for(i=p0ststart;i<=postend&&postDates[i]!=preDates[prestart+1];i++);
len=i-poststart+1;//左子树长度
//递归处理左子树
creatBTree(BT->lchild,preDates,prestart+1,prestart+len,postDates,poststart,i);
//递归处理右子树
creatBTree(BT->rchild,preDates,prestart+len+1,preend,postDates,i+1,postend-1);
}
}
原文地址：https://blog.csdn.net/m0_56332819/article/details/142697106
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！