如题 自用笔记 如有错误欢迎及时指正

---

设前序序列保存在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 10
typedef int DataType;

// 二叉树存储结构 二叉链式
typedef struct BiTNode{
    DataType data;  //数据域
    struct BiTNode *lchild;
    struct BiTNode *rchild;
} BiTNode, *BiTree; 

//操作函数 负责visit
inline 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;
}

以上

2021.11.02

16：50