NOIP基础——树.pptVIP

数据结构—— 树 前面引入的有关树的一些基本术语对二叉树仍然适用。下图列出二叉树的五种基本形态： 给出一棵二叉树的中序遍历：DBGEACHFI 与后序遍历：DGEBHIFCA ，画出此二叉树。 04年分区联赛第三题 FBI树 【问题描述】 我们可以把由“0”和“1”组成的字符串分为三类：全“0”串称为B串，全“1”串称为I串，既含“0”又含“1”的串则称为F串。 FBI树是一种二叉树，它的结点类型也包括F结点，B结点和I结点三种。由一个长度为2N的“01”串S可以构造出一棵FBI树T，递归的构造方法如下： (1)T的根结点为R，其类型与串S的类型相同； (2)若串S的长度大于1，将串S从中间分开，分为等长的左右子串S1和S2；由左子串S1构造R的左子树T1，由右子串S2构造R的右子树T2。 现在给定一个长度为2N的“01”串，请用上述构造方法构造出一棵FBI树，并输出它的后序遍历序列。 【输入文件】 输入文件fbi.in的第一行是一个整数N（0=N=10），第二行是一个长度为2N的“01”串。 【输出文件】 输出文件fbi.out包括一行，这一行只包含一个字符串，即FBI树的后序遍历序列。 【样例输入】 3 【样例输出】 IBFBBBFIBFIIIFF 【数据规模】 对于40%的数据，N = 2； 对于全部的数据，N = 10。 解题目思路 解题方法：由于2的10次方=1024，若选择字符串就回超出，故选择用数组，1表示B 2表示I 3表示F。先将读入的0转换为1，将1转换为2。 以输入数据为第一层开始构造完整的FBI树，遵循此规则 1：两个数据结合，若其中有F(表示为3)，结合结果为F(表示为3) 2：两个数据结合，其中不存在F(表示为3) (1)两数据相同，结果为此数据 (2)两数据不同，结果为F(表示为3) 构造好FBI数后，以最上层开始进行后序遍历(先左子树再右子树最后根)。一边遍历一边输出 该题目的难度在于遍历 为了方便叙述，我们以下图为例解释三种遍历规则，我们在写遍历子过程前先定义树结构如下： type tree=record r,l,f:longint; d:char; end; var i,j,k,m,n:longint; s:string; a:array[1..100000]of tree; procedure jianshu(i:longint);//建树 begin if mn then exit; if a[i].d= then begin a[i].d:=s[m]; inc(m); end; if a[i].d=# then exit; if a[i].l=0 then begin inc(k); a[k].f:=i; a[i].l:=k; jianshu(k); end; if a[i].r=0 then begin inc(k); a[k].f:=i; a[i].r:=k; jianshu(k); end; end; ⑴前序遍历 前序遍历的规则如下： 若二叉树为空，则退出。否则 ⑴访问处理根结点； ⑵前序遍历左子树； ⑶前序遍历右子树； a b d e h i c f g procedure qianxu(i:longint); begin if a[i].d=# then exit; write(a[i].d); if a[i].l0 then qianxu(a[i].l); if a[i].r0 then qianxu(a[i].r); end; ⑵中序遍历 中序遍历的规则如下： 若二叉树为空，则退出；否则 ⑴中序遍历左子树； ⑵访问处理根结点； ⑶中序遍历右子树； 若中序遍历上图中的二叉树，可以得到如下的中序序列： d b h e i a f c g procedure zhongxu(i:longint); begin if a[i].d=# then exit; if a[i].l0 then zhongxu(a[i].l); write(a[i].d); if a[i].r0 then zhongxu(a[i].r); end; ⑶后序遍历 后序遍历的规则如下： 若二叉树为空，则退出；否则 ⑴后序遍历左子树； ⑵后序遍历右子树； ⑶访问处理根结点； 若后