计算机软件基础(自考10)ppt课件

计算机软件基础,第二篇数据结构基础,第十章树和二叉树,一、树（tree）,1.树的定义,树：是一个具有n（n0）个节点的有限集合T。满足以下两个条件：,（1）任意一颗树有且仅有一个特定的根节点（rootnode）。,（2）除根节点以外，其余节点可以分为m（m0）个互不相交的子集T1，T2,Tm，其中每个子集本身又是一颗树，称为根的子树。,结论：一棵树由若干子树构成，而每一颗子树由若干颗子子树构成。,一、树（tree）,2.树的表示形式,自然表示法,集合表示法,A,B,C,E,D,F,层次表示法,1A,1.1A,1.2B,1.2.1E,1.2.2F,1.3D,一、树（tree）,3.树的有关名词,（1）节点的度：节点的孩子数。,（2）树的度=树的叉=拥有孩子最多节点的孩子个数,（3）叶子节点=终端节点=没有孩子的节点,（4）双亲节点：指的是这个节点的父亲节点。,（5）树的高度=树的层数,二、二叉树,二叉树：最多具有两个树杈的树。其中，左边的树杈称为该节点的左子树，右边的树杈称为该节点的右子树。,2.二叉树的基本形态：共5种,一个节点也没有,只有一个根节点,只有左子树,只有右子树,左、右子树都有,二、二叉树,3.二叉树与一般树的区别：,二、二叉树,4.二叉树的性质,性质1：二叉树的第i层上最多有2i-1个节点（i1）；,性质2：高度为k的二叉树最多有2k-1个节点（k1）；,性质3：任意一颗二叉树中，如果没有孩子的节点个数为n0，有两个孩子的节点个数为n2，那么n0=n2+1,二、二叉树,5.二叉树的两种特殊情形：,（1）满二叉树：除叶子节点以外，其它节点都有两个孩子，而且叶子节点位于同一层上的二叉树。,满二叉树,（2）完全二叉树：一个满二叉树的最下层，从右向左连续缺少n个节点的二叉树。,完全二叉树,注意：深度为k的满二叉树，有2k-1个节点,二、二叉树,例：（2010.4单选）一个深度为k的完全二叉树中节点数至少有（）。,A2kB2k-1C2k+1D2k-1,二、二叉树,例10-1试写出具有3个节点的所有不同形态的树和二叉树。,二叉树有五种：,树有2种：,二、二叉树,6.二叉树的存储结构顺序存储,操作步骤为：,step1：现将二叉树变成完全二叉树（给有关节点补够两个孩子，所补节点为虚拟节点，仅占个空间）,step2：将这个完全二叉树中各节点从上到下，逐层由左向右一次存放到计算机连续空间中。,二、二叉树,例10-2：,1,2,3,4,5,7,8,9,10,11,12,13,6,a,b,c,d,二、二叉树,例10-3一个深度为K且只有K个节点的二叉树顺序存储最多需要多少个存储空间，最少需要多少个。,二、二叉树,（2）完全二叉树节点顺序编号的意义,二、二叉树,例10-4一个完全二叉树节点个数为1000，则n0、n1、n2和高度h各为多少?,二、二叉树,6.二叉树的存储结构链式存储,（1）二叉树链式存储中，每个节点有3个成员（域）,data,Lchild,Rchild,Lchild存放该节点左孩子的地址；,Rchild存放该节点右孩子的地址；,data存放该节点的数据；,二、二叉树,6.二叉树的存储结构链式存储,（2）二叉树链式存储类型的定义,structnodedatatypedata;structnode*Lchild,*Rchild;,二、二叉树,例10-5,A,A,A,A,三、二叉树的遍历,1.中序遍历,如果二叉树不为空，则依次执行如下操作：,（1）先：中序遍历左子树；,（2）再：访问根节点；,（3）最后：中序遍历右子树。,根,二叉树的遍历：按照一定的顺序访问树中所有节点，而且每个节点仅被访问一次的操作。,三、二叉树的遍历,例：如图所示二叉树，试写出对其中序遍历的结果。,中序遍历结果：,DBGEHACIF,三、二叉树的遍历,中序遍历的算法描述,voidinorde(bitree*root)/root为指向根节点的指针if(root!=null)inorde(root-Lchild);/先遍历左子树printf(%c,root-data);/然后访问根节点inorde(root-Rchild);/最后遍历右子树,三、二叉树的遍历,1.先序遍历,如果二叉树不为空，则依次执行如下操作：,（1）先：访问根节点；,（2）再：先序遍历左子树；,（3）最后：先序遍历右子树。,根,三、二叉树的遍历,例：如图所示二叉树，试写出对其先序遍历的结果。,先序遍历结果：,ABDEGHCFI,三、二叉树的遍历,1.后序遍历,如果二叉树不为空，则依次执行如下操作：,（1）先：后序遍历左子树；,（2）再：后序遍历右子树；,（3）最后：访问根节点。,根,三、二叉树的遍历,例：如图所示二叉树，试写出对其后序遍历的结果。,后序遍历结果：,DGHEBIFCA,三、二叉树的遍历,结论：由先序和中序或后序和中序遍历结果，可以确定唯一的一棵二叉树。,口诀：,先序后序定树根；,中序区分左和右。,三、二叉树的遍历,例：（2010.4）已知二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是。,c,e,d,b,a,cedba,三、二叉树的遍历,例10-7已知二叉树的后序遍历序列和中序遍历序列结果分别是DGHEBIFCA和DBGEHACIF，试确定这个二叉树。,A,C,F,I,B,D,E,G,H,四、树、森林和二叉树,一、树的存储结构,1、双亲静态链表存储法,四、树、森林和二叉树,一、树的存储结构,2、孩子链表存储法,四、树、森林和二叉树,1）树的孩子兄弟表示,口诀：竖线连接左孩子，横线连接亲兄弟。,例：将如图所示树，用树的孩子兄弟表示。,3、孩子兄弟链式存储法,四、树、森林和二叉树,2）用链连接各节点。,3、孩子兄弟链式存储法,A,B,C,D,E,F,存储,date,指向大孩子,指向下一个兄弟,四、树、森林和二叉树,1.树变二叉树,step1:写出树的孩子兄弟表示；,step2:将竖线变成左子树，横向变成右子树。,一、树的存储结构,四、树、森林和二叉树,3.树的遍历,树的遍历有：先序和后序,注意：,树的先序遍历结果与对应二叉树的先序遍历结果相同；,树的后序遍历结果与对应二叉树的中序遍历结果相同。,四、树、森林和二叉树,4.森林变二叉树,step1:把构成森林的每一棵树变成二叉树；,step2:依次把后一棵二叉树连在前一棵二叉树根的右子树上。,四、树、森林和二叉树,4.森林变二叉树（续）,四、树、森林和二叉树,5.森林的遍历,森林的遍历有：先序和后序,注意：,森林的先序遍历结果与对应二叉树的先序遍历结果相同；,森林的后序遍历结果与对应二叉树的中序遍历结果相同。,例.（2010.4解答）已知下图所示的二叉树，要求：,（1）将该二叉树还原成森林；,（2）写出森林的先根遍历序列和后根遍历序列,解（1）将该二叉树还原成森林；,（2）写出森林的先根遍历序列和后根遍历序列,解（1）将该二叉树还原成森林；,解（1）将该二叉树还原成森林；,解（2）先根遍历序列：abdgcefhij,后根遍历序列：bgdaecihjf,五、哈夫曼树及其应用,1.几个基本术语,（1）第i个叶子节点的权值Wi：给第i个节点所赋予的重要程度值；,（2）第i个叶子节点的路径长度Li：从根到第i个节点所经路径的段数；,（3）第i个叶子节点的带权路径长度WPLi：WPLi=WiLi；,（4）树的带权路径长度WPL：等于该树中所有叶子的带权路径长度之和。,五、哈夫曼树及其应用,五、哈夫曼树及其应用,2.哈夫曼树,哈夫曼树：也称为最优二叉树，就是带权路径长度为最小的二叉树。,3.根据已知树，求对应哈夫曼树的方法,step1：将该树的叶子权值由小到大进行排序；,step2：从所排序中取出两个最小的权值和构造二叉树，该二叉树的根节点为W（）,step3：从权值序列中划去和。划去后，如果序列为空，说明所要求的二叉树已经构成；否则，将W加入权值序列中，重复step1step3。,五、哈夫曼树及其应用,例：（09.4月）给定一组权值：4、1、12、2、10，构造对应的哈夫曼树（权值小的为左子树，权值大的为右子树），并求出该树的带权路径长度。,step1：按权值由小到大排序：,1,step2：取两个最小权值，,、,2,、,4,、,10,12,、,3,构建一颗二叉树,1,2,step3：从原序列中划去1和2,将3插入到序列中,3,step3：重复步骤13,4,7,7,10,17,12,17,29,五、哈夫曼树及其应用,4.哈夫曼树的性质,（1）给定权值树所对应的哈夫曼树不是唯一的，但是，该树的带权路径长度WPL肯定是唯一的；,（2）权值越大的节点，距离根节点越近；,（3）哈夫曼树中，不存在只有一个孩子的节点；,（4）哈夫曼树的节点总数n：=2叶子节点个数1。,五、哈夫曼树及其应用,5.哈夫曼编码,（1）定义：长度最小的二进制串电文编码。,（2）求哈夫曼编码的步骤：,step1：构造哈夫曼树（依据：以电文中各字符出现的次数为权值）；,step2：构造哈夫曼编码树（方法：在哈夫曼树左子树的边上添0，右子树的边上添1）；,step3：求各字符的哈夫曼编码（从根到各字符节点路径上的二进制序列）；,五、哈夫曼树及其应用,例：（2008.04）假设字符a，b，c，d，e，f使用的频率分别为0.07，0.09，0.13，0.21，0.23，0.27，构造哈夫曼编码树（权值小的为左子树，权值大的为右子树），并根据哈夫曼编码树写出a，