高中信息竞赛数据结构-树的基础知识

树及其应用高中信息竞赛数据结构—树的基础知识共78页，您现在浏览的是第1页!栈、队列属于线性结构。在这种结构中,不管其存储方式(顺序和链式)如何,数据元素的逻辑位置之间呈线性关系,即每一个数据元素通常只有一个前驱(除个元素外)和一个后继(除最后一个元素外)。但也有很多问题数据元素间的逻辑关系不能用线性结构明确、方便地描述出来。一般来说，至少存在一个结点（数据元素）有多于一个前驱或后继的数据结构称为非线性结构。具有非线性结构特征的数据结构有两种

⑴树⑵图高中信息竞赛数据结构—树的基础知识共78页，您现在浏览的是第2页!节:树高中信息竞赛数据结构—树的基础知识共78页，您现在浏览的是第3页!高中信息竞赛数据结构—树的基础知识共78页，您现在浏览的是第4页!3、有关度的定义

⑴.结点的度：一个结点的子树数目称为该结点的度（区分图中结点的度）。图中，结点i度为3，结点t的度为2，结点b的度为1。显然，所有树叶的度为0。

⑵.树的度：所有结点中最大的度称为该树的度(宽度）。图中树的度为3。高中信息竞赛数据结构—树的基础知识共78页，您现在浏览的是第5页!5、森林所谓森林，是指若干棵互不相交的树的集合。如图去掉根结点A，其原来的三棵子树Tb，Tc，Td的集合{Tb，Tc，Td}就为森林，这三棵子树的具体形态如图（c）。高中信息竞赛数据结构—树的基础知识共78页，您现在浏览的是第6页!二、树的表示方法和存储结构1、树的表示方法树的表示方法一般有两种：

⑴自然界的树形表示法：用结点和边表示树，例如上图采用的就是自然界的树形表示法。树形表示法一般用于分析问题。优点:直观,形象;缺点:保存困难.高中信息竞赛数据结构—树的基础知识共78页，您现在浏览的是第7页!2、树的存储结构树的存储结构一般有两种⑴.静态的记录数组。所有结点存储在一个数组中,数组元素为记录类型,包括数据域和长度为n(n为树的度)的数组,分别存储该结点的每一个儿子的下标#definen树的度；#definemax结点数的上限；structtreetype{intdata;//数据域intch[n]；//指向各儿子的下标}treetypetree[max]；//树数组高中信息竞赛数据结构—树的基础知识共78页，您现在浏览的是第8页!DataParentinttree[maxn][2];//树的存储2.父亲表示法(重点掌握)

这种方法是定义一个数组，每个数组元素为一个记录，除了存放一个结点的数据信息外，还存放该结点编号．其结点的结构定义如下：#definem10；树的结点数structnode{intdata;数据域intparent;父结点}高中信息竞赛数据结构—树的基础知识共78页，您现在浏览的是第9页!树的遍历在应用树结构解决问题时，往往要求按照某种次序获得树中全部结点的信息，这种操作叫作树的遍历。遍历的方法有多种，常用的有：高中信息竞赛数据结构—树的基础知识共78页，您现在浏览的是第10页!(2).后序（根）遍历：先从左到右遍历各棵子树，再访问根结点。如上图后序遍历的结果为：562389741；(3).层次遍历：按层次从小到大逐个访问，同一层次按照从左到右的次序。如上图层次遍历的结果为：123456789；（广度优先遍历）思想如下：若某个结点被访问，则该结点的子结点应登录，等待被访问。顺序访问各层次上结点，直至不再有未访问过的结点。(4).叶结点遍历：有时，把所有的数据信息都存放在叶结点中，而其余结点都是用来表示数据之间的某种分支或层次关系，这种情况就用这种方法。如上图按照这个思想访问的结果为：56389；树的遍历高中信息竞赛数据结构—树的基础知识共78页，您现在浏览的是第11页!1、树的统计输入森林中的结点关系，统计森林中树的数量，输出树的根。输入：行：n：结点数量；k：边数；（n,k<=100）以下k行：每行两个结点编号：i，j：i是j的父结点(I,j<=100)。输出：行：树的数量。第二行：依次输出森林中树的根结点编号（从小到大）。样例输入：9712234645789194输出：279应用:高中信息竞赛数据结构—树的基础知识共78页，您现在浏览的是第12页!2、找树根和孩子（treea.pas）给定一棵树，输出树的根root，孩子最多的结点max以及他的孩子。输入：行：n（结点个数），m（边数）。以下m行；每行两个结点x和y，表示y是x的孩子。输出：行：树根：root。第二行：孩子最多的结点max。第三行：max的孩子。样例输入：8741421315262728样例输出：42678高中信息竞赛数据结构—树的基础知识共78页，您现在浏览的是第13页!第二节:二叉树的基本概念高中信息竞赛数据结构—树的基础知识共78页，您现在浏览的是第14页!二叉树和树区别：⑴树的每一个结点可以有任意多个孩子，而二叉树中每个结点的孩子数不能超过2；⑵树的子树可以不分次序（除有序树外）；而二叉树的子树有左右之分。左儿子和右儿子。下图列出二叉树的五种基本形态：高中信息竞赛数据结构—树的基础知识共78页，您现在浏览的是第15页!3、二叉树的三个主要性质性质1：在二叉树的第i（i≥1）层上，最多有2i-1个结点性质2：在深度为k(k≥1)的二叉树中最多有2k-1个结点。性质3：在任何二叉树中，叶子结点数总比度为2的结点多1。n0=n2+1(设n0为二叉树的叶结点数；n2为二叉树中度为2的结点数)高中信息竞赛数据结构—树的基础知识共78页，您现在浏览的是第16页!【试题分析】：如果一棵m度的树中有N1个度为1的顶点，N2个度为2的顶点，N3个度为3的顶点，……，Nm个度为m的顶点，求该树中叶子顶点个数。分析：设叶子结点数为N0所有结点数为n，边数(分支）为b，则有：n=b+1(1)又：n=N0+N1+N2+…..+NM(2)

b=

N1+2N2+3N3+…..+M*NM(3)(2),(3)代入（1）得出：N0=N2+2N3+3N4+…..+(M-1)NM+1高中信息竞赛数据结构—树的基础知识共78页，您现在浏览的是第17页!二、二叉树的存储结构二叉树的存储结构有两种形式⑴顺序存储结构(重点)⑵链式存储结构高中信息竞赛数据结构—树的基础知识共78页，您现在浏览的是第18页!例如，采用数组tree存储二叉树（如下图）高中信息竞赛数据结构—树的基础知识共78页，您现在浏览的是第19页!⑴、前（根）序遍历前序遍历的规则为：若二叉树为空，则退出。否则⑴访问处理根结点；⑵前序遍历左子树；⑶前序遍历右子树；abdehicfg高中信息竞赛数据结构—树的基础知识共78页，您现在浏览的是第20页!⑶后序遍历后序遍历的规则如下：若二叉树为空，则退出；否则⑴后序遍历左子树；⑵后序遍历右子树；⑶访问处理根结点；若后序遍历上图中的二叉树，可以得到如下的后序序列dhiebfgca高中信息竞赛数据结构—树的基础知识共78页，您现在浏览的是第21页!1、编程实现：二叉树的遍历（tree1.pas）建立二叉树，然后实现：输出先序遍历、中序遍历、后序遍历的结果。输入：行：结点个数n。以下行：每行3个数，个是父亲，后两个依次为左右孩子，0表示空。输出：根、先中后序遍历结果。样例输入：8124200480315560607800700样例输出：3312485672184367528417653高中信息竞赛数据结构—树的基础知识共78页，您现在浏览的是第22页!四、树或森林转换成二叉树1、树转化为二叉树一棵有序树转化成二叉树的根结点是没有右子树的,并且除保留每个结点的最左分支外，其余分支应去掉,然后从最左的儿子开始沿右儿子方向依次链接该结点的全部儿子。例如将下图(a)所示的普通有序树转换成二叉树(下图（b))。高中信息竞赛数据结构—树的基础知识共78页，您现在浏览的是第23页!森林转化为二叉树1240Description：将一棵一般树（由单字符组成）转换成二叉树，并将转换得到的二叉树按先序、中序、后序进行遍历，输出遍历后结点的序列。(最多30个结点)

Input7

'A'2340

'B'50

'C'670

'D'0

'E'0

'F'0

'G'0OutputABECFGD

EBFGCDA

EGFDCBA高中信息竞赛数据结构—树的基础知识共78页，您现在浏览的是第24页!五、由二叉树的两种遍历顺序确定树结构遍历二叉树（如下图）有三种规则： 前序遍历：根—左子树—右子树；中序遍历：左子树—根—右子树；后序遍历：左子树—右子树—根；问:已知前序序列和中序序列能否确定出二叉树?已知中序序列和后序序列能否确定出二叉树?已知前序序列和后序序列能否确定出二叉树?高中信息竞赛数据结构—树的基础知识共78页，您现在浏览的是第25页!2、(NOIP7)已知一棵二叉树的结点名为大写英文字母，中序：CBGEAFHDIJ后序：CGEBHFJIDA求该二叉树的先序遍历的顺序为多少?1、已知：先序遍历结果：ABCDEFGH

中序遍历结果：CBEDAGHF求后序遍历结果。高中信息竞赛数据结构—树的基础知识共78页，您现在浏览的是第26页!#include<iostream>usingnamespacestd;chara[20],b[20];voidf(chara[],charb[],intll){inti=0;cout<<b[ll-1];while(a[i]!=b[ll-1])i++;if(i>0)f(a,b,i);if(i<ll-1)f(a+i+1,b+i,ll-1-i);}intmain(){cin>>a>>b;f(a,b,strlen(b));return0;}课后完成已知中序和后序求先序。高中信息竞赛数据结构—树的基础知识共78页，您现在浏览的是第27页!【分析】此题的后序遍历适合用递归算法完成。由题目可知，输入数据给出的字符为所要遍历的fbi树的叶结点代码，又因为字符串的长度为2的整数次幂，故此fbi树为完全二叉树。由于题中明确规定：子符串中的字符都是‘0’，为B串；都是‘1’，为I串；既有‘0’又有‘1’，为F串。即：二叉树的子结点都是B，父结点为B；子结点都是I，父结点为I；既有I又有B，父结点为F。因此，根据树的子结点可以求出父结点。我们要做的是根据子结点后序遍历二叉树。基本算法为：

voidbianli(intx,inty)//遍历过程；x，y：为子结点在数组a中的位置。

{

if(x==y)输出叶结点;//结束递归条件，结点为一个字符。

else{

遍历左子树；

遍历右子树；求出父结点；

输出父结点；

}

}

//递归算法

高中信息竞赛数据结构—树的基础知识共78页，您现在浏览的是第28页!六．二叉排序树所谓二叉排序树是指具有下列性质的非空二叉树⑴若根结点的左子树不空，则左子树的所有结点值均小于根结点值；⑵若根结点的右子树不空，则右子树的所有结点值均不小于根结点值；⑶根结的左右树也分别为二叉排序树；显然，对二叉排序树进行中序遍历，可得出结点值递增的排序序列。如下面的排序二叉树按中序遍历结果为：5689101113141517如何生成这样的一棵二叉树呢？高中信息竞赛数据结构—树的基础知识共78页，您现在浏览的是第29页!

cin>>n>>x;//建立根节点tree[1][1]=x;for(i=2;i<=n;i++){cin>>x;root=1;p=true;while(p){if(tree[root][1]>=x)//小于等于根节点的情况if(tree[root][2]==0){tree[i][1]=x;//加入树tree[root][2]=i;//连接p=false;}elseroot=tree[root][2];//对下一个根进行搜索if(tree[root][1]<x)//大于根节点的情况if(tree[root][3]==0){tree[i][1]=x;//加入树tree[root][3]=i;//连接p=false;}elseroot=tree[root][3];//对下一个根进行搜索}}高中信息竞赛数据结构—树的基础知识共78页，您现在浏览的是第30页!3.二叉排序树的查找-------查找第k小的数

二叉排序树的典型应用-------查找第k小的数

高中信息竞赛数据结构—树的基础知识共78页，您现在浏览的是第31页!用排序二叉树查找第k小的数

intfind(intkey)//查找第k小的数{i=1;k=key;while(1){j=tree[tree[i,2]][4];//取左子树的子孙数if(k<=j)i=tree[i,2];//k比j小，说明第k小的数在左子树elseif(k==j+1)returntree[i][1];//k比j大1,说明第k小的数是当前节点elsei=tree[i][3];

//k比j大1以上,说明第k小的数在右子树k=k-j-1;}}高中信息竞赛数据结构—树的基础知识共78页，您现在浏览的是第32页!显然图(D)所示的合并方法付出的代价最小:545*2+（2+4）*3+（6+7）*2=54例如n=5,重量分别为7、5、2、4、6。246511671324(D)

L=6+11+13+24=54高中信息竞赛数据结构—树的基础知识共78页，您现在浏览的是第33页!2、最优二叉树的构造方法假定给出n个结点ki(i=1‥n)，其权值分别为wi(i=1‥n)。要构造以此n个结点为叶结点的最优二叉树，其构造方法如下：首先,将给定的n个结点构成n棵二叉树的集合F={T1,T2,……,Tn}。其中每棵二叉树Ti中只有一个权值为wi的根结点ki，其左、右子树均为空。然后做以下两步⑴.在F中选取根结点权值最小的两棵二叉树作为左右子树,构造一棵新的二叉树,并且置新的二叉树的根结点的权值为其左、右子树根结点的权值之和；⑵.在F中删除这两棵二叉树,同时将新得到的二叉树加入F中；重复⑴、⑵,直到在F中只含有一棵二叉树为止。这棵二叉树便是最优二叉树。

以上构造最优二叉树的方法称为哈夫曼（huffmann）算法。高中信息竞赛数据结构—树的基础知识共78页，您现在浏览的是第34页!⑵以具有权值16及2的根结点的两棵二叉树为左、右子树，构造一棵根权值为18的新二叉树，并从F中删去这两棵二叉树（如下图）：高中信息竞赛数据结构—树的基础知识共78页，您现在浏览的是第35页!⑷又得到一个新二叉树的集合F，其根结点的权值分别为34，41（如下图）：高中信息竞赛数据结构—树的基础知识共78页，您现在浏览的是第36页!3、哈夫曼编码使用频率高的采用短的的编码,则总的编码长度便可减少.例如:在某通讯中只使用abcd四种字符,其出现频率分别为:0.4,0.3,0.2,0.1。请进行哈夫曼编码。使通讯码尽可能的短,并写出信息：bbdaac的编码。高中信息竞赛数据结构—树的基础知识共78页，您现在浏览的是第37页!⑥(NOIP6)在有N个叶子节点的哈夫曼树中，其节点总数为（）

A.不确定B.2N-1C.2N+1D.2N

高中信息竞赛数据结构—树的基础知识共78页，您现在浏览的是第38页!在最优二叉树的顺序存储结构中前n个结点为叶结点。构造最优二叉树的算法如下：intminn(inth)//在前h个结点中选择父指针为0且权值最小的结点{ml=∞；for(p=1;p<=h;p++)if((tree[p].prt==0)&&(m1>tree[p].data))//没有父亲结点且较小的结点{i=p;m1=tree[p].data;}returni;}高中信息竞赛数据结构—树的基础知识共78页，您现在浏览的是第39页!计算每一个叶结点的路径长度Voidht(intt)//通过前序遍历计算每一个叶结点的路径长度{if(t==m)tree[t].lth=0;//若结点t为根,则路径长度为0;否则结点t的路径长度为其父结点的路径长度+1elsetree[t].lth=tree[tree[t].prt].lth+1;if(tree[t].lch!=0){ht(tree[t].lch);ht(tree[t].rch);}//分别递归左右子树}由此可见,叶结点t（1≤t≤n）的带权路径长度即为:tree[t].lth*tree[t].data。高中信息竞赛数据结构—树的基础知识共78页，您现在浏览的是第40页!树的递归定义如下：树是n(n>0)个结点的有限集，这个集合满足以下条件：⑴有且仅有一个结点没有前驱（父亲结点），该结点称为树的根；⑵除根外，其余的每个结点都有且仅有一个前驱；⑶除根外，每一个结点都通过唯一的路径连到根上（否则有环）。这条路径由根开始，而未端就在该结点上，且除根以外，路径上的每一个结点都是前一个结点的后继（儿子结点）；由上述定义可知，树结构没有封闭的回路。

一、树的概念1、树的定义高中信息竞赛数据结构—树的基础知识共78页，您现在浏览的是第41页!2、结点的分类结点一般分成三类⑴根结点：没有父亲的结点。在树中有且仅有一个根结点。⑵分支结点：除根结点外，有孩子的结点称为分支结点。b，c，x，t，d，i。分支结点亦是其子树的根；⑶叶结点：没有孩子的结点称为树叶。w，h，e，f，s，m，o，n，j，u为叶结点。根结点到每一个分支结点或叶结点的路径是唯一的。从根r到结点i的唯一路径为rcti。高中信息竞赛数据结构—树的基础知识共78页，您现在浏览的是第42页!4、树的深度（高度）

树是分层次的。结点所在的层次是从根算起的。根结点在层，根的儿子在第二层，其余各层依次类推。图中的树共有五层。在树中，父结点在同一层的所有结点构成兄弟关系。树中最大的层次称为树的深度，亦称高度。图中树的深度为5。高中信息竞赛数据结构—树的基础知识共78页，您现在浏览的是第43页!6、有序树和无序树按照树中同层结点是否保持有序性，可将树分为有序树和无序树。如果树中同层结点从左而右排列，其次序不容互换，这样的树称为有序树；如果同层结点的次序任意，这样的树称为无序树。高中信息竞赛数据结构—树的基础知识共78页，您现在浏览的是第44页!

⑵.括号表示法：先将根结点放入一对圆括号中，然后把它的子树按由左而右的顺序放入括号中，而对子树也采用同样方法处理：同层子树与它的根结点用圆括号括起来，同层子树之间用逗号隔开，最后用闭括号括起来。例如图可写成如下形式(A(B(E(K,L),F),C(G),D(H(M),I,J)))优点:易于保存;缺点:不直观.高中信息竞赛数据结构—树的基础知识共78页，您现在浏览的是第45页!12345678910111213下标信息儿子1A2342B5603C7004D89105E111206F0007G0008H13009I00010J00011K00012L00013M000Idatach[1..m]高中信息竞赛数据结构—树的基础知识共78页，您现在浏览的是第46页!树的双亲表示法优缺点：利用了树中除根结点外每个结点都有唯一的父结点这个性质。很容易找到树根，但找孩子时需要遍历整个线性表。高中信息竞赛数据结构—树的基础知识共78页，您现在浏览的是第47页!

(1).前序（根）遍历：先访问根结点，再从左到右按照前序思想遍历各棵子树。如上图前序遍历的结果为：125634789；具体步骤（深度优先遍历）１.读入数据cin>>n;for(i=1;i<=n;i++)cin>>tree[i][1]>>tree[i][2];２.寻找根节点root=1;while(tree[root][2]!=0)root=tree[root][2];//寻找根节点3.先序遍历树voiddfs(intk)//深度优先遍历{cout<<tree[k][1]<<“”;//输出当前节点for(i=1;i<=n;i++)if(tree[i][2]==k)dfs(i);//遍历当前节点孩子}树的遍历高中信息竞赛数据结构—树的基础知识共78页，您现在浏览的是第48页!树的宽度和深度描述：对于每个节点，找到它离根节点的层数。最大层数即为深度，相同层数节点数最多为最大宽度。

高中信息竞赛数据结构—树的基础知识共78页，您现在浏览的是第49页!#include<iostream>usingnamespacestd;intn,m,tree[101],ans[10];intmain(){inti,x,y,root,maxroot,sum=0,j=0,max=0;cin>>n>>m;memset(tree,0,sizeof(tree));//默认根标志是本身,各自是独立的一棵树for(i=1;i<=m;i++){cin>>x>>y;tree[y]=x;}for(i=1;i<=n;i++)if(tree[i]==0){ans[++j]=i;sum++;}cout<<sum<<endl;for(i=1;i<=j;i++)cout<<ans[i]<<'';return0;}核心代码高中信息竞赛数据结构—树的基础知识共78页，您现在浏览的是第50页!#include<iostream>usingnamespacestd;intn,m,tree[101]={0};intmain(){inti,x,y,root,maxroot,sum=0,j,Max=0;cin>>n>>m;for(i=1;i<=m;i++){cin>>x>>y;tree[y]=x;}for(i=1;i<=n;i++)//找出树根if(tree[i]==0){root=i;break;}

for(i=1;i<=n;i++)//找孩子最多的结点

{sum=0;for(j=1;j<=n;j++)if(tree[j]==i)sum++;if(sum>Max){Max=sum;maxroot=i;}}cout<<root<<endl<<maxroot<<endl;if(tree[i]==maxroot)cout<<i<<"";return0;}高中信息竞赛数据结构—树的基础知识共78页，您现在浏览的是第51页!一、二叉树的概念二叉树的特点:是每个结点最多有两个孩子，且其子树有左右之分（有序树，次序不能任意颠倒）。1、二叉树的递归定义和基本形态二叉树是以结点为元素的有限集，它或者为空，或者满足以下条件：⑴有一个特定的结点称为根；⑵余下的结点分为互不相交的子集L和R，其中L是根的左子树；R是根的右子树；L和R又是二叉树；由此定义可以看出，一个二叉树中的每个结点只能含有0、1或2个孩子高中信息竞赛数据结构—树的基础知识共78页，您现在浏览的是第52页!2、二叉树的两个特殊形态

⑴满二叉树：如果一棵深度为K的二叉树，共有2K-1个结点，即第i层有2i-1的结点，称为满二叉树。(a)

⑵完全二叉树：如果一棵二叉树最多只有最下面两层结点度数可以小于2，并且最下面一层的结点都集中在该层最左边的若干位置上，则称此二叉树为完全二叉树（例如下图(b)）(a)(b)高中信息竞赛数据结构—树的基础知识共78页，您现在浏览的是第53页!设n0为二叉树的叶结点数；n1为二叉树中度为1的结点数；n2为二叉树中度为2的结点数，显然n=n0+n1+n2（1）由于二叉树中除了根结点外，其余每个结点都有且仅有一个边指向父亲。设b为二叉树的边的个数，n=b+1（2）所有这些分支同时又为度为1和度为2的结点发出的。因此又有b=n1+2n2(3)由1，2，3得到：n0=n2+1高中信息竞赛数据结构—树的基础知识共78页，您现在浏览的是第54页!①(NOIP9)一个高度为h的二叉树最小元素数目（

）。

A）2h+1

B）h

C）2h-1

D）2h

E）2h-1②(NOIP8)按照二叉数的定义，具有3个结点的二叉树有（）种。A）3B）4C）5D）6③(NOIP8)设有一棵k叉树，其中只有度为0和k两种结点，设n0，nk，分别表示度为0和度为k的结点个数，试求出n0和nk之间的关系（n0=数学表达式，数学表达式仅含nk、k和数字）。④(NOIP7).一棵二叉树的高度为h，所有结点的度为0，或为2，则此树最少有()个结点A)2h-1B)2h-1C)2h+1D)h+1高中信息竞赛数据结构—树的基础知识共78页，您现在浏览的是第55页!1、顺序存储结构将每个结点依次存放在一维数组中，用数组下标指示结点编号，编号的方法是从根结点开始编号1，然后由左而右进行连续编号。每个结点的信息包括#definem树中结点数上限；structtreetype{intdata；//数据值intprt,lch,rch;//父结点、左儿子、右儿子编号}treetypetree[m]；高中信息竞赛数据结构—树的基础知识共78页，您现在浏览的是第56页!三、二叉树的遍历(访问)所谓二叉树的遍历是指按照一定的规律不重复地访问二叉树中的每一个结点。如果用L、D、R分别表示遍历左子树、访问根结点、遍历右子树，则对二叉树的遍历可以有下列六种（3!=6）组合：LDR、LRD、DLR、DRL、RDL、RLD若再限定先左后右的次序，则只剩下三种组合

DLR、LDR、LRD这三种遍历规则分别称为先（前）序遍历、中序遍历和后序遍历（以根为标准）。高中信息竞赛数据结构—树的基础知识共78页，您现在浏览的是第57页!⑵中序遍历中序遍历的规则如下：若二叉树为空，则退出；否则⑴中序遍历左子树；⑵访问处理根结点；⑶中序遍历右子树；若中序遍历上图中的二叉树，可以得到如下的中序序列：dbheiafcg高中信息竞赛数据结构—树的基础知识共78页，您现在浏览的是第58页!

关于前面讲的表达式树，我们可以分别用先序、中序、后序的遍历方法得出完全不同的遍历结果，如对于右图3种遍历结果如下，它们正好对应着表达式的3种表示方法。-+a*b-cd/ef(前缀表示、波兰式)a+b*c-d-e/f(中缀表示)abcd-*+ef/-(后缀表示、逆波兰式)高中信息竞赛数据结构—树的基础知识共78页，您现在浏览的是第59页!#include<iostream>usingnamespacestd;inta[100][2],b[100];intdfs(intk,intw){if(w==1)cout<<k<<"";if(a[k][0]!=0)dfs(a[k][0],w);if(w==2)cout<<k<<"";if(a[k][1]!=0)dfs(a[k][1],w);if(w==3)cout<<k<<"";return0;}intmain(){intn,i,j,m,t,root;cin>>n;for(i=1;i<=n;i++)//边读入边建立二叉树{cin>>t;cin>>a[t][0]>>a[t][1];b[a[t][0]]=1;b[a[t][1]]=1;}for(i=1;i<=n;i++)if(b[i]==0){root=i;break;}dfs(root,1);cout<<endl;dfs(root,2);cout<<endl;dfs(root,3);cout<<endl;}高中信息竞赛数据结构—树的基础知识共78页，您现在浏览的是第60页!高中信息竞赛数据结构—树的基础知识共78页，您现在浏览的是第61页!intdfs(intk,intw){if(w==1)cout<<char(k-1+'A');if(a[k][0]!=0)dfs(a[k][0],w);if(w==2)cout<<char(k-1+'A');if(a[k][1]!=0)dfs(a[k][1],w);if(w==3)cout<<char(k-1+'A');return0;}intmain(){intn,i,j,m,b;strings;cin>>n;for(i=1;i<=n;i++)//边读入边建立二叉树{cin>>s;for(j=1;;j++){cin>>m;if(m==0)break;if(j==1)a[i][0]=m;//左儿子编号elsea[b][1]=m;//右儿子编号b=m;}}dfs(1,1);cout<<endl;dfs(1,2);cout<<endl;dfs(1,3);cout<<endl;}高中信息竞赛数据结构—树的基础知识共78页，您现在浏览的是第62页!例题:由二叉树的先序序列和中序序列可唯一地确定一棵二叉树。例,先序序列{ABHFDECKG}和中序序列{HBDFAEKCG},构造二叉树过程如下：高中信息竞赛数据结构—树的基础知识共78页，您现在浏览的是第63页!Description：给出一棵二叉树的中序与后序排列。求出它的先序排列。(约定树结点用不同的大写字母表示，长度≤8)。Input：一棵二叉树的中序与后序排列Output：先序排列SampleInput：BADCBDCASampleOutput：ABCD【培训试题】求先序排列1010高中信息竞赛数据结构—树的基础知识共78页，您现在浏览的是第64页!Description我们可以把由“0”和“1”组成的字符串分为三类：全“0”串称为B串，全“1”串称为I串，既含“0”又含“1”的串则称为F串。

FBI树是一种二叉树，它的结点类型也包括F结点，B结点和I结点三种。由一个长度为2^N的“01”串S可以构造出一棵FBI树T，递归的构造方法如下：

1)T的根结点为R，其类型与串S的类型相同3)；

2)若串S的长度大于1，将串S从中间分开，分为等长的左右子串S1和S2；由左子串S1构造R的左子树T1，由右子串S2构造R的右子树T2。

现在给定一个长度为2^N的“01”串，请用上述构造方法构造出一棵FBI树，并输出它的后序遍历序列。Input输入的行是一个整数N（0<=N<=10），第二行是一个长度为2^N的“01”串。Output输出包括一行，这一行只包含一个字符串，即FBI树的后序遍历序列。SampleInput310001011SampleOutputIBFBBBFIBFIIIFFHint对于40%的数据，N<=2；

对于全部的数据，N<=10。FBZ树1056高中信息竞赛数据结构—树的基础知识共78页，您现在浏览的是第65页!voidbianli(intx,inty)//递归过程,x,y为所要遍历的树的叶结点在数组a中位置}{if(x==y){if(a[x]=='0')cout<<"B";if(a[x]=='1')cout<<"I";}//输出叶结点else{bianli(x,x+(y-x+1)/2-1);//遍历左子树bianli(x+(y-x+1)/2,y);//遍历右子树treei=false;treeb=false;for(i=x;i<=y;i++)//求根节点if(a[i]=='0')treeb=true;elsetreei=true;//求出树的父结点if(treei&&treeb)tree='F';else{if(treei)tree='I';if(treeb)tree='B';//输出父结点}cout<<tree;}}高中信息竞赛数据结构—树的基础知识共78页，您现在浏览的是第66页!2．二叉排序树的生成a1,a2,………an为初始序列．我们按照下述规则生成其对应的二叉排序树：(1).令a1为二叉树的根(2).若a2<a1,则令a2为a1左子树的跟结点，否则令a2为a1的右子树的根结点；(3).对a3,a4,a5,…….,an递归重复步骤(2);高中信息竞赛数据结构—树的基础知识共78页，您现在浏览的是第67页!1.怎样在一个有序序列中统计<=ai或者>=ai的顶点个数?2.怎样在一个有序序列中统计ai<=x<=aj的顶点个数?问题高中信息竞赛数据结构—树的基础知识共78页，您现在浏览的是第68页!二叉排序树用于动态查找12623381825195297查找7找到了!高中信息竞赛数据结构—树的基础知识共78页，您现在浏览的是第69页!【石子合并问题】有n堆石子,每堆有一个重量,每次把2堆石子合并成1堆,付出的代价为这两堆石子的重量之和,如果把这n堆石子最后合并成1堆石子,怎样合并才能使付出的代价最小,求出最小的代价.七、最优二叉树(哈夫曼树)高中信息竞赛数据结构—树的基础知识共78页，您现在浏览的是第70页!1、最优二叉树的定义在具有n个带权叶结点的二叉树中，使所有叶结点的带权路径长度之和（即二叉树的带权路径长度）为最小的二叉树，称为最优二叉树（又称