中序序列+层序序列构造二叉树

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

其他关于二叉树遍历序列建立的问题

https://blog.csdn.net/weixin_46127065/article/details/121102001

算法描述

在层序序列中&＃xff0c;从左到右每一个结点&＃xff0c;或是当前结点某个子树的根结点&＃xff0c;或是叶子节点

        1.按层序序列遍历 第一个结点不空  在中序序列中划分左右子树

        2.当中序序列左子树不空 层序序列第二个结点为二叉树左子树的根

       3. 当中序序列左子树为空 层序序列第二个结点为二叉树右子树的根

对其他结点左右子树的检查同理易得

算法实现

设层序序列保存在LEVEL数组中&＃xff0c;中序序列保存在LDR中&＃xff0c;对应下标l1h1和l2h2。

BiTree Create(DataType LEVEL[], int l1, int h1, DataType LDR[], int l2, int h2){if (l2 > h2){return NULL;}else{BiTree T &＃61; (BiTNode *)malloc(sizeof(BiTNode));int mark &＃61; 0; //标识器int i, j;//分别指向LEVEL和LDR中数组的元素//寻找根&＃xff0c;LEVEL中第一个与LDR中元素匹配的即为根结点for (i &＃61; l1; i <&＃61; h1; &＃43;&＃43;i){for (j &＃61; l2; j <&＃61; h2; &＃43;&＃43;j){if (LEVEL[i] &＃61;&＃61; LDR[j]){mark &＃61; 1;break;}}if (mark &＃61;&＃61; 1){break;}}T->data &＃61; LEVEL[i]; //根节点数据域T->lchild &＃61; Create(LEVEL, l1 &＃43; 1, h1, LDR, l2, j - 1);T->rchild &＃61; Create(LEVEL, l1 &＃43; 1, h1, LDR, j &＃43; 1, h2);return T;}
}

测试

#include
#include
#include
#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 T1;/* DataType DLR[7] &＃61; {1, 2, 4, 5, 3, 6, 7};DataType LRD[7] &＃61; {4, 5, 2, 6, 7, 3, 1}; */DataType LDR[7] &＃61; {4, 2, 5, 1, 6, 3, 7};DataType LEVEL[7] &＃61; {1, 2, 3, 4, 5, 6, 7};T1&＃61;Create(LEVEL, LDR, 0, 6, 0, 6);printf("二叉树T1为&＃xff1a;\n");InOrderTraverse(T1);return 0;
}