如题 自用笔记 如有错误欢迎及时指正
设前序序列保存在DLR[]中，中序序列保存在LDR[]中，后序序列保存在LRD[]中
核心问题是递归时针对保存先序/后序序列数组DLR/LRD的划分，以及对中序序列数组LDR的划分
本质是把对应序列转化二叉树的手工过程转换成代码描述
只要理解手工过程并建立递归模型 该问题易实现
本问题解决方法的思路详解与递归模型可参照下面文章的解释 本质上是一致的 此处不再多赘述
已知满二叉树先序序列如何求后序序列_kollektor的博客-CSDN博客
前序+中序建立二叉树
设有一颗二叉树结点值各不相同，其先序序列与中序序列存放于两个数组DLR与LDR中，设计建立该二叉树链式存储的算法
思路：任一二叉树先序加中序可唯一确定二叉树
1.DLR找出根节点
2.LDR划分左右子树
3.回到1中，在2中划分好的左右子树中再次寻找根节点
//DLR[l1...h1]//LDR[l2...h2]void DLRandLDR(BiTree &T, DataType DLR[], int l1, int h1, DataType LDR[], int l2, int h2){//l1 h1为DLR下标范围 l2 h2同理T = (BiTNode *)malloc(sizeof(BiTNode));T->data = DLR[l1];//根节点数据域保存int leftLen, rightLen;//左右子树长度int i;//下面寻找LDR中的左右子树划分 用i保存for (i = l2; LDR[i]!=T->data;i++);leftLen = i - l2;rightLen = h2 - i;//求高度//开始递归if(leftLen!=0){ //处理左子树DLRandLDR(T->lchild,DLR, l1 + 1, l1 + leftLen, LDR, l2, l2 + leftLen - 1); //递归进入先序的左子部分 中序的左子部分}else{T->lchild = NULL; //无左时 T左孩子空}if(rightLen!=0){ //处理右子树 同上DLRandLDR(T->rchild,DLR, h1 - rightLen + 1, h1, LDR, h2 - rightLen + 1, h2);}else{T->rchild = NULL;}}
后序+中序建立二叉树
设有一颗二叉树结点值各不相同 其后序序列与中序序列存放于两个数组lrd与ldr中 设计建立该二叉树链式存储的算法
思路：任一二叉树后序加中序可唯一确定二叉树
1.LRD找出根节点
2.LDR划分左右子树
3.回到1中，在2中划分好的左右子树中再次寻找根节点
//LRD[l1...h1]//LDR[l2...h2]void LRDandLDR(BiTree &T, DataType LRD[], int l1, int h1, DataType LDR[], int l2, int h2){//l1 h1为lrd下标范围 l2 h2同理T = (BiTNode *)malloc(sizeof(BiTNode));T->data = LRD[h1];//尾结点是根int leftLen, rightLen;//左右子树长度int i;//下面寻找LDR中的左右子树划分 用i保存根节点在LDR序列中的位置for (i = l2; LDR[i] != T->data;i++);leftLen = i - l2;rightLen = h2 - i;//开始递归if(leftLen!=0){//左子树LRDandLDR(T->lchild, LRD, l1, l1 + leftLen-1, LDR, l2, l2 + leftLen - 1);}else{T->lchild = NULL;}if(rightLen!=0){ //右子树LRDandLDR(T->rchild, LRD, h1-rightLen, h1 - 1, LDR, h2 - rightLen + 1, h2);}else{T->rchild = NULL;}}
测试
#include<stdio.h>#include<string.h>#include<stdlib.h>#define MaxSize 10typedef int DataType;// 二叉树存储结构 二叉链式typedef struct BiTNode{DataType data; //数据域struct BiTNode *lchild;struct BiTNode *rchild;} BiTNode, *BiTree; //操作函数 负责visitinline void visit(BiTree p){printf("%d ", p->data);}//中序遍历递归void InOrderTraverse(BiTree T){if(T){InOrderTraverse(T->lchild);visit(T);InOrderTraverse(T->rchild);}}/*实现部分*/int main(){BiTree Tree;DataType DLR[7] = {1, 2, 4, 5, 3, 6, 7}; //本题用例DataType LDR[7] = {4, 2, 5, 1, 6, 3, 7};DataType LRD[7] = {4, 5, 2, 6, 7, 3, 1};//DLRandLDR(Tree,DLR, 0, 6, LDR, 0, 6);LRDandLDR(Tree,LRD,0,6,LDR,0,6);printf("二叉树T为：\n");InOrderTraverse(Tree);return 0;}
以上
