《计算机统考重难点班讲义(数据结构)-第二讲.ppt》由会员分享，可在线阅读，更多相关《计算机统考重难点班讲义(数据结构)-第二讲.ppt（40页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构数据结构重难点串讲重难点串讲讲师：翔高教育一级培训师地点：上海第四章第四章 树与二叉树树与二叉树重难点导航重难点导航v二叉树遍历的递归算法（前序、中序和后序）、非二叉树遍历的递归算法（前序、中序和后序）、非递归算法（前序和中序，后序非递归遍历有其特殊递归算法（前序和中序，后序非递归遍历有其特殊性）。遍历是正章的基础和重点。性）。遍历是正章的基础和重点。v树以及二叉树的存储结构树以及二叉树的存储结构v二叉树的线索化。二叉树线索化的实质就是建立结二叉树的线索化。二叉树线索化的实质就是建立结点在相应序列中与其前驱和后继之间的联系点在相应序列中与其前驱和后继之间的联系v树、森林和二叉树之间的转
2、换树、森林和二叉树之间的转换v哈夫曼树的定义、构造和求哈夫曼编码。哈夫曼树的定义、构造和求哈夫曼编码。3二叉树的基本运算v（1 1）构造一棵二叉树构造一棵二叉树 CreateBTree(BT)CreateBTree(BT)v（2 2）清空以）清空以BTBT为根的二叉树为根的二叉树 ClearBTree(BT)ClearBTree(BT)v（3 3）判断二叉树是否为空）判断二叉树是否为空 BTreeEmpty(BT)BTreeEmpty(BT)v（4 4）获取给定结点的左孩子和右孩子）获取给定结点的左孩子和右孩子 LeftChild(BT,node)LeftChild(BT,node)，Righ
3、tChild(BT,node)RightChild(BT,node)v（5 5）获取给定结点的双亲）获取给定结点的双亲 Parent(BT,node)Parent(BT,node)v（6 6）遍历二叉树）遍历二叉树Traverse(BT)Traverse(BT)二叉树的性质v二叉树具有下列二叉树具有下列5 5个重要的性质。个重要的性质。v【性质性质1 1】在二叉树的第在二叉树的第i i层上最多有层上最多有2 2i-1i-1个结点（个结点（i i1 1）。）。v【性质性质2 2】深度为深度为K K的二叉树最多有的二叉树最多有2 2K K-1-1个结点（个结点（K K1 1）。）。v【性质性质3
4、3】对于任意一棵二叉树对于任意一棵二叉树BTBT，如果度为，如果度为0 0的结点个数为的结点个数为n n0 0，度，度为为2 2的结点个数为的结点个数为n n2 2，则，则n n0 0=n=n2 2+1+1。v【性质性质4 4】具有具有n n个结点的完全二叉树的深度为个结点的完全二叉树的深度为 loglog2 2n n+1+1。其中，。其中，loglog2 2n n 的结果是不大于的结果是不大于loglog2 2n n的最大整数。的最大整数。v【性质性质5 5】对于有对于有n n个结点的完全二叉树中的所有结点按从上到下，个结点的完全二叉树中的所有结点按从上到下，从左到右的顺序进行编号，则对任意
5、一个结点从左到右的顺序进行编号，则对任意一个结点i i（1in1in），都有：），都有：v（1 1）如果）如果i=1i=1，则结点，则结点i i是这棵完全二叉树的根，没有双亲；否则其是这棵完全二叉树的根，没有双亲；否则其双亲结点的编号为双亲结点的编号为 i/2i/2。v（2 2）如果）如果2in2in，则结点，则结点i i没有左孩子；否则其左孩子结点的编号为没有左孩子；否则其左孩子结点的编号为2i2i。v（3 3）如果）如果2i+1n2i+1n，则结点，则结点i i没有右孩子；否则其右孩子结点的编号没有右孩子；否则其右孩子结点的编号为为2i+12i+1。二叉树的存储结构v二叉树也可以采用两种存
6、储方式：顺序存储结构和链二叉树也可以采用两种存储方式：顺序存储结构和链式存储结构。式存储结构。v顺序存储结构顺序存储结构v这种存储结构适用于完全二叉树。其存储形式为：用这种存储结构适用于完全二叉树。其存储形式为：用一组连续的存储单元按照完全二叉树的每个结点编号一组连续的存储单元按照完全二叉树的每个结点编号的顺序存放结点内容。的顺序存放结点内容。链式存储结构v在顺序存储结构中，利用编号表示元素的位置及元素在顺序存储结构中，利用编号表示元素的位置及元素之间孩子或双亲的关系，因此对于非完全二叉树，需之间孩子或双亲的关系，因此对于非完全二叉树，需要将空缺的位置用特定的符号填补，若空缺结点较多，要将空缺
7、的位置用特定的符号填补，若空缺结点较多，势必造成空间利用率的下降。在这种情况下，就应该势必造成空间利用率的下降。在这种情况下，就应该考虑使用链式存储结构。考虑使用链式存储结构。v常见的二叉树结点结构如下所示：常见的二叉树结点结构如下所示：图图 5-12v其中，其中，LchildLchild和和RchildRchild是分别指向该结点左孩子和右是分别指向该结点左孩子和右孩子的指针，孩子的指针，itemitem是数据元素的内容。在是数据元素的内容。在C C语言中的语言中的类型定义为：类型定义为：vtypedef struct BTNodetypedef struct BTNodevEntryTyp
8、e item;EntryType item;vstruct BTNode*Lchild,*Rchlid;struct BTNode*Lchild,*Rchlid;vBTNode,*BTree;BTNode,*BTree;v 下面是一棵二叉树及相应的链式存储结构。下面是一棵二叉树及相应的链式存储结构。遍历二叉树v二叉树是一种非线性的数据结构，在对它进行操作时，二叉树是一种非线性的数据结构，在对它进行操作时，总是需要逐一对每个数据元素实施操作，这样就存在总是需要逐一对每个数据元素实施操作，这样就存在一个操作顺序问题，由此提出了二叉树的遍历操作。一个操作顺序问题，由此提出了二叉树的遍历操作。所谓遍历
9、二叉树就是按某种顺序访问二叉树中的每个所谓遍历二叉树就是按某种顺序访问二叉树中的每个结点一次且仅一次的过程。这里的访问可以是输出、结点一次且仅一次的过程。这里的访问可以是输出、比较、更新、查看元素内容等等各种操作。比较、更新、查看元素内容等等各种操作。v二叉树的遍历方式分为两大类：一类按根、左子树和二叉树的遍历方式分为两大类：一类按根、左子树和右子树三个部分进行访问；另一类按层次访问。下面右子树三个部分进行访问；另一类按层次访问。下面我们将分别进行讨论。我们将分别进行讨论。按根、左子树和右子树三部分进行遍历v遍历二叉树的顺序存在下面遍历二叉树的顺序存在下面6 6种可能：种可能：vTLRTLR（
10、根左右）（根左右）,TRL,TRL（根右左）（根右左）vLTRLTR（左根右）（左根右）,RTL,RTL（右根左）（右根左）vLRTLRT（左右根）（左右根）,RLT,RLT（右左根）（右左根）v其中，其中，TRLTRL、RTLRTL和和RLTRLT三种顺序在左右子树之间均三种顺序在左右子树之间均是先右子树后左子树，这与人们先左后右的习惯不同，是先右子树后左子树，这与人们先左后右的习惯不同，因此，往往不予采用。余下的三种顺序因此，往往不予采用。余下的三种顺序TLRTLR、LTRLTR和和LRTLRT根据根访问的位置不同分别被称为先序遍历、中根据根访问的位置不同分别被称为先序遍历、中序遍历和后序
11、遍历。序遍历和后序遍历。v（1 1）先序遍历）先序遍历v若二叉树为空，则结束遍历操作；否则若二叉树为空，则结束遍历操作；否则v访问根结点；访问根结点；v先序遍历左子树；先序遍历左子树；v先序遍历右子树。先序遍历右子树。v（2 2）中序遍历）中序遍历v若二叉树为空，则结束遍历操作；否则若二叉树为空，则结束遍历操作；否则v中序遍历左子树；中序遍历左子树；v访问根结点；访问根结点；v中序遍历右子树。中序遍历右子树。v（3 3）后序遍历）后序遍历v若二叉树为空，则结束遍历操作；否则若二叉树为空，则结束遍历操作；否则v后序遍历左子树；后序遍历左子树；v后序遍历右子树；后序遍历右子树；v访问根结点。访问根
12、结点。v下面是一棵二叉树及其经过三种遍历得到的相应序列。下面是一棵二叉树及其经过三种遍历得到的相应序列。v下面我们再给出两种遍历二叉树的方法：下面我们再给出两种遍历二叉树的方法：v1 1）对一棵二叉树中序遍历时，若我们将二叉树严格）对一棵二叉树中序遍历时，若我们将二叉树严格地按左子树的所有结点位于根结点的左侧，右子树的地按左子树的所有结点位于根结点的左侧，右子树的所有结点位于根右侧的形式绘制，就可以对每个结点所有结点位于根右侧的形式绘制，就可以对每个结点做一条垂线，映射到下面的水平线上，由此得到的顺做一条垂线，映射到下面的水平线上，由此得到的顺序就是该二叉树的中序遍历序列。序就是该二叉树的中序
13、遍历序列。v在二叉树的层次遍历算法中，应使用一个队列结构完在二叉树的层次遍历算法中，应使用一个队列结构完成这项操作。所谓记录访问结点就是入队操作；而取成这项操作。所谓记录访问结点就是入队操作；而取出记录的结点就是出队操作。这样一来，我们的算法出记录的结点就是出队操作。这样一来，我们的算法就可以描述成下列形式：就可以描述成下列形式：v（1 1）访问根结点，并将根结点入队；）访问根结点，并将根结点入队；v（2 2）当队列不空时，重复下列操作：）当队列不空时，重复下列操作：l从队列退出一个结点；从队列退出一个结点；l若其有左孩子，则访问左孩子，并将其左孩子入队若其有左孩子，则访问左孩子，并将其左孩子
14、入队l若其有右孩子，则访问右孩子，并将其右孩子入队若其有右孩子，则访问右孩子，并将其右孩子入队计算一棵二叉树的叶子结点数目v这个操作可以使用三种遍历顺序中的任何一种，只是这个操作可以使用三种遍历顺序中的任何一种，只是需要将访问操作变成判断该结点是否为叶子结点，如需要将访问操作变成判断该结点是否为叶子结点，如果是叶子结点将累加器加果是叶子结点将累加器加1 1即可。下面这个算法是利即可。下面这个算法是利用中序遍历实现的。用中序遍历实现的。v【算法算法5-135-13】vvoid Leaf(BTree BT,int*count)void Leaf(BTree BT,int*count)v v if(
15、BT)if(BT)v Leaf(BT-child,&count);Leaf(BT-child,&count);v /计算左子树的叶子结点个数计算左子树的叶子结点个数 v if(BT-lchild=NULL&BT-if(BT-lchild=NULL&BT-rchild=NULL)(*count)+;rchild=NULL)(*count)+;v Leaf(BT-rchild,&count);Leaf(BT-rchild,&count);v /计算右子树的叶子结点个数计算右子树的叶子结点个数v v 求二叉树的高度v这个操作使用后序遍历比较符合人们求解二叉树高度的思维这个操作使用后序遍历比较符合人们
16、求解二叉树高度的思维方式。首先分别求出左右子树的高度，在此基础上得出该棵方式。首先分别求出左右子树的高度，在此基础上得出该棵树的高度，即左右子树较大的高度值加树的高度，即左右子树较大的高度值加1 1。vint hight(BTree BT)int hight(BTree BT)v/h1/h1和和h2h2分别是以分别是以BTBT为根的左右子树的高度为根的左右子树的高度v if(BT=NULL)return 0;if(BT=NULL)return 0;v else else v h1=hight(BT-lchild);h1=hight(BT-lchild);v h2=hight(BT-right)
17、;h2=hight(BT-right);v return maxh1,h2+1;return maxh1,h2+1;v v 树、森林与二叉树的转换树、森林转换成二叉树v将一棵树转换成二叉树的方法：将一棵树转换成二叉树的方法：v将一棵树转换成二叉树实际上就是将这棵树用孩子兄将一棵树转换成二叉树实际上就是将这棵树用孩子兄弟表示法存储即可，此时，树中的每个结点最多有两弟表示法存储即可，此时，树中的每个结点最多有两个指针：一个指针指向第一个孩子，另一个指针指向个指针：一个指针指向第一个孩子，另一个指针指向右侧第一个兄弟。当你将这两个指针看作是二叉树中右侧第一个兄弟。当你将这两个指针看作是二叉树中的左孩
18、子指针和孩子右指针时，就是一棵二叉树了。的左孩子指针和孩子右指针时，就是一棵二叉树了。v特点：一棵树转换成二叉树后，根结点没有右孩子特点：一棵树转换成二叉树后，根结点没有右孩子v将森林转换成二叉树的方法与一棵树转换成二叉树的将森林转换成二叉树的方法与一棵树转换成二叉树的方法类似，只是把森林中所有树的根结点看作兄弟关方法类似，只是把森林中所有树的根结点看作兄弟关系，并对其中的每棵树依依地进行转换。系，并对其中的每棵树依依地进行转换。二叉树还原成树或森林v这个过程实际上是树、森林转换成二叉树的逆过程，这个过程实际上是树、森林转换成二叉树的逆过程，即将该二叉树看作是树或森林的孩子兄弟表示法。比即将该
19、二叉树看作是树或森林的孩子兄弟表示法。比如，若二叉树为空，树也为空；否则，由二叉树的根如，若二叉树为空，树也为空；否则，由二叉树的根结点开始，延右指针向下走，直到为空，途经的结点结点开始，延右指针向下走，直到为空，途经的结点个数是相应森林所含树的棵数；若某个结点的左指针个数是相应森林所含树的棵数；若某个结点的左指针非空，说明这个结点在树中必有孩子，并且从二叉树非空，说明这个结点在树中必有孩子，并且从二叉树中该结点左指针所指结点开始，延右指针向下走，直中该结点左指针所指结点开始，延右指针向下走，直到为空，途经的结点个数就是这个结点的孩子数目。到为空，途经的结点个数就是这个结点的孩子数目。哈夫曼树
20、的定义哈夫曼树的定义路径：路径：从一个结点到另一个结点所经过的分支从一个结点到另一个结点所经过的分支路径长度路径长度L：路径上分支的数目路径上分支的数目树的路径长度树的路径长度PL：根到每个结点的路径长度之和根到每个结点的路径长度之和 n结点个数EFDCBAEFCBADh=3,PL=0+1+1+2+2+2=8h=5,PL=0+1+2+3+4+4=13 树的带权路径长度WPL：树中所有叶子叶子带权路径长度之和n树叶个数 哈夫曼树：由权值为 w1,w2,.,wn)的n片叶子构成的所 有二叉树中，WPL值最小的二叉树。哈夫曼树又被称为最优二叉树 结点的带权路径长度：结点的权值乘结点到根的路径长度wi
21、liHuffman算法思想：1.将权值为将权值为ww1 1,w,w2 2,.,w,.,wn n的的n n个叶子构成一个具有个叶子构成一个具有n n棵树的森林：棵树的森林：2.从森林从森林F F中选取根权值最小的两棵树，分别作为左子树和右子树，再中选取根权值最小的两棵树，分别作为左子树和右子树，再新添一个结点做为根，合并成一棵新的二叉树，新二叉树根的权值等于新添一个结点做为根，合并成一棵新的二叉树，新二叉树根的权值等于左、右子树根权值之和。左、右子树根权值之和。3.重复重复2 2，直到，直到F F中只剩下一棵树为止，这棵树就是所求的中只剩下一棵树为止，这棵树就是所求的HuffmanHuffman
22、树。树。w1w2w3wnFa6b1f4c5d4e2e2b13a6f4c5d4d4e2b13e2b137a6f4c5d4e2b137c5f49a6a6d4e2b13713c5f49d4e2b137c5f49a613d4e2b13722a613d4e2b137c5f49c5f4922a613d4e2b137WPL=(1+2)4+43+(4+5+6)2=54哈夫曼树及其应用哈夫曼树及其应用 哈夫曼树的构造哈夫曼树的构造8 构造n个叶子的哈夫曼树需要经过n-1次合并，每次合并都要增加一个新结点。所以n个叶子的哈夫曼树上有且仅有2n-1个个结点8 哈夫曼树上不存在度为1的结点。我们把这种不存在度为1的结
23、点的二叉树称为严格二叉树严格二叉树或正则正则二叉树二叉树。n0=n2+1 n=n0+n1+n2=n0+n2=n0+(n0-1)=2*n0-1 电文“abcdedacafcfadcacfdaef”字符集 a,b,c,d,e,f 利用二叉树可以获得前缀码：利用二叉树可以获得前缀码：以字符集中的字符为叶子，构造一棵二叉树;在左树枝上标0码，右树枝上标1码。从树根到树叶所经历的分支构成了相应叶子字符的前缀码：cfadeb0100111001a:10b:1100c:01d:111e:1101 f:00由于n个叶子能够构造出很多形态各异的二叉树，因而会有多种前缀码方案，取那种呢？当然是使得电文比特流为最短
24、的编码方案。cfadeb0100111001a:10b:1100c:01d:111e:1101 f:008显然，如果ci是权，比特流长度就是二叉树的WPL。8哈夫曼树的WPL是最小的，故用哈夫曼树产生前缀码是最优前缀码最优前缀码，又称为哈夫曼编码哈夫曼编码。n n字符个数字符个数ci ci字符在电文中重复出现次数字符在电文中重复出现次数li li串长，根到叶子的路径长度串长，根到叶子的路径长度经典例题分析经典例题分析v【例例1 1】算术表达式算术表达式a+b*(c+da+b*(c+de)e)转为后缀表达转为后缀表达式后为式后为()()。【中科大中科大 20082008】A Aab+cd+e/*
25、Bab+cd+e/*Babcde/+*+abcde/+*+C Cabcdeabcde*+D+Dabcde*abcde*+v解解 考察表达式二叉树的知识。将算术表达式转化考察表达式二叉树的知识。将算术表达式转化为二叉树，相应的二叉树中以左子树表示第一操作为二叉树，相应的二叉树中以左子树表示第一操作数，右子树表示第二操作数，根结点的数据域存放数，右子树表示第二操作数，根结点的数据域存放运算符运算符(若为一元运算符，则左子树为空若为一元运算符，则左子树为空)。算术表。算术表达式达式a+b*(c+da+b*(c+de)e)对应的二叉树为。对应的二叉树为。因此本题答案为因此本题答案为B B34v【例例2
26、 2】下列线索二叉树中下列线索二叉树中(用虚线表示线索用虚线表示线索)，符合，符合后序线索树定义的是后序线索树定义的是v【解析解析】本题考查对线索二叉树的线索的理解。线本题考查对线索二叉树的线索的理解。线索二叉树是利用原二叉树中的空指针来反映二叉树索二叉树是利用原二叉树中的空指针来反映二叉树的三种遍历的前后关系。题目中的这棵树的后序遍的三种遍历的前后关系。题目中的这棵树的后序遍历序列是历序列是dbcadbca。所以。所以d d无前驱结点，左链域为空，无前驱结点，左链域为空，由此排除选项由此排除选项B B和和C C。b b的前驱结点为的前驱结点为d,d,所以所以b b的左的左链域指向结点链域指向
27、结点d d，因此排除选项，因此排除选项A A。因此本题答案为。因此本题答案为D D35v【例例3 3】在下图所示的平衡二叉树中，插入关键宇在下图所示的平衡二叉树中，插入关键宇4848后得到一棵新平衡二叉树。在新平衡二叉树中，后得到一棵新平衡二叉树。在新平衡二叉树中，关键宇关键宇3737所在结点的左、右子结点中保存的关键字所在结点的左、右子结点中保存的关键字分别是分别是 A A1313、48 B48 B2424、48 48 C C2424、53 D53 D2424、9090 【解析解析】本题考查对平衡二叉树的基本操作。插入关本题考查对平衡二叉树的基本操作。插入关键字键字4848后，根结点的平衡因
28、子由后，根结点的平衡因子由-1-1变成变成-2-2，要进行，要进行两次旋转操作，具体过程如下图：两次旋转操作，具体过程如下图：36v【例例4 4】在一棵度为在一棵度为4 4的树的树T T中，若有中，若有2020个度为个度为4 4的的结点结点,10,10个度为个度为3 3的结点，的结点，1 1个度为个度为2 2的结点；的结点；1010个个度为度为1 1的结点，则树的结点，则树T T的叶结点个数是的叶结点个数是vA A41 B41 B82 C82 C113 D113 D122122v【解析解析】本题考查树的基本概念。设树中结点总数本题考查树的基本概念。设树中结点总数为为N N，度为，度为i(i=0
29、,1,2,3,4)i(i=0,1,2,3,4)的结点数分别为的结点数分别为NiNi，树，树中各结点的度之和等于中各结点的度之和等于N-1N-1。则可得：。则可得：vN=NN=N0 0+N+N1 1+2*N+2*N2 2+3*N+3*N3 3+4*N+4*N4 4+1+1v代入题设中的数据可得代入题设中的数据可得N N0 0=82=82，即树的叶子结点数，即树的叶子结点数为为82.82.因此本题答案为因此本题答案为B.B.37v【例例5 5】对对n n(n n2)2)个权值均不相同的字符构造哈夫个权值均不相同的字符构造哈夫曼树。下列关于该哈夫曼树的叙述中，错误的是曼树。下列关于该哈夫曼树的叙述中
30、，错误的是vA A该树一定是一棵完全二叉树该树一定是一棵完全二叉树 vB B树中一定没有度为树中一定没有度为I I的结点的结点vC C树中两个权值最小的结点一定是兄弟结点树中两个权值最小的结点一定是兄弟结点vD D树中任一非叶结点的权值二定不小于下一层任树中任一非叶结点的权值二定不小于下一层任一结点的权值一结点的权值v【解析解析】具有最小带权路径长度的二叉树称为哈夫具有最小带权路径长度的二叉树称为哈夫曼树。根据哈夫曼树的构造过程，树中肯定没有度曼树。根据哈夫曼树的构造过程，树中肯定没有度为为1 1的结点，树中任一非叶结点的权值一定大于下的结点，树中任一非叶结点的权值一定大于下一层任一结点的权值
31、，而且树中的两个权值最小的一层任一结点的权值，而且树中的两个权值最小的结点一定是兄弟结点。错的是结点一定是兄弟结点。错的是A A，因为这个树不一，因为这个树不一定是一棵完全二叉树。定是一棵完全二叉树。38v【例例1414】编写算法，求二叉树的宽度编写算法，求二叉树的宽度v按层次遍历二叉树，采用一个队列，让根节点如队按层次遍历二叉树，采用一个队列，让根节点如队列，最后出队列，如有左右子树，则左右子树根结列，最后出队列，如有左右子树，则左右子树根结点入队列，如此反复，直到为空点入队列，如此反复，直到为空391.1.intint Width(BinTreeWidth(BinTree btbt)2.2
32、./求二叉树求二叉树btbt的最大宽度的最大宽度3.3.if(btif(bt=NULL)/=NULL)/空二叉树的宽度为空二叉树的宽度为0 04.4.return 0;return 0;5.5.Queue Q;/QQueue Q;/Q为队列，元素为二叉树结点指针为队列，元素为二叉树结点指针6.6.front=rear=last=1;/last front=rear=last=1;/last 为同层最右结点在队列中的位置。为同层最右结点在队列中的位置。7.7.temp=temp=naxwnaxw=0;=0;8.8.QrearQrear=btbt;9.9.while(frontwhile(fron
33、t=last)-lchildlchild!=NULL)!=NULL)13.13.Q+rearQ+rear=p-=p-lchildlchild;/;/左孩子如队列左孩子如队列14.14.if(pif(p-rchildrchild!=NULL)!=NULL)15.15.Q+rearQ+rear=p-=p-rchildrchild;/;/有孩子如队列有孩子如队列16.16.if(frontif(frontlast)last)17.17.last=rear;last=rear;18.18.if(tempif(tempmaxwmaxw)maxwmaxw=temp;=temp;19.19.temp=0;temp=0;20.20.21.21.22.22.40