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

高中信息竞赛数据结构树的基础知识树及其应用树及其应用高中信息竞赛数据结构树的基础知识高中信息竞赛数据结构树的基础知识高中信息竞赛数据结构树的基础知识树的递归定义如下：树的递归定义如下： 树是树是n(n(n0n0) )个结点的有限集，这个集合满足以下条件：个结点的有限集，这个集合满足以下条件： 有且仅有一个结点没有前驱（父亲结点），该结点称为树有且仅有一个结点没有前驱（父亲结点），该结点称为树的根；的根； 除根外，其余的每个结点都有且仅有一个前驱；除根外，其余的每个结点都有且仅有一个前驱； 除根外，每一个结点都通过除根外，每一个结点都通过唯一唯一的路径连到根上（否则有的路径连到根上（否则有环）。这条路径由根开始，而未端就在该结点上，且除根以环）。这条路径由根开始，而未端就在该结点上，且除根以外，路径上的每一个结点都是前一个结点的后继（儿子结外，路径上的每一个结点都是前一个结点的后继（儿子结点）；点）；由上述定义可知，树结构没有封闭的回路。由上述定义可知，树结构没有封闭的回路。 1、树的定义、树的定义高中信息竞赛数据结构树的基础知识高中信息竞赛数据结构树的基础知识高中信息竞赛数据结构树的基础知识高中信息竞赛数据结构树的基础知识高中信息竞赛数据结构树的基础知识 所谓森林，是指若干棵互不相交的树的集合。如图去掉根所谓森林，是指若干棵互不相交的树的集合。如图去掉根结点结点A A，其原来的三棵子树，其原来的三棵子树T Tb b，T Tc c，T Td d的集合的集合TTb b，T Tc c，T Td d 就为就为森林，这三棵子树的具体形态如图（森林，这三棵子树的具体形态如图（c c）。）。高中信息竞赛数据结构树的基础知识高中信息竞赛数据结构树的基础知识二、树的表示方法和存储结构二、树的表示方法和存储结构1 1、树的表示方法、树的表示方法树的表示方法一般有两种：树的表示方法一般有两种： 自然界的树形表示法：用结点和边表示树，例如上图自然界的树形表示法：用结点和边表示树，例如上图采用的就是自然界的树形表示法。树形表示法一般用于分析问采用的就是自然界的树形表示法。树形表示法一般用于分析问题。题。高中信息竞赛数据结构树的基础知识. .括号表示法：括号表示法： 先将根结点放入一对圆括号中，然后把它的子树按由左先将根结点放入一对圆括号中，然后把它的子树按由左而右的顺序放入括号中，而对子树也采用同样方法处理：同而右的顺序放入括号中，而对子树也采用同样方法处理：同层子树与它的根结点用圆括号括起来，同层子树之间用逗号层子树与它的根结点用圆括号括起来，同层子树之间用逗号隔开，最后用闭括号括起来。例如图可写成如下形式隔开，最后用闭括号括起来。例如图可写成如下形式(A(B(E(K,L),F),C(G),D(H(M),I,J) 优点优点:易于保存易于保存;缺点缺点:不直观不直观.高中信息竞赛数据结构树的基础知识2 2、树的存储结构、树的存储结构高中信息竞赛数据结构树的基础知识12345678910111213高中信息竞赛数据结构树的基础知识DataParent高中信息竞赛数据结构树的基础知识高中信息竞赛数据结构树的基础知识高中信息竞赛数据结构树的基础知识 高中信息竞赛数据结构树的基础知识高中信息竞赛数据结构树的基础知识 高中信息竞赛数据结构树的基础知识1、树的统计、树的统计输入森林中的结点关系，统计森林中树的数量，输出树的根。输入森林中的结点关系，统计森林中树的数量，输出树的根。输入：输入：第一行：第一行：n：结点数量；：结点数量；k：边数；（：边数；（n,k=100）以下以下k行：每行两个结点编号：行：每行两个结点编号：i，j：i是是j的父结点的父结点(I,j=100)。输出：输出：第一行：树的数量。第一行：树的数量。第二行：依次输出森林中树的根结点编号（从小到大）。第二行：依次输出森林中树的根结点编号（从小到大）。样例输入：样例输入：9 71 22 34 64 57 89 1 9 4输出：输出：27 9应用应用:高中信息竞赛数据结构树的基础知识#includeusing namespace std;int n,m,tree101,ans10;int main() int i,x,y,root,maxroot,sum=0,j=0,max=0; cinnm; memset(tree,0,sizeof(tree);/默认根标志是本身默认根标志是本身,各自是独立的一棵树各自是独立的一棵树 for(i=1;ixy;treey=x; for(i=1;i=n;i+) if(treei=0)ans+j=i;sum+; coutsumendl; for(i=1;i=j;i+) coutansi ; return 0;高中信息竞赛数据结构树的基础知识2、找树根和孩子（、找树根和孩子（treea.pas）给定一棵树，输出树的根给定一棵树，输出树的根root，孩子最多的结点，孩子最多的结点max以及他的孩子。以及他的孩子。输入：输入：第一行：第一行：n（结点个数），（结点个数），m（边数）。（边数）。以下以下m行；每行两个结点行；每行两个结点x和和y，表示，表示y是是x的孩子。的孩子。输出：输出：第一行：树根：第一行：树根：root。第二行：孩子最多的结点第二行：孩子最多的结点max。第三行：第三行：max的孩子。的孩子。样例输入：样例输入：8 74 14 21 31 52 62 72 8样例输出：样例输出：42 6 7 8高中信息竞赛数据结构树的基础知识#includeusing namespace std;int n,m,tree101=0;int main() int i,x,y,root,maxroot,sum=0,j,Max=0; cinnm; for(i=1;ixy;treey=x; for(i=1;i=n;i+)/找出树根找出树根 if(treei=0)root=i;break; for(i=1;i=n;i+)/找孩子最多的结点找孩子最多的结点 sum=0; for(j=1;jMax)Max=sum;maxroot=i; coutrootendlmaxrootendl; if(treei=maxroot)couti ; return 0; 高中信息竞赛数据结构树的基础知识高中信息竞赛数据结构树的基础知识一、二叉树的概念一、二叉树的概念 二叉树的特点二叉树的特点: :是每个结点最多有两个孩子，且其子树有是每个结点最多有两个孩子，且其子树有左右之分（有序树，次序不能任意颠倒）。左右之分（有序树，次序不能任意颠倒）。1 1、二叉树的递归定义和基本形态、二叉树的递归定义和基本形态 二叉树是以结点为元素的有限集，它或者为空，或者满足二叉树是以结点为元素的有限集，它或者为空，或者满足以下条件：以下条件： 有一个特定的结点称为根；有一个特定的结点称为根； 余下的结点分为互不相交的子集余下的结点分为互不相交的子集L L和和R R，其中，其中L L是根的左是根的左子树；子树；R R是根的右子树；是根的右子树；L L和和R R又是二叉树；又是二叉树；高中信息竞赛数据结构树的基础知识二叉树和树区别：二叉树和树区别： 树的每一个结点可以有任意多个孩子，而二叉树中每个树的每一个结点可以有任意多个孩子，而二叉树中每个结点的孩子数不能超过结点的孩子数不能超过2 2； 树的子树可以不分次序（除有序树外）；而二叉树的子树的子树可以不分次序（除有序树外）；而二叉树的子树有左右之分。左儿子和右儿子。树有左右之分。左儿子和右儿子。下图列出二叉树的五种基本形态：下图列出二叉树的五种基本形态：高中信息竞赛数据结构树的基础知识(a)(b)高中信息竞赛数据结构树的基础知识3 3、二叉树的三个主要性质、二叉树的三个主要性质性质性质1 1：在二叉树的第：在二叉树的第i i（i1i1）层上，最多有）层上，最多有2 2i-1i-1个结点个结点性质性质2 2：在深度为：在深度为k(k1)k(k1)的二叉树中最多有的二叉树中最多有2 2k k-1-1个结点。个结点。性质性质3 3：在任何二叉树中，叶子结点数总比度为：在任何二叉树中，叶子结点数总比度为2 2的结点多的结点多1 1。 n n0 0=n=n2 2+1+1( (设设n n0 0为二叉树的叶结点数；为二叉树的叶结点数；n n2 2为二叉树中度为为二叉树中度为2 2的结点数的结点数) )高中信息竞赛数据结构树的基础知识设设n n0 0为二叉树的叶结点数；为二叉树的叶结点数；n n1 1为二叉树中度为为二叉树中度为1 1的结点数；的结点数；n n2 2为二叉树中度为为二叉树中度为2 2的结点数，显然的结点数，显然 n=nn=n0 0+n+n1 1+n+n2 2 （1 1）由于二叉树中除了根结点外，其余每个结点都有且仅有一由于二叉树中除了根结点外，其余每个结点都有且仅有一个边指向父亲。设个边指向父亲。设 b b为二叉树的边的个数，为二叉树的边的个数， n=b+1 n=b+1 （2 2） 所有这些分支同时又为度为所有这些分支同时又为度为1 1和度为和度为2 2的结点发出的。因此的结点发出的。因此又有又有 b=nb=n1 1+2n+2n2 2 (3) (3)由由1，2，3得到：得到：n0=n2+1高中信息竞赛数据结构树的基础知识【试题分析试题分析】：如果一棵：如果一棵m m度的树中有度的树中有N N1 1个度为个度为1 1的顶点，的顶点，N N2 2个个度为度为2 2的顶点，的顶点，N N3 3个度为个度为3 3的顶点，的顶点，N Nm m个度为个度为m m的顶点，的顶点，求该树中叶子顶点个数。求该树中叶子顶点个数。分析：设叶子结点数为分析：设叶子结点数为N N0 0 所有结点数为所有结点数为n n，边数，边数( (分支）为分支）为b b，则有：，则有： n=b+1 n=b+1 (1) 又：又：n= Nn= N0 0+N+N1 1+N+N2 2+.+N+.+NM M (2)(2) b=b= N N1 1+2N+2N2 2+3N+3N3 3+.+M+.+M* *N NM M (3)(3) (2),(3) (2),(3)代入（代入（1 1）得出：）得出： N N0 0 =N =N2 2+2N+2N3 3+3N+3N4 4+.+(M-1)N+.+(M-1)NM M+1+1高中信息竞赛数据结构树的基础知识(NOIP9)(NOIP9)一个高度为一个高度为h h 的二叉树最小元素数目（的二叉树最小元素数目（ ）。）。AA） 2h+1B2h+1B） h Ch C） 2h-1D2h-1D） 2hE2hE） 2h-12h-1(NOIP8)(NOIP8)按照二叉数的定义，具有按照二叉数的定义，具有3 3个结点的二叉树有（个结点的二叉树有（ ）种。）种。 A A）3 B3 B）4 C4 C）5 D5 D）6 6(NOIP8)(NOIP8)设有一棵设有一棵k k叉树，其中只有度为叉树，其中只有度为0 0和和k k两种结点，设两种结点，设n n 0 0 ，n n k k ，分别表示度为，分别表示度为0 0和度为和度为k k的结点个数，试求出的结点个数，试求出n n 0 0 和和n n k k之间的之间的关系（关系（n n 0 0 = = 数学表达式，数学表达式仅含数学表达式，数学表达式仅含n n k k 、k k和数字）。和数字）。(NOIP7).一棵二叉树的高度为一棵二叉树的高度为h，所有结点的度为，所有结点的度为0，或为，或为2，则此树最少有则此树最少有( )个结点个结点 A)2h-1 B)2h-1 C)2h+1 D)h+1高中信息竞赛数据结构树的基础知识二、二叉树的存储结构二、二叉树的存储结构二叉树的存储结构有两种形式二叉树的存储结构有两种形式 顺序存储结构顺序存储结构(重点重点) 链式存储结构链式存储结构高中信息竞赛数据结构树的基础知识高中信息竞赛数据结构树的基础知识例如，采用数组例如，采用数组treetree存储二叉树（如下图）存储二叉树（如下图）高中信息竞赛数据结构树的基础知识 三、二叉树的遍历三、二叉树的遍历( (访问访问) ) 所谓二叉树的遍历是指按照一定的规律不重复地访问二叉所谓二叉树的遍历是指按照一定的规律不重复地访问二叉树中的每一个结点。树中的每一个结点。 如果用如果用L L、D D、R R分别表示遍历分别表示遍历左左子树、访问子树、访问根根结点、遍历结点、遍历右右子树，则对二叉树的遍历可以有下列六种（子树，则对二叉树的遍历可以有下列六种（3!=63!=6）组合：）组合： LDRLDR、 LRDLRD、 DLRDLR、 DRLDRL、RDLRDL、 RLDRLD 若再限定若再限定先左后右先左后右的次序，则只剩下三种组合的次序，则只剩下三种组合 DLRDLR、LDRLDR、LRDLRD 这三种遍历规则分别称为先（前）序遍历、中序遍历和后这三种遍历规则分别称为先（前）序遍历、中序遍历和后序遍历（序遍历（以根为标准以根为标准）。）。高中信息竞赛数据结构树的基础知识、前（根）序遍历、前（根）序遍历前序遍历的规则为：若二叉树为空，则退出。否则前序遍历的规则为：若二叉树为空，则退出。否则 访问处理根结点；访问处理根结点； 前序遍历左子树；前序遍历左子树； 前序遍历右子树；前序遍历右子树； a b d e h i c f ga b d e h i c f g高中信息竞赛数据结构树的基础知识中序遍历中序遍历中序遍历的规则如下：中序遍历的规则如下：若二叉树为空，则退出；否则若二叉树为空，则退出；否则 中序遍历左子树；中序遍历左子树； 访问处理根结点；访问处理根结点； 中序遍历右子树；中序遍历右子树；若中序遍历上图中的二叉树，可以得到如下的中序序列：若中序遍历上图中的二叉树，可以得到如下的中序序列： d b h e i a f c g 高中信息竞赛数据结构树的基础知识后序遍历后序遍历后序遍历的规则如下：后序遍历的规则如下： 若二叉树为空，则退出；否则若二叉树为空，则退出；否则 后序遍历左子树；后序遍历左子树； 后序遍历右子树；后序遍历右子树； 访问处理根结点；访问处理根结点； 若后序遍历上图中的二叉树，可以得到如下的后序序列若后序遍历上图中的二叉树，可以得到如下的后序序列 d h i e b f g c a高中信息竞赛数据结构树的基础知识 高中信息竞赛数据结构树的基础知识1、编程实现：二叉树的遍历（、编程实现：二叉树的遍历（tree1.pas）建立二叉树，然后实现：输出先序遍历、中序遍历、后序遍历的结果。建立二叉树，然后实现：输出先序遍历、中序遍历、后序遍历的结果。输入：第一行：结点个数输入：第一行：结点个数n。以下行：每行。以下行：每行3个数，第一个是父亲，后两个个数，第一个是父亲，后两个依次为左右孩子，依次为左右孩子，0表示空。表示空。输出：根、先中后序遍历结果。输出：根、先中后序遍历结果。样例输入：样例输入：81 2 42 0 04 8 03 1 55 6 06 0 78 0 07 0 0样例输出：样例输出：33 1 2 4 8 5 6 72 1 8 4 3 6 7 52 8 4 1 7 6 5 3高中信息竞赛数据结构树的基础知识#includeusing namespace std;int a1002,b100;int dfs(int k,int w) if(w=1)coutk ; if(ak0!=0)dfs(ak0,w); if(w=2)coutk ; if(ak1!=0)dfs(ak1,w); if(w=3)coutkn; for(i=1;it;cinat0at1; bat0=1;bat1=1; for(i=1;i=n;i+) if(bi=0)root=i;break; dfs(root,1);coutendl; dfs(root,2);coutendl; dfs(root,3);coutendl;高中信息竞赛数据结构树的基础知识1 1、树转化为二叉树、树转化为二叉树 一棵有序树转化成二叉树的根结点是没有右子树的一棵有序树转化成二叉树的根结点是没有右子树的, ,并且除保并且除保留每个结点的最左分支外，其余分支应去掉留每个结点的最左分支外，其余分支应去掉, ,然后从最左的儿子然后从最左的儿子开始沿右儿子方向依次链接该结点的全部儿子。例如将下图开始沿右儿子方向依次链接该结点的全部儿子。例如将下图(a)(a)所所示的普通有序树转换成二叉树示的普通有序树转换成二叉树( (下图（下图（b)b)。 高中信息竞赛数据结构树的基础知识高中信息竞赛数据结构树的基础知识高中信息竞赛数据结构树的基础知识高中信息竞赛数据结构树的基础知识五、由二叉树的两种遍历顺序确定树结构五、由二叉树的两种遍历顺序确定树结构 遍历二叉树（如下图）有三种规则：遍历二叉树（如下图）有三种规则： 前序遍历：根前序遍历：根左子树左子树右子树；右子树； 中序遍历：左子树中序遍历：左子树根根右子树；右子树； 后序遍历：左子树后序遍历：左子树右子树右子树根；根； 问问:高中信息竞赛数据结构树的基础知识 例题例题:由二叉树的先序序列和中序序列可唯一地确定一棵二由二叉树的先序序列和中序序列可唯一地确定一棵二叉树。叉树。例例, 先序序列先序序列 ABHFDECKG 和中序序列和中序序列 HBDFAEKCG , 构造二叉树过程如下：构造二叉树过程如下：高中信息竞赛数据结构树的基础知识2 2、(NOIP7)(NOIP7)已知一棵二叉树的结点名为大写英文字母，已知一棵二叉树的结点名为大写英文字母， 中序：中序：CBGEAFHDIJCBGEAFHDIJ 后序：后序：CGEBHFJIDACGEBHFJIDA 求该二叉树的先序遍历的顺序为多少求该二叉树的先序遍历的顺序为多少? ?1 1、已知：先序遍历结果：、已知：先序遍历结果：ABCDEFGHABCDEFGH 中序遍历结果：中序遍历结果：CBEDAGHFCBEDAGHF 求后序遍历结果。求后序遍历结果。高中信息竞赛数据结构树的基础知识Description： 给出一棵二叉树的中序与后序排列。求出它的先序排给出一棵二叉树的中序与后序排列。求出它的先序排列。列。(约定树结点用不同的大写字母表示，长度约定树结点用不同的大写字母表示，长度8)。Input： 一棵二叉树的中序与后序排列一棵二叉树的中序与后序排列Output： 先序排列先序排列Sample Input： BADC BDCASample Output： ABCD高中信息竞赛数据结构树的基础知识#includeusing namespace std;char a20,b20;void f(char a,char b,int ll) int i=0; cout0)f(a,b,i); if(iab; f(a,b,strlen(b); return 0;高中信息竞赛数据结构树的基础知识高中信息竞赛数据结构树的基础知识高中信息竞赛数据结构树的基础知识高中信息竞赛数据结构树的基础知识高中信息竞赛数据结构树的基础知识2二叉排序树的生成二叉排序树的生成a1,a2,an为初始序列我们按照下述规则生成其对为初始序列我们按照下述规则生成其对应的二叉排序树：应的二叉排序树：(1).令令a1为二叉树的根为二叉树的根(2).若若a2a1,则令则令a2为为a1左子树的跟结点，否则令左子树的跟结点，否则令a2为为a1的的右子树的根结点；右子树的根结点；(3).对对a3,a4,a5,.,an递归重复步骤递归重复步骤(2);高中信息竞赛数据结构树的基础知识 高中信息竞赛数据结构树的基础知识高中信息竞赛数据结构树的基础知识 高中信息竞赛数据结构树的基础知识12623381825195297查找查找7找到了找到了!高中信息竞赛数据结构树的基础知识 高中信息竞赛数据结构树的基础知识高中信息竞赛数据结构树的基础知识例如n=5,重量 分别为7、5、2、4、6。246511671324高中信息竞赛数据结构树的基础知识高中信息竞赛数据结构树的基础知识高中信息竞赛数据结构树的基础知识高中信息竞赛数据结构树的基础知识高中信息竞赛数据结构树的基础知识高中信息竞赛数据结构树的基础知识高中信息竞赛数据结构树的基础知识高中信息竞赛数据结构树的基础知识高中信息竞赛数据结构树的基础知识高中信息竞赛数据结构树的基础知识高中信息竞赛数据结构树的基础知识高中信息竞赛数据结构树的基础知识高中信息竞赛数据结构树的基础知识高中信息竞赛数据结构树的基础知识计算每一个叶结点的路径长度计算每一个叶结点的路径长度高中信息竞赛数据结构树的基础知识