《第9周树和二叉树（下）第3讲-二叉树的构造.pdf》由会员分享，可在线阅读，更多相关《第9周树和二叉树（下）第3讲-二叉树的构造.pdf（16页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、同一同一棵棵二叉树二叉树（假设每个节点值唯一假设每个节点值唯一）具有具有唯一唯一先序序列先序序列、中中 序序列和后序序列序序列和后序序列。 但但不同的二叉树可能不同的二叉树可能具有相同的先序序列具有相同的先序序列、中中序序序列或后序序列或后序序序 列列。 回顾回顾 A B C A BC 先序序列先序序列均为均为ABC 例如例如 以下命题以下命题成立否？成立否？ 定理定理7.1：任何任何n（n0）个不同节点的二又树个不同节点的二又树，都可由它的中序序都可由它的中序序 列和先序序列唯一地确定列和先序序列唯一地确定。 先序序列：先序序列：a0a1 akak+1 an-1 左子树先序序左子树先序序 列
2、，有列，有k个节点个节点 右子树先序序列，右子树先序序列， 有有n- -k- -1个节点个节点 中序序列：中序序列：b0b1bk-1bkbk+1 bn-1 左子树中序序左子树中序序 列，有列，有k个节点个节点 右子树中序序列，右子树中序序列， 有有n- -k- -1个节点个节点 通过根节点通过根节点a0在中序序列中找到在中序序列中找到bk a0 先序：先序：a1 ak 中序：中序： b0bk-1 左 子 树 左 子 树 先序：先序：ak+1 an-1 中序：中序： bk+1 bn-1 右 子 树 右 子 树 例如，已知先序序列为例如，已知先序序列为ABDGCEF，中序序列为，中序序列为DGBA
3、ECF，则构，则构 造二叉树的过程如下所示。造二叉树的过程如下所示。 二叉树构造完毕二叉树构造完毕 由先序和中序序列构造二叉树示例由先序和中序序列构造二叉树示例的演示的演示 先序先序:ABDGCEF 中序中序:DGBAECF A 先序先序:BDG 中序中序:DGB B 先序先序:CEF 中序中序:ECF C 先序先序:E 中序中序:E E 先序先序:F 中序中序:F F 先序先序:DG 中序中序:DG D 先序先序:G 中序中序:GG BTNode *CreateBT1(char *pre，char *in，int n) BTNode *s; char *p; int k; if (ndata
4、=*pre; for (p=in;plchild=CreateBT1(pre+1，in，k);/构造左子树构造左子树 s-rchild=CreateBT1(pre+k+1，p+1，n-k-1); /构造右子树构造右子树 return s; 先 序 遍 历 的 思 路 先 序 遍 历 的 思 路 先序先序pre：a0a1 ak-1akak+1 an-2 an-1 中序中序in： b0b1 bk-1bkbk+1bn-1 p pre+1pre+k+1 p+1in 左子树：左子树： 先序序列为先序序列为pre+1开始的开始的k个字符个字符 中序序列为中序序列为in开始的开始的k个字符个字符 右子树：右
5、子树： 先序序列为先序序列为pre+k+1开始的开始的n- -k- -1个字符个字符 中序序列为中序序列为p+1开始的开始的n- -k- -1个字符个字符 定理定理7.2：任何任何n（n0）个不同节点的二又树，都可由它的）个不同节点的二又树，都可由它的 中序序列和后序序列唯一地确定。中序序列和后序序列唯一地确定。 后序后序序列：序列：a0a1 ak-1ak an-2 an-1 左子树后序左子树后序序序 列，有列，有k个节点个节点 右子右子树后序序列树后序序列， 有有n- -k- -1个节点个节点 中序序列：中序序列：b0b1bk-1bkbk+1 bn-1 左子树中序序左子树中序序 列，有列，有
6、k个节点个节点 右子树中序序列，右子树中序序列， 有有n- -k- -1个节点个节点 通过根节点通过根节点an-1在在中序序列中找到中序序列中找到bk an-1 后序：后序：a0 ak-1 中序：中序： b0bk-1 左 子 树 左 子 树 后序：后序：ak an-2 中序：中序： bk+1 bn-1 右 子 树 右 子 树 例如，已知中序序列例如，已知中序序列为为DGBAECF，后序序列为，后序序列为GDBEFCA。对应。对应 的构造二叉树的过程如下所示。的构造二叉树的过程如下所示。 二叉树构造完毕二叉树构造完毕 由后序和中序序列构造二叉树示例由后序和中序序列构造二叉树示例的演示的演示 后序
7、后序: GDBEFCA 中序中序: DGBAECF A BC EFD G 后序后序: GDB 中序中序: DGB 后序后序: EFC 中序中序: ECF 后序后序: GD 中序中序: DG 后序后序: G 中序中序: G 后序后序: E 中序中序: E 后序后序: F 中序中序: F BTNode *CreateBT2(char *post,char *in,int n) BTNode *b; char r,*p; int k; if (ndata=r; for (p=in;plchild=CreateBT2(post,in,k);/递归构造左子树递归构造左子树 b-rchild=Create
8、BT2(post+k,p+1,n-k-1); /递归构造右子树递归构造右子树 return b; 先 序 遍 历 的 思 路 先 序 遍 历 的 思 路 后序后序post：a0a1 ak-1akak+1 an-2 an-1 中序中序in：b0b1 bk-1bkbk+1bn-1 p postpost+k p+1in 左子树：左子树： 后序序列为后序序列为post开始的开始的k个字符个字符 中序序列为中序序列为in开始的开始的k个字符个字符 右子树：右子树： 后序序列为后序序列为post+k开始的开始的n- -k- -1个字符个字符 中序序列为中序序列为p+1开始的开始的n- -k- -1个字符个
9、字符 【例例7- -11】设计一个算法将二叉树的顺序存储结构转换成二设计一个算法将二叉树的顺序存储结构转换成二 叉链存储结构。叉链存储结构。 解：解：设二叉树的顺序存储结构为设二叉树的顺序存储结构为a，由，由f(a,1)返回创建的二叉链返回创建的二叉链 存储结构的根存储结构的根节点节点指针指针b。 f(a,i) = NULL当当i大于大于MaxSize f(a,i) = NULL当当i对应的节点为空对应的节点为空 f(a,i) = b（创建（创建根根节点节点*b，其，其data值为值为ai）;其他其他情况情况 b-lchild=f(a,2*i); b-rchild=f(a,2*i+1)） b
10、12 a 递归模型：递归模型： 对应的递归算法如下：对应的递归算法如下： 先 序 遍 历 的 思 路 先 序 遍 历 的 思 路 【例例7- -12】设计设计一个算法将一个算法将二叉树二叉树的二叉链转换成顺序存储结构。的二叉链转换成顺序存储结构。 解：解：f(b,a,i)：由二叉链：由二叉链b创建创建ai为根节点的顺序存储结构为根节点的顺序存储结构a。 f(b,a,i) 不做任何事情不做任何事情当当b=NULL f(b,a,i) ai=b-data（创建创建根根节点）节点）;其他其他情况情况 f(b-lchild,a,2*i); f(b-rchild,a,2*i+1)） 递归模型：递归模型： b # 12 a# MaxSize- -1 初始调用：初始调用：f(b,a,1) 调用前调用前a的所有元素为的所有元素为# void *trans2(BTNode *b,SqBTree a，int i) if (b!=NULL) ai=b-data;/创建根节点创建根节点 trans2(b-lchild,a,2*i);/递归创建左子树递归创建左子树 trans2(b-rchild,a,2*i+1);/递归创建右子树递归创建右子树 对应的递归算法如下：对应的递归算法如下： 先 序 遍 历 的 思 路 先 序 遍 历 的 思 路 本讲完本讲完