《计算机统考重难点班讲义(数据结构）-第二讲.ppt》由会员分享，可在线阅读，更多相关《计算机统考重难点班讲义(数据结构）-第二讲.ppt（40页珍藏版）》请在三一文库上搜索。
1、数据结构 重难点串讲,讲师：翔高教育一级培训师 地点：上海,第四章 树与二叉树,重难点导航,二叉树遍历的递归算法（前序、中序和后序）、非递归算法（前序和中序，后序非递归遍历有其特殊性）。遍历是正章的基础和重点。 树以及二叉树的存储结构 二叉树的线索化。二叉树线索化的实质就是建立结点在相应序列中与其前驱和后继之间的联系 树、森林和二叉树之间的转换 哈夫曼树的定义、构造和求哈夫曼编码。,3,二叉树的基本运算 （1） 构造一棵二叉树 CreateBTree ( BT) （2）清空以BT为根的二叉树 ClearBTree(BT) （3）判断二叉树是否为空 BTreeEmpty(BT) （4）获取给定结
2、点的左孩子和右孩子 LeftChild(BT,node)，RightChild(BT,node) （5）获取给定结点的双亲 Parent(BT,node) （6）遍历二叉树Traverse(BT),二叉树的性质 二叉树具有下列5个重要的性质。 【性质1】 在二叉树的第i层上最多有2i-1个结点（i1）。 【性质2】 深度为K的二叉树最多有2K-1个结点（K1）。 【性质3】 对于任意一棵二叉树BT，如果度为0的结点个数为n0，度为2的结点个数为n2，则n0=n2+1。 【性质4】 具有n个结点的完全二叉树的深度为 log2n+1。其中，log2n 的结果是不大于log2n的最大整数。 【性质5
3、】 对于有n个结点的完全二叉树中的所有结点按从上到下，从左到右的顺序进行编号，则对任意一个结点i （1in），都有： （1）如果i=1，则结点i是这棵完全二叉树的根，没有双亲；否则其双亲结点的编号为 i/2。 （2）如果2in，则结点i没有左孩子；否则其左孩子结点的编号为2i。 （3）如果2i+1n，则结点i没有右孩子；否则其右孩子结点的编号为2i+1。,二叉树的存储结构 二叉树也可以采用两种存储方式：顺序存储结构和链式存储结构。 顺序存储结构 这种存储结构适用于完全二叉树。其存储形式为：用一组连续的存储单元按照完全二叉树的每个结点编号的顺序存放结点内容。,链式存储结构 在顺序存储结构中，利用
4、编号表示元素的位置及元素之间孩子或双亲的关系，因此对于非完全二叉树，需要将空缺的位置用特定的符号填补，若空缺结点较多，势必造成空间利用率的下降。在这种情况下，就应该考虑使用链式存储结构。 常见的二叉树结点结构如下所示：,图 5-12,其中，Lchild和Rchild是分别指向该结点左孩子和右孩子的指针，item是数据元素的内容。在C语言中的类型定义为： typedef struct BTNode EntryType item; struct BTNode *Lchild,*Rchlid; BTNode,*BTree; 下面是一棵二叉树及相应的链式存储结构。,遍历二叉树 二叉树是一种非线性的数据
5、结构，在对它进行操作时，总是需要逐一对每个数据元素实施操作，这样就存在一个操作顺序问题，由此提出了二叉树的遍历操作。所谓遍历二叉树就是按某种顺序访问二叉树中的每个结点一次且仅一次的过程。这里的访问可以是输出、比较、更新、查看元素内容等等各种操作。 二叉树的遍历方式分为两大类：一类按根、左子树和右子树三个部分进行访问；另一类按层次访问。下面我们将分别进行讨论。,按根、左子树和右子树三部分进行遍历 遍历二叉树的顺序存在下面6种可能： TLR（根左右）, TRL（根右左） LTR（左根右）, RTL（右根左） LRT（左右根）, RLT（右左根） 其中，TRL、RTL和RLT三种顺序在左右子树之间均
6、是先右子树后左子树，这与人们先左后右的习惯不同，因此，往往不予采用。余下的三种顺序TLR、LTR和LRT根据根访问的位置不同分别被称为先序遍历、中序遍历和后序遍历。,（1）先序遍历 若二叉树为空，则结束遍历操作；否则 访问根结点； 先序遍历左子树； 先序遍历右子树。 （2）中序遍历 若二叉树为空，则结束遍历操作；否则 中序遍历左子树； 访问根结点； 中序遍历右子树。,（3）后序遍历 若二叉树为空，则结束遍历操作；否则 后序遍历左子树； 后序遍历右子树； 访问根结点。 下面是一棵二叉树及其经过三种遍历得到的相应序列。,下面我们再给出两种遍历二叉树的方法： 1）对一棵二叉树中序遍历时，若我们将二叉
7、树严格地按左子树的所有结点位于根结点的左侧，右子树的所有结点位于根右侧的形式绘制，就可以对每个结点做一条垂线，映射到下面的水平线上，由此得到的顺序就是该二叉树的中序遍历序列。,在二叉树的层次遍历算法中，应使用一个队列结构完成这项操作。所谓记录访问结点就是入队操作；而取出记录的结点就是出队操作。这样一来，我们的算法就可以描述成下列形式： （1）访问根结点，并将根结点入队； （2）当队列不空时，重复下列操作： 从队列退出一个结点； 若其有左孩子，则访问左孩子，并将其左孩子入队 若其有右孩子，则访问右孩子，并将其右孩子入队,计算一棵二叉树的叶子结点数目 这个操作可以使用三种遍历顺序中的任何一种，只是
8、需要将访问操作变成判断该结点是否为叶子结点，如果是叶子结点将累加器加1即可。下面这个算法是利用中序遍历实现的。,【算法5-13】 void Leaf(BTree BT,int *count) if (BT) Leaf(BT-child, /计算右子树的叶子结点个数 ,求二叉树的高度 这个操作使用后序遍历比较符合人们求解二叉树高度的思维方式。首先分别求出左右子树的高度，在此基础上得出该棵树的高度，即左右子树较大的高度值加1。 int hight(BTree BT) /h1和h2分别是以BT为根的左右子树的高度 if (BT=NULL) return 0; else h1=hight(BT-lch
9、ild); h2=hight(BT-right); return maxh1,h2+1; ,树、森林与二叉树的转换 树、森林转换成二叉树 将一棵树转换成二叉树的方法： 将一棵树转换成二叉树实际上就是将这棵树用孩子兄弟表示法存储即可，此时，树中的每个结点最多有两个指针：一个指针指向第一个孩子，另一个指针指向右侧第一个兄弟。当你将这两个指针看作是二叉树中的左孩子指针和孩子右指针时，就是一棵二叉树了。,特点：一棵树转换成二叉树后，根结点没有右孩子 将森林转换成二叉树的方法与一棵树转换成二叉树的方法类似，只是把森林中所有树的根结点看作兄弟关系，并对其中的每棵树依依地进行转换。,二叉树还原成树或森林 这
10、个过程实际上是树、森林转换成二叉树的逆过程，即将该二叉树看作是树或森林的孩子兄弟表示法。比如，若二叉树为空，树也为空；否则，由二叉树的根结点开始，延右指针向下走，直到为空，途经的结点个数是相应森林所含树的棵数；若某个结点的左指针非空，说明这个结点在树中必有孩子，并且从二叉树中该结点左指针所指结点开始，延右指针向下走，直到为空，途经的结点个数就是这个结点的孩子数目。,哈夫曼树的定义,路径：从一个结点到另一个结点所经过的分支 路径长度L：路径上分支的数目 树的路径长度PL：根到每个结点的路径长度之和,n结点个数,树的带权路径长度WPL：树中所有叶子带权路径长度之和,n树叶个数,哈夫曼树：由权值为
11、w1,w2,.,wn)的n片叶子构成的所 有二叉树中，WPL值最小的二叉树。 哈夫曼树又被称为最优二叉树,结点的带权路径长度：结点的权值乘结点到根的路径长度wili,Huffman算法思想： 1. 将权值为w1, w2, ., wn的n个叶子构成一个具有n棵树的森林：,2. 从森林F中选取根权值最小的两棵树，分别作为左子树和右子树，再新添一个结点做为根，合并成一棵新的二叉树，新二叉树根的权值等于左、右子树根权值之和。 3. 重复2，直到F中只剩下一棵树为止，这棵树就是所求的Huffman树。,3,7,9,13,22,WPL=(1 + 2 )4 + 43 + (4 + 5 + 6)2=54,构造
12、n个叶子的哈夫曼树需要经过n-1次合并，每次合并都要增加一个新结点。所以n个叶子的哈夫曼树上有且仅有2n-1个结点 哈夫曼树上不存在度为1的结点。我们把这种不存在度为1的结点的二叉树称为严格二叉树或正则二叉树。 n0=n2+1 n=n0 + n1 + n2 = n0 + n2 = n0 + (n0-1) = 2 * n0 - 1,电文“abcdedacafcfadcacfdaef” 字符集 a, b, c, d, e, f ,利用二叉树可以获得前缀码：以字符集中的字符为叶子，构造一棵二叉树; 在左树枝上标0码，右树枝上标1码。从树根到树叶所经历的分支构成了相应叶子字符的前缀码：,由于n个叶子能
13、够构造出很多形态各异的二叉树， 因而会有多种前缀码方案， 取那种呢？ 当然是使得电文比特流为最短的编码方案。,显然，如果ci是权，比特流长度就是二叉树的WPL。 哈夫曼树的WPL是最小的，故用哈夫曼树产生前缀码是最优前缀码，又称为哈夫曼编码。,n字符个数 ci字符在电文中重复出现次数 li串长，根到叶子的路径长度,经典例题分析,【例1】算术表达式a+b*(c+de)转为后缀表达式后为( )。 【中科大 2008】 Aab+cd+e/* Babcde/+*+ Cabcde*+ Dabcde*+ 解 考察表达式二叉树的知识。将算术表达式转化为二叉树，相应的二叉树中以左子树表示第一操作数，右子树表示
14、第二操作数，根结点的数据域存放运算符(若为一元运算符，则左子树为空)。算术表达式a+b*(c+de)对应的二叉树为。 因此本题答案为B,34,【例2】下列线索二叉树中(用虚线表示线索)，符合后序线索树定义的是 【解析】本题考查对线索二叉树的线索的理解。线索二叉树是利用原二叉树中的空指针来反映二叉树的三种遍历的前后关系。题目中的这棵树的后序遍历序列是dbca。所以d无前驱结点，左链域为空，由此排除选项B和C。b的前驱结点为d,所以b的左链域指向结点d，因此排除选项A。因此本题答案为D,35,【例3】在下图所示的平衡二叉树中，插入关键宇48后得到一棵新平衡二叉树。在新平衡二叉树中，关键宇37所在结
15、点的左、右子结点中保存的关键字分别是 A13、48 B24、48 C24、53 D24、90 【解析】本题考查对平衡二叉树的基本操作。插入关键字48后，根结点的平衡因子由-1变成-2，要进行两次旋转操作，具体过程如下图：,36,【例4】在一棵度为4的树T中，若有20个度为4的结点,10个度为3的结点，1个度为2的结点；10个度为1的结点，则树T的叶结点个数是 A41 B82 C113 D122 【解析】本题考查树的基本概念。设树中结点总数为N，度为i(i=0,1,2,3,4)的结点数分别为Ni，树中各结点的度之和等于N-1。则可得： N=N0+N1+2*N2+3*N3+4*N4+1 代入题设中
16、的数据可得N0=82，即树的叶子结点数为82.因此本题答案为B.,37,【例5】对n(n2)个权值均不相同的字符构造哈夫曼树。下列关于该哈夫曼树的叙述中，错误的是 A该树一定是一棵完全二叉树 B树中一定没有度为I的结点 C树中两个权值最小的结点一定是兄弟结点 D树中任一非叶结点的权值二定不小于下一层任一结点的权值 【解析】具有最小带权路径长度的二叉树称为哈夫曼树。根据哈夫曼树的构造过程，树中肯定没有度为1的结点，树中任一非叶结点的权值一定大于下一层任一结点的权值，而且树中的两个权值最小的结点一定是兄弟结点。错的是A，因为这个树不一定是一棵完全二叉树。,38,【例14】编写算法，求二叉树的宽度
17、按层次遍历二叉树，采用一个队列，让根节点如队列，最后出队列，如有左右子树，则左右子树根结点入队列，如此反复，直到为空,39,int Width(BinTree bt) /求二叉树bt的最大宽度 if(bt=NULL) /空二叉树的宽度为0 return 0; Queue Q; /Q为队列，元素为二叉树结点指针 front=rear=last=1; /last 为同层最右结点在队列中的位置。 temp=naxw=0; Qrear=bt; while(frontlchild!=NULL) Q+rear=p-lchild; /左孩子如队列 if(p-rchild!=NULL) Q+rear=p-rchild; /有孩子如队列 if(frontlast) last=rear; if(tempmaxw) maxw=temp; temp=0; ,40,