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

1、树及其运用树及其运用树的递归定义如下：树的递归定义如下： 树是树是n(n0)n(n0)个结点的有限集，这个集合满足以下条件：个结点的有限集，这个集合满足以下条件： 有且仅有一个结点没有前驱父亲结点，该结点称为树有且仅有一个结点没有前驱父亲结点，该结点称为树的根；的根； 除根外，其他的每个结点都有且仅有一个前驱；除根外，其他的每个结点都有且仅有一个前驱； 除根外，每一个结点都经过独一的途径连到根上否那么除根外，每一个结点都经过独一的途径连到根上否那么有环。这条途径由根开场，而未端就在该结点上，且除根有环。这条途径由根开场，而未端就在该结点上，且除根以外，途径上的每一个结点都是前一个结点的后继儿子

2、结以外，途径上的每一个结点都是前一个结点的后继儿子结点；点；由上述定义可知，树构造没有封锁的回路。由上述定义可知，树构造没有封锁的回路。 e e，f f，s s，m m，o o，n n，j j，u u为叶结点。为叶结点。根结点到每一个分支结根结点到每一个分支结点或叶结点的途径是独点或叶结点的途径是独一的。从根一的。从根r r到结点到结点i i的的独一途径为独一途径为rctircti。二、树的表示方法和存储构造二、树的表示方法和存储构造1 1、树的表示方法、树的表示方法树的表示方法普通有两种：树的表示方法普通有两种：自然界的树形表示法：用结点和边表示树，例自然界的树形表示法：用结点和边表示树，例

3、如上图采用的就是自然界的树形表示法。树形表示法如上图采用的就是自然界的树形表示法。树形表示法普通用于分析问题。普通用于分析问题。. .括号表示法：括号表示法： 先将根结点放入一对圆括号中，然后把先将根结点放入一对圆括号中，然后把它的子树按由左而右的顺序放入括号中，而它的子树按由左而右的顺序放入括号中，而对子树也采用同样方法处置：同层子树与它对子树也采用同样方法处置：同层子树与它的根结点用圆括号括起来，同层子树之间用的根结点用圆括号括起来，同层子树之间用逗号隔开，最后用闭括号括起来。例如图可逗号隔开，最后用闭括号括起来。例如图可写成如下方式写成如下方式(A(B(E(K,L),F),C(G),D(

4、H(M),I,J) (A(B(E(K,L),F),C(G),D(H(M),I,J) 优点优点: :易于保管易于保管; ;缺陷缺陷: :不直观不直观. .2 2、树的存储构造、树的存储构造树的存储构造普通有两种树的存储构造普通有两种. .静态的记录数组。一切结点存储在一个数静态的记录数组。一切结点存储在一个数组中组中, ,数组元素为记录类型数组元素为记录类型, ,包括数据域和长度包括数据域和长度为为n(nn(n为树的度为树的度) )的数组的数组, ,分别存储该结点的每分别存储该结点的每一个儿子的下标一个儿子的下标#define n #define n 树的度；树的度；#define max #d

5、efine max 结点数的上限；结点数的上限；struct treetypestruct treetype int data; / int data; /数据域数据域 int chn int chn； / /指向各儿子的下标指向各儿子的下标 treetype treemaxtreetype treemax； / /树数组树数组12345678910111213DataParent (1).前序根遍历：先访问根结点，再从左到右按照前序思想遍历各棵子树。如上图前序遍历的结果为：125634789； 详细步骤深度优先遍历.读入数据 cinn; for(i=1;itreei1treei2;.寻觅根节

6、点 root=1; while(treeroot2!=0)root=treeroot2; /寻觅根节点 3.先序遍历树 void dfs(int k)/深度优先遍历 couttreek1“ ; /输出当前节点 for(i=1;i=n;i+) if(treei2=k)dfs(i); /遍历当前节点孩子 1、树的统计、树的统计输入森林中的结点关系，统计森林中树的数量，输出树的根。输入森林中的结点关系，统计森林中树的数量，输出树的根。输入：输入：第一行：第一行：n：结点数量；：结点数量；k：边数；：边数；n,k=100以下以下k行：每行两个结点编号：行：每行两个结点编号：i，j：i是是j的父结点的父

7、结点(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);/默许根标志是本身默许根标志是本身,各自是独各自是独立的一棵树立的

8、一棵树 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。第二

9、行：孩子最多的结点第二行：孩子最多的结点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+)/找孩子最多的结点找孩子最多的结点

10、 sum=0; for(j=1;jMax)Max=sum;maxroot=i; coutrootendlmaxrootendl; if(treei=maxroot)couti ; return 0; 一、二叉树的概念一、二叉树的概念 二叉树的特点二叉树的特点: :是每个结点最多有两个孩子，且其子树有是每个结点最多有两个孩子，且其子树有左右之分有序树，次序不能恣意颠倒。左右之分有序树，次序不能恣意颠倒。1 1、二叉树的递归定义和根本形状、二叉树的递归定义和根本形状 二叉树是以结点为元素的有限集，它或者为空，或者满足二叉树是以结点为元素的有限集，它或者为空，或者满足以下条件：以下条件： 有一个特定

11、的结点称为根；有一个特定的结点称为根； 余下的结点分为互不相交的子集余下的结点分为互不相交的子集L L和和R R，其中，其中L L是根的左是根的左子树；子树；R R是根的右子树；是根的右子树；L L和和R R又是二叉树；又是二叉树； 由此定义可以看出，一个二叉树中的由此定义可以看出，一个二叉树中的每个结点只能含有每个结点只能含有0 0、 1 1或或2 2个孩子个孩子二叉树和树区别：二叉树和树区别： 树的每一个结点可以有恣意多个孩子，而二叉树中每个树的每一个结点可以有恣意多个孩子，而二叉树中每个结点的孩子数不能超越结点的孩子数不能超越2 2； 树的子树可以不分次序除有序树外；而二叉树的子树的子树

12、可以不分次序除有序树外；而二叉树的子树有左右之分。左儿子和右儿子。树有左右之分。左儿子和右儿子。以下图列出二叉树的五种根本形状：以下图列出二叉树的五种根本形状：(a)(b)3 3、二叉树的三个主要性质、二叉树的三个主要性质性质性质1 1：在二叉树的第：在二叉树的第i ii1i1层上，最多有层上，最多有2i-12i-1个结点个结点性质性质2 2：在深度为：在深度为k(k1)k(k1)的二叉树中最多有的二叉树中最多有2k-12k-1个结点。个结点。性质性质3 3：在任何二叉树中，叶子结点数总比度为：在任何二叉树中，叶子结点数总比度为2 2的结点多的结点多1 1。 n0=n2+1 n0=n2+1(

13、(设设n0n0为二叉树的叶结点数；为二叉树的叶结点数；n2n2为二叉树中度为为二叉树中度为2 2的结点数的结点数) )设设n0n0为二叉树的叶结点数；为二叉树的叶结点数；n1n1为二叉树中度为为二叉树中度为1 1的结点数；的结点数；n2n2为二叉树中度为为二叉树中度为2 2的结点数，显然的结点数，显然 n=n0+n1+n2 n=n0+n1+n2 1 1由于二叉树中除了根结点外，其他每个结点都有且仅有一由于二叉树中除了根结点外，其他每个结点都有且仅有一个边指向父亲。设个边指向父亲。设 b b为二叉树的边的个数，为二叉树的边的个数， n=b+1 n=b+1 2 2 一切这些分支同时又为度为一切这些

14、分支同时又为度为1 1和度为和度为2 2的结点发出的。因此的结点发出的。因此又有又有 b=n1+2n2 (3)b=n1+2n2 (3)由由1 1，2 2，3 3得到：得到：n0=n2+1n0=n2+1【试题分析】：假设一棵【试题分析】：假设一棵m度的树中有度的树中有N1个度为个度为1的顶点，的顶点，N2个度为个度为2的的顶点，顶点，N3个度为个度为3的顶点，的顶点，Nm个度为个度为m的顶点，求该树中叶子顶点的顶点，求该树中叶子顶点个数。个数。分析：设叶子结点数为分析：设叶子结点数为N0N0 一切结点数为一切结点数为n n，边数，边数( (分支为分支为b b，那么有：，那么有： n=b+1 (1

15、) n=b+1 (1) 又：又：n= N0+N1+N2+.+NM (2)n= N0+N1+N2+.+NM (2) b= N1+2N2+3N3+.+M b= N1+2N2+3N3+.+M* *NM (3)NM (3) (2),(3) (2),(3)代入代入1 1得出：得出： N0 =N2+2N3+3N4+.+(M-1)NM+1 N0 =N2+2N3+3N4+.+(M-1)NM+1(NOIP9)(NOIP9)一个高度为一个高度为h h 的二叉树最小元素数目的二叉树最小元素数目 。AA 2h+1B 2h+1B h C h C 2h-1D 2h-1D 2hE 2hE 2h-1 2h-1(NOIP8)(

16、NOIP8)按照二叉数的定义，具有按照二叉数的定义，具有3 3个结点的二叉树有个结点的二叉树有 种。种。 A A3 B3 B4 C4 C5 D5 D6 6(NOIP8)(NOIP8)设有一棵设有一棵k k叉树，其中只需度为叉树，其中只需度为0 0和和k k两种结点，设两种结点，设n 0 n 0 ，n k n k ，分别表示度为，分别表示度为0 0和度为和度为k k的结点个数，试求出的结点个数，试求出n 0 n 0 和和n kn k之间之间的关系的关系n 0 = n 0 = 数学表达式，数学表达式仅含数学表达式，数学表达式仅含n k n k 、k k和数字。和数字。(NOIP7).(NOIP7)

17、.一棵二叉树的高度为一棵二叉树的高度为h h，一切结点的度为，一切结点的度为0 0，或为，或为2 2，那么此树最少有那么此树最少有( )( )个结点个结点 A)2h-1 A)2h-1 B)2h-1 B)2h-1 C)2h+1 C)2h+1 D)h+1D)h+1二、二叉树的存储构造二、二叉树的存储构造二叉树的存储构造有两种方式二叉树的存储构造有两种方式 顺序存储构造顺序存储构造(重点重点) 链式存储构造链式存储构造例如，采用数组例如，采用数组treetree存储二叉树如以下图存储二叉树如以下图 三、二叉树的遍历三、二叉树的遍历( (访问访问) ) 所谓二叉树的遍历是指按照一定的规律不反复地访问二

18、叉所谓二叉树的遍历是指按照一定的规律不反复地访问二叉树中的每一个结点。树中的每一个结点。 假设用假设用L L、D D、R R分别表示遍历左子树、访问根结点、遍历分别表示遍历左子树、访问根结点、遍历右子树，那么对二叉树的遍历可以有以下六种右子树，那么对二叉树的遍历可以有以下六种3!=63!=6组合：组合： LDRLDR、 LRDLRD、 DLRDLR、 DRLDRL、RDLRDL、 RLDRLD 假设再限定先左后右的次序，那么只剩下三种组合假设再限定先左后右的次序，那么只剩下三种组合 DLRDLR、LDRLDR、LRDLRD 这三种遍历规那么分别称为先前序遍历、中序遍历和这三种遍历规那么分别称为

19、先前序遍历、中序遍历和后序遍历以根为规范。后序遍历以根为规范。、前根序遍历、前根序遍历前序遍历的规那么为：假设二叉树为空，那么退出。否那么前序遍历的规那么为：假设二叉树为空，那么退出。否那么 访问处置根结点；访问处置根结点； 前序遍历左子树；前序遍历左子树； 前序遍历右子树；前序遍历右子树； a b d e h i c f g a b d e h i c f g中序遍历中序遍历中序遍历的规那么如下：中序遍历的规那么如下：假设二叉树为空，那么退出；否那么假设二叉树为空，那么退出；否那么 中序遍历左子树；中序遍历左子树； 访问处置根结点；访问处置根结点； 中序遍历右子树；中序遍历右子树；假设中序遍

20、历上图中的二叉树，可以得到如下的中序序假设中序遍历上图中的二叉树，可以得到如下的中序序列：列： d b h e i a f c g 后序遍历后序遍历后序遍历的规那么如下：后序遍历的规那么如下： 假设二叉树为空，那么退出；否那么假设二叉树为空，那么退出；否那么 后序遍历左子树；后序遍历左子树； 后序遍历右子树；后序遍历右子树； 访问处置根结点；访问处置根结点； 假设后序遍历上图中的二叉树，可以得到如下的后序序假设后序遍历上图中的二叉树，可以得到如下的后序序列列 d h i e b f g c a 关于前面讲的表达式树，我们可以分别用先序、中序、后序的遍历方法得出完全不同的遍历结果，如对于右图3种

21、遍历结果如下，它们正好对应着表达式的3种表示方法。 -+a*b-cd/ef (前缀表示、波兰式) a+b*c-d-e/f (中缀表示) abcd-*+ef/- (后缀表示、逆波兰式)1、编程实现：二叉树的遍历、编程实现：二叉树的遍历tree1.pas建立二叉树，然后实现：输出先序遍历、中序遍历、建立二叉树，然后实现：输出先序遍历、中序遍历、后序遍历的结果。后序遍历的结果。输入：第一行：结点个数输入：第一行：结点个数n。以下行：每行。以下行：每行3个数，第个数，第一个是父亲，后两个依次为左右孩子，一个是父亲，后两个依次为左右孩子，0表示空。表示空。输出：根、先中后序遍历结果。输出：根、先中后序遍

22、历结果。样例输入：样例输入：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;

23、 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)所示的普

24、通有序树转换成二叉树所示的普通有序树转换成二叉树( (以下图以下图b)b)。 五、由二叉树的两种遍历顺序确定树构造五、由二叉树的两种遍历顺序确定树构造 遍历二叉树如以下图有三种规那么：遍历二叉树如以下图有三种规那么： 前序遍历：根前序遍历：根左子树左子树右子树；右子树； 中序遍历：左子树中序遍历：左子树根根右子树；右子树； 后序遍历：左子树后序遍历：左子树右子树右子树根；根； 问问: :知前序序列和中序序列能否确定出二叉树知前序序列和中序序列能否确定出二叉树? ? 知中序序列和后序序列能否确定出二叉树知中序序列和后序序列能否确定出二叉树? ? 知前序序列和后序序列能否确定出二叉树知前序序列和后

25、序序列能否确定出二叉树? ? 例题例题:由二叉树的先序序列和中序序列可独一地确定一棵二由二叉树的先序序列和中序序列可独一地确定一棵二叉树。例叉树。例, 先序序列先序序列 ABHFDECKG 和中序序列和中序序列 HBDFAEKCG , 构造二叉树过程如下：构造二叉树过程如下：2 2、(NOIP7)(NOIP7)知一棵二叉树的结点名为大写英文字母，知一棵二叉树的结点名为大写英文字母， 中序：中序：CBGEAFHDIJCBGEAFHDIJ 后序：后序：CGEBHFJIDACGEBHFJIDA 求该二叉树的先序遍历的顺序为多少求该二叉树的先序遍历的顺序为多少? ?1 1、知：先序遍历结果：、知：先序遍历结果：ABCDEFGHABCDEFGH 中序遍历结果：中