数据结构与算法 课件 第五章树与二叉树

全国高等教育自学考试指定教材

计算机及应用专业（本科段）数据结构与算法第五章树与二叉树学习目标理解树及二叉树的基本概念，掌握二叉树的基本性质掌握树及二叉树的存储方式能够实现树及二叉树的基本操作及遍历算法掌握堆的概念及基本操作的实现。理解优先队列的概念理解递归的概念，能够实现递归程序掌握树、森林与二叉树之间的相互转换掌握哈夫曼树及哈夫曼编码的概念，能够构造哈夫曼树并设计哈夫曼编码本章主要内容树的基本概念12二叉树的操作3二叉树树和森林5哈夫曼树及哈夫曼编码6堆及优先队列4第一节树的基本概念树是一种层次结构，是一种非线性结构日常生活中，经常会遇到具有层次关系的示例家族中部分成员的辈份关系树的定义定义5-1一棵树（tree）T是由一个或一个以上的结点组成的有限集，其中有一个特定的结点R称为树T的根结点。在集合中除根结点R外，其余的结点可划分为k(k≥0)个不相交的子集T1,T2,…,Tk，其中每个子集都是树，并且其相应的根结点R1,R2,…,Rk是R的孩子结点，R称为Ri(1≤i≤k)的双亲结点，Ri(1≤i≤k)互称为兄弟结点。子集Ti(1≤i≤k)称为根R的子树（subtree）树的结点集合至少包含一个结点只含有一个结点的树是只有根结点的树，也就是单结点树对于多结点的树，必须有一个结点是根结点之间通过边来连接，边也称为分支。含n个结点的树有且仅有n-1条边，这是树的重要特性之一根结点的各子树之间不会有重叠树是一种层次结构，也是递归形式的含有A,B,C,D,E,F,G,H,I,J共10个结点的树TA为根结点，{B,E,F}，{C,G}和{D,H,I,J}构成根结点A的三棵子树，B,C,D分别是这三棵子树的根树中每个结点拥有的子树的个数称为结点的度结点的度即为其子结点的个数树中结点的度的最大值称为树的度度为0的结点称为叶结点，或终端结点度不为0的结点称为分支结点如果树中每个结点的孩子结点之间规定了次序，则树称为有序树具有同一双亲结点的结点是兄弟结点从任一结点到根结点之间所经过的所有结点称为该结点的祖先结点以任一结点为根的子树中的所有结点称为该结点的后代将线性结构中的前驱和后继概念引申至树中，将某结点的双亲结点看作是它的前驱，它的孩子结点看作是它的后继除根结点外，每个结点均只有一个前驱结点根的前驱结点个数为0，除叶结点外，每个结点都有若干个后继结点叶结点的后继结点个数为0树中每个元素的前驱的个数不会多于1个，后继的个数可以是任意个树是一种层次结构，设根为0层，根的孩子结点为1层，依此类推一般地，若某个结点位于i（i≥0）层，则它的孩子结点位于i+1层树中结点的最大层数定义为树的深度最大层数加1为树的高度树中从某一结点出发，到达另一个结点之间所经过的边组成一条路径路径中所含的边数为路径长度虽然树的路径定义中并没有限制路径的方向，但路径通常是沿一个方向延伸的，即从某一结点向根的方向延伸，或是从某一结点向叶结点方向延伸通常，以组成路径的结点序列来表示该条路径m（m≥0）棵互不相交的树构成森林对树中每个结点来说，其子树的集合即为森林第二节二叉树定义5-2二叉树（binarytree）是结点的一个有限集合，这个集合或者为空，或者是由一个根结点以及两棵互不相交的、分别称为这个根的左子树和右子树的二叉树组成。左子树和右子树的根分别称为此二叉树根结点的左孩子结点和右孩子结点二叉树的左子树和右子树都可以存在或者为空，不同的存在状态可以组合出5种基本形态一棵高度为h的二叉树若有2h-1个结点，则二叉树称为满二叉树从形式上来看，满二叉树中除叶结点外，每个结点都有两个孩子结点，即除最后一层外，每一层的结点都是“满”的满二叉树中的n个结点进行连续编号，从编号为0的结点开始，由连续编号的任意多个结点组成的二叉树称为完全二叉树特殊二叉树满二叉树和完全二叉树完全二叉树的特性

二叉树的性质性质1在二叉树的i层上最多有2i个结点(i≥0)证明：使用数学归纳法证明

归纳基础：

对于非空的二叉树T，根在0层，本层只有20=1个结点，结论成立

归纳假设：

设二叉树T中i-1层最多有2i-1个结点，考虑i层，由于i层的结点均为i-1层结点的孩子结点，而二叉树中每个结点最多有两个孩子结点，故i层最多有2

2i-1=2i个结点

根据归纳法原理，性质1得证

性质3对任何非空二叉树T，设n0是叶结点的个数，n2是度为2的结点的个数，则有n0=n2+1证明：设二叉树T中度为1的结点个数为n1，则T中结点总数n为 n=n0+n1+n2 n-1=2

n2+1

n1+0

n0

将上两式联立求解，得到 n0=n2+1

例5-3一棵二叉树共有20个结点，其中叶结点为5个，则度为l的结点个数是（）。A．11B．9C．6D．4答案为A二叉树的存储——顺序存储结构对于完全二叉树，各层自上至下，同层间自左至右，将结点依次存入数组从前至后的各个元素中。按照前面使用过的编号方法，一般来讲，编号为i的结点存放在数组中下标为i的位置使用这样的存储规则可以很方便地找到二叉树中的相关结点，即若知道二叉树某一结点保存在数组中下标i的位置，则可以很方便地求出它的双亲结点（若存在）和左、右孩子结点（若存在）在数组中的位置对于一般的二叉树，顺序存储的思想是，针对二叉树中的每个位置，不论这个位置有没有结点，都在数组中预留保存空间。采用这种存储方式保存完全二叉树时，既不浪费空间，又便于有关操作的实现例5-4设高度为k（k≥1）的二叉树T采用顺序存储结构保存在数组B[2k-1]中，在没有保存T中元素的数组位置中，保存一个区别于T中元素的特殊标记。B中保存的特殊标记个数最多为（）。A．k-1B．2k-1C．2k-k-1D．2k-1答案为C链式存储结构定义一个结点结构：它含有两个指针域，一个指针用来指向该结点左孩子所在的结点，称为左孩子指针，简称为左指针；另一个指针用来指向该结点右孩子所在的结点，称为右孩子指针，简称为右指针。此外，还定义一个用来保存结点中数据的数据域二叉链表表示二叉树结点类的定义及二叉树的定义二叉链表中结点类的定义及二叉树的定义typedefintELEMType;typedefstructBNode //二叉树结点{ ELEMTypedata; //数据域 structBNode*left,*right;

//指向左孩子、右孩子的指针}BinTNode;typedefBinTNode*BTree; //二叉树二叉链表中到底有多少空指针域呢设二叉树中有n个结点，每个结点都含有两个指针域，则二叉链表中共有2

n个指针域已知含n个结点的树中仅含有n-1个分支，即只有n-1个指针域不为空，则其余的n+1个指针域均为空可以看出，二叉链表中有超过一半的指针域都是空的，这些都是结构性开销第三节二叉树的操作二叉树的生成按照二叉树的顺序存储方式，将二叉树各结点值保存在一维数组中，然后建立二叉链表如要建立如下的二叉链表输入的数组是inta[]={0,1,2,3,4,NA,5,NA,NA,NA,NA,NA,NA,6};函数CreateBinaryTree递归处理二叉链表的生成调用它的主程序中先创建一个根结点，其中保存数组首元素的值，该结点作为参数传递给函数CreateBinaryTree。这个结点的位置是下标0，将这个位置值也作为参数传给函数CreateBinaryTree主程序中BTreeroot;root=(BTree)malloc(sizeof(BinTNode));root->data=a[0];root->left=NULL;root->right=NULL;调用函数CreateBinaryTree。参数0是起始位置CreateBinaryTree(0,n,a,root);生成二叉链表如果下标i处的结点有左孩子，则其应该保存在下标2

i+1处如果有右孩子，则应该保存在下标2

i+2处故在函数内，判断数组中位置2

i+1及位置2

i+2处是否保存了元素值如果确实有值，则分配空间创建结点且保存数组中相应位置的元素值，并让下标i处结点的相应指针指向新创建的结点然后再以2

i+1或2

i+2为参数值，递归调用函数，去处理2

i+1或2

i+2位置处结点的左孩子和右孩子如果数组中数据的存储是正确的，则能正确建立二叉链表。如果位置2

i+1或位置2

i+2处没有保存元素值，则递归结束二叉树的遍历对非空的二叉树的遍历可以相应地分解为三项“子任务”访问根结点遍历左子树（即依相应的规律访问左子树中的全部结点）遍历右子树（即依相应的规律访问右子树中的全部结点）常规的3种遍历算法分别是先序遍历、中序遍历和后序遍历。这3种遍历也分别称为先根遍历、中根遍历和后根遍历先序遍历算法若二叉树为空，则返回；否则依次执行以下操作（1）访问根结点（2）先序遍历左子树（3）先序遍历右子树中序遍历算法若二叉树为空，则返回；否则依次执行以下操作（1）中序遍历左子树（2）访问根结点（3）中序遍历右子树后序遍历算法若二叉树为空，则返回；否则依次执行以下操作（1）后序遍历左子树（2）后序遍历右子树（3）访问根结点先序遍历过程中序遍历过程后序遍历过程例5-6写出其先序、中序及后序遍历序列先序遍历序列为A,B,D,G,H,J,K,E中序遍历序列为G,D,J,H,K,B,E,A后序遍历序列为G,J,K,H,D,E,B,A先序遍历算法先序遍历算法中序遍历算法中序遍历算法后序遍历算法后序遍历算法给出二叉树的先序遍历序列和中序遍历序列，能唯一确定该二叉树给出二叉树的后序遍历序列和中序遍历序列，能唯一确定该二叉树例5-7设二叉树T的先序遍历序列是A,B,D,G,H,J,K,E，中序遍历序列是G,D,J,H,K,B,E,A，画出二叉树T由先序遍历序列可知，T的根是A在中序遍历序列中查找A的位置，位于A前面的是其左子树的中序遍历序列，位于A后面的是其右子树的中序遍历序列从而将原问题的求解（对整棵树的还原）分解为两个更小问题的求解（对两棵子树的还原）例5-8统计以二叉链表表示的二叉树T中叶结点的个数T中叶结点的个数等于根左子树中叶结点的个数加上根右子树中叶结点的个数。所以如果递归调用已经得到了两棵子树中叶结点的个数，那么将结果相加即求解例5-9编写程序，返回二叉树T的高度仍是使用递归的思想去编写程序。如果左子树的高度和右子树的高度都已经知道，则二叉树T的高度就可求得，树的高度是两棵子树中较高者的高度再加1层序遍历所谓按层遍历，即是从根结点开始逐层向下遍历，直到最后一层对于同一层的结点，由左到右遍历各结点同一层中的结点相继被访问，同时，它们之间的相对次序也决定着它们孩子结点的相对次序。即同一层中的结点u和结点v，若先遍历u再遍历v，则u的孩子结点的遍历也早于v的孩子结点的遍历按层进行遍历先访问最上面一层即0层中的元素，输出1然后依次访问1的子结点2和3再继续访问2的子结点和3的子结点依此类推，得到的层序遍历结果是：1,2,3,4,5,6,7层序遍历算法二叉树层序遍历的算法遍历的非递归实现仍然将一棵二叉树分为三部分：根、左子树和右子树。从根开始遍历二叉树时，根的左子树和右子树的遍历不能同时进行，只能先遍历一棵子树，同时保存二叉树中尚不能遍历部分的信息，留待一棵子树处理完毕后再处理分析二叉树的遍历过程可知，使用栈来保存相关信息先序遍历算法在进入左子树进行处理之前，需要在栈中保存右子树的相关信息，以便当左子树处理完毕，能够根据保存的线索找到右子树的根。所以，栈中保存右子树的根即可程序中序遍历算法中序遍历时，先进行左子树的遍历，然后遍历根，再遍历右子树。所以栈中保存根的信息，遍历完左子树后，从栈中找到根，访问根，同时也能容易地找到右子树程序后序遍历算法类似于中序遍历过程，在进入左子树遍历之前，需要先保存根的信息。当左子树遍历结束，从栈中找到根，但此时因为右子树尚未遍历，所以根并不能从栈中弹出，仍需要保存在栈中，只有当右子树也遍历结束后，才能访问根栈中保存的结点需要入栈两次出栈两次。为了能有所区别，二叉树结点入栈时，附带一个标记位flag。第一次出栈时，并不访问结点。第二次出栈时才访问它将二叉树结点和标记组合在一起，定义新的栈的类型，专用于非递归实现二叉树的后序遍历过程typedefstruct SNode //进栈带标记结点{ BinTNodebtreeNode; //二叉树结点

intflag; //标记}StackTNode; typedefstruct{ //用于后序遍历的栈 StackTNodeelement[maxSize]; inttop; //栈顶位置}SeqBTreeStackforPostT;程序二叉树的应用可以使用二叉树来表示一个表达式，这样的二叉树称为表达式树2*y*(a+3*y)-b画出表达式树先根据运算符的优先级对表达式加括号去掉最外层括号。中间的运算符为根，前后两部分分别对应于左子树和右子树对左子树递归执行步骤②对右子树递归执行步骤②当遇到空串时，递归结束例5-12已知算术表达式的中缀形式为A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为（）A．-A+B*C/DEB．-A+B*CD/EC．-+*ABC/DED．-+A*BC/DE答案：D

第四节堆及优先队列前一种关系表明，任何一个分支结点的值都不大于它子结点的值，所以树根结点的值是全部结点中的最小值。这样的堆称为最小堆或小根堆后一种关系表明，任何一个分支结点的值都不小于它子结点的值，故树根结点的值是全部结点中的最大值。这样的堆称为最大堆或大根堆树根结点称为堆顶堆的定义中还隐含了递归的含义，当用完全二叉树的形式表示堆时，树中的任意一棵子树都可以构成堆，并且保持与原来同样的性质最大堆中任何结点的子树仍是最大堆最小堆中任何结点的子树仍是最小堆最小堆和最大堆堆的类型定义#defineHeapSize30 //堆的容量typedefintELEMType; //元素类型typedefstructHeap{ ELEMTypeheap[HeapSize]; //存放元素的数组 intn; //堆中当前元素个数};堆的基本操作intcreatHeap(maxHeap*H,ELEMTypearr[],intn); //创建堆intinsertHeap(maxHeap*H,ELEMTypex); //在堆中插入元素xintdeleteHeap(maxHeap*H,ELEMType*x); //删除堆顶元素intisHeapEmpty(maxHeap*H); //如果堆为空，则返回1，否则返回0intisHeapFull(maxHeap*H); //如果堆为满，则返回1，否则返回0最大堆的类型定义#defineHeapSize30 //堆的容量typedefintELEMType; //元素类型typedefstructmaxHeap{ ELEMTypeheap[HeapSize]; //存放元素的数组 intn; //堆中当前元素个数};判空、判满创建最大堆向最大堆中插入新元素删除堆顶元素例5-1370,13,65,24,56,48,92,86，将其建成最大堆例5-14在最大堆中插入新元素40例5-15删除最大堆的堆顶优先队列一些应用中，各元素本身还被赋予一个优先值，可以用一个非负整数表示优先值。优先值也称为优先权。具有优先值的各元素保存在一个结构中，这个结构称为优先队列。输出时，选择最优先的元素输出。“最优先”取决于优先值的定义，可以是优先值最小，也可以是优先值最大。第五节树和森林树的存储结构父结点表示法孩子结点表示法孩子-兄弟表示法父结点表示法树中每个结点至少含两个域，一个域用来保存结点本身的值，另一个域用来保存结点之父结点的相关信息孩子结点表示法父结点-孩子结点表示法孩子-兄弟表示法为树中的每个结点定义一个存储结点，其中有左、右两个指针域，左指针域指向这个结点的第一个孩子结点，右指针域指向这个结点的下一个兄弟结点树、森林与二叉树的转换树和二叉树都可以用二叉链表作为存储结构同一个二叉链表，若按树的存储含义来解释，可以还原为树。若按二叉树的存储含义来解释，可以还原为二叉树正是因为这一点，可以在树与二叉树之间建立一种对应关系转换规则规则1：将森林转换成二叉树设F={T1,T2,…,Tm}是森林，则可按如下规则将森林F转换为一棵二叉树B=(root,LB,RB)（1）若F为空（m=0），则B为空树（2）若F非空（m>0），则森林中T1的根作为二叉树B的根root；T1中各子树组成的森林F1={T11,T12,…,T1s}转换成的二叉树作为B的左子树BL；森林F’={T2,T3,…,Tm}转换成的二叉树作为B的右子树BR森林转换为二叉树转换规则规则2：将二叉树还原为森林设B=(root,BL,BR)是一棵二叉树，则可按如下规则转换成森林F={T1,T2,…,Tm}（1）若B为空，则F为空（2）若B非空，则B的根root作为F中第一棵树T1的根；B的左子树BL还原得到的森林作为T1的各子树；B的右子树BR还原得到的森林作为F中的T2,T3,…,Tm树和森林的遍历树的两种遍历策略先序（根）遍历先访问树的根结点，再依次先序遍历根结点的各棵子树后序（根）遍历若树的根结点有子树，则首先后序遍历各棵子树，然后再访问根结点；否则（根结点无子树），只访问根结点森林的两种遍历策略先序遍历森林森林的先序遍历过程，是按照树的排列次序，先序遍历各棵树后序遍历森林森林的后序遍历过程，是按照树的排列次序，后序遍历各棵树可以看出，森林的遍历序列中，各棵树中的结点不会混杂在一起森林与对应的二叉树的遍历序列的关系二叉树的先序遍历序列和中序遍历序列，与森林的先序遍历序列和后序遍历序列分别相同第六节哈夫曼树及哈夫曼编码编码ASCII编码、Unicode码、电报码定长编码算法简单，效率高在编码长度确定之后，译文的长度完成取决于原文的长度变长编码变长编码前缀特性：一个编码方案中，任何一个字符的编码都不是该方案中任何其他字符编码的前缀，这样的编码称为具有前缀特性正是因为编码方案具有前缀特性，才能够保证译码过程的正确性和唯一性。可以使用二叉树来表示一个编码方案在二叉树的分支上标注0或1，从根到某结点的路径上，各分支标注的0或1组成一个编码哈夫曼树二叉树中，叶结点的带权路径长度定义为叶结点的权值乘上其到根结点的路径长度二叉树的带权路径长度，就是树中所有叶结点的带权路径长度之和二叉树的外部带权路径长度记为WPL其中n为叶结点个数，wk为第k个叶结点的权值，lk为第k个叶结点的路径长度各字符出现的频度分别是6、12、25、30，构造4棵二叉树，分别计算其WPL值4棵二叉树的带权路径长度WPL分别为134、195、139和146我们的任务是构造具有最小WPL且满足前缀特性的编码树设有n个权值{w1,w2,…,wn}，构造具有n个叶结点的二叉树，每个叶结点带有一个权值wi。在所有这样的二叉树中，带权路