第5章 树和二叉树

李冬梅第5章树和二叉树•Office:西配楼304（软件教研室）•Email:[e-mail]北京林业大学信息学院北京林业大学信息学院线性结构——一个对一个，如线性表、栈、队列树形结构——一个对多个，如树集合——数据元素间除“同属于一个集合”外，无其它关系图形结构——多个对多个，如图逻辑结构北京林业大学信息学院第5章树和二叉树5.1树和二叉树的定义5.2案例引入5.3树和二叉树的抽象数据类型定义5.4二叉树的性质和存储结构5.5遍历二叉树和线索二叉树5.6树和森林5.7哈夫曼树及其应用5.8案例分析与实现北京林业大学信息学院1.掌握二叉树的基本概念、性质和存储结构2.熟练掌握二叉树的前、中、后序遍历方法3.了解线索化二叉树的思想4.熟练掌握：哈夫曼树的实现方法、构造哈夫曼编码的方法5.了解：森林与二叉树的转换，树的遍历方法教学目标北京林业大学信息学院5.1树和二叉树的定义树（Tree）是n（n≥0）个结点的有限集，它或为空树（n=0）；或为非空树，对于非空树T：（1）有且仅有一个称之为根的结点；（2）除根结点以外的其余结点可分为m（m＞0）个互不相交的有限集T1,T2,…,Tm,其中每一个集合本身又是一棵树，并且称为根的子树（SubTree）。树的定义北京林业大学信息学院ACBGFEHIJDMKLA树是n个结点的有限集T1T2T3北京林业大学信息学院ACBGFEHIJDMKLAJIMHDGCFLKEB凹入表示ABFEKLGCDHMIJ嵌套集合(A(B(E(K,L),F),C(G),D(H(M),I,J)))广义表树的其它表示方式北京林业大学信息学院根叶子森林有序树无序树——即根结点(没有前驱)——即终端结点(没有后继)——指m棵不相交的树的集合(例如删除A后的子树个数)——结点各子树从左至右有序，不能互换（左为第一）——结点各子树可互换位置。ACBGFEHIJDMKL基本术语北京林业大学信息学院——即上层的那个结点(直接前驱)——即下层结点的子树的根(直接后继)——同一双亲下的同层结点（孩子之间互称兄弟）——即双亲位于同一层的结点（但并非同一双亲）——即从根到该结点所经分支的所有结点——即该结点下层子树中的任一结点双亲孩子兄弟堂兄弟祖先子孙ACBGFEHIJDMKL基本术语北京林业大学信息学院——即树的数据元素——结点挂接的子树数结点结点的度结点的层次终端结点分支结点树的度树的深度(或高度)——从根到该结点的层数（根结点算第一层）——即度为0的结点，即叶子——即度不为0的结点（也称为内部结点）——所有结点度中的最大值——指所有结点中最大的层数ACBGFEHIJDMKL层次1234基本术语北京林业大学信息学院二叉树（BinaryTree）是n（n≥0）个结点所构成的集合，它或为空树（n=0）；或为非空树，对于非空树T：（1）有且仅有一个称之为根的结点；（2）除根结点以外的其余结点分为两个互不相交的子集T1和T2，分别称为T的左子树和右子树，且T1和T2本身又都是二叉树。二叉树的定义北京林业大学信息学院普通树（多叉树）若不转化为二叉树，则运算很难实现为何要重点研究每结点最多只有两个“叉”的树？二叉树的结构最简单，规律性最强；可以证明，所有树都能转为唯一对应的二叉树，不失一般性。北京林业大学信息学院二叉树基本特点：•结点的度小于等于2•有序树（子树有序，不能颠倒）二叉树的五种不同形态北京林业大学信息学院具有3个结点的二叉树可能有几种不同形态？普通树呢？练习5种/2种北京林业大学信息学院5.2案例引入案例5.1：数据压缩问题将数据文件转换成由0、1组成的二进制串，称之为编码。字符编码字符编码字符编码a00a0a0b01b10b01c10c110c010d11d111d111（a）等长编码方案（b）不等长编码方案1（c）不等长编码方案2北京林业大学信息学院案例5.2：利用二叉树求解表达式的值以二叉树表示表达式的递归定义如下：（1）若表达式为数或简单变量，则相应二叉树中仅有一个根结点，其数据域存放该表达式信息；（2）若表达式为“第一操作数运算符第二操作数”的形式，则相应的二叉树中以左子树表示第一操作数，右子树表示第二操作数，根结点的数据域存放运算符（若为一元运算符，则左子树为空），其中，操作数本身又为表达式。(a+b*(c-d)-e/f)的二叉树北京林业大学信息学院5.3树和二叉树的抽象数据类型定义ADTBinaryTree{数据对象D:数据关系R:基本操作P：}ADTBinaryTree若D=Φ，则R=Φ；若D≠Φ，则R={H}；存在二元关系：①root唯一//关于根的说明②Dj∩Dk=Φ//关于子树不相交的说明③……//关于数据元素的说明④……//关于左子树和右子树的说明D是具有相同特性的数据元素的集合。//至少有20个二叉树的抽象数据类型定义北京林业大学信息学院CreateBiTree(&T,definition)初始条件；definition给出二叉树T的定义。操作结果：按definition构造二叉树T。PreOrderTraverse(T)初始条件：二叉树T存在。操作结果：先序遍历T，对每个结点访问一次。InOrderTraverse(T)初始条件：二叉树T存在。操作结果：中序遍历T，对每个结点访问一次。PostOrderTraverse(T)初始条件：二叉树T存在。操作结果：后序遍历T，对每个结点访问一次。北京林业大学信息学院5.4二叉树的性质和存储结构性质1:在二叉树的第i层上至多有2i-1个结点提问：第i层上至少有个结点？性质2:深度为k的二叉树至多有2k-1个结点提问：深度为k时至少有个结点？1k北京林业大学信息学院1891011124526731891011124526731nB1212nnB11212nnn012nnn性质3:对于任何一棵二叉树，若2度的结点数有n2个，则叶子数n0必定为n2＋1（即n0=n2+1）北京林业大学信息学院189101112131415452673满二叉树：一棵深度为k且有2k-1个结点的二叉树。（特点：每层都“充满”了结点）189101112452673特殊形态的二叉树完全二叉树：深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应只有最后一层叶子不满，且全部集中在左边北京林业大学信息学院满二叉树是叶子一个也不少的树，而完全二叉树虽然前n-1层是满的，但最底层却允许在右边缺少连续若干个结点。满二叉树是完全二叉树的一个特例。189101112131415452673189101112452673满二叉树和完全二叉树的区别北京林业大学信息学院一棵完全二叉树有5000个结点，可以计算出其叶结点的个数是（）。练习2500北京林业大学信息学院性质4:具有n个结点的完全二叉树的深度必为[log2n]＋1189101112452673k层nk-1层121k12k2k−1−1＜n≤2k−1或2k−1≤n＜2kk−1≤log2n＜k，因为k是整数所以k=log2n+1北京林业大学信息学院性质5:对完全二叉树，若从上至下、从左至右编号，则编号为i的结点，其左孩子编号必为2i，其右孩子编号必为2i＋1；其双亲的编号必为i/2。北京林业大学信息学院二叉树的顺序存储实现：按满二叉树的结点层次编号，依次存放二叉树中的数据元素。北京林业大学信息学院abcde0000fg012345678910abcdefg特点：结点间关系蕴含在其存储位置中浪费空间，适于存满二叉树和完全二叉树单支树二叉树的顺序存储北京林业大学信息学院DATAPARENTLCHILDRCHILDlchilddatarchildlchilddatarchildparent二叉树的链式存储北京林业大学信息学院ABCDEFGABCDEFG^^^^^^^^二叉链表typedefstructBiNode{TElemTypedata;structBiNode*lchild,*rchild;//左右孩子指针}BiNode,*BiTree;北京林业大学信息学院分析：必有2n个链域。除根结点外，每个结点有且仅有一个双亲，所以只会有n－1个结点的链域存放指针，指向非空子女结点。空指针数目＝2n－(n-1)=n+1在n个结点的二叉链表中，有个空指针域练习ABCDEFG^^^^^^^^n+1北京林业大学信息学院三叉链表ABCDEFGABCDEFG^^^^^^^^^lchilddataparentrchildtypedefstructTriTNode{TelemTypedata;structTriTNode*lchild,*parent,*rchild;}TriTNode,*TriTree;北京林业大学信息学院5.5遍历二叉树和线索二叉树遍历定义——指按某条搜索路线遍访每个结点且不重复（又称周游）。遍历用途——它是树结构插入、删除、修改、查找和排序运算的前提，是二叉树一切运算的基础和核心。北京林业大学信息学院ROOTLCHILDRCHILDDLRDLRLDRLRDDRLRDLRLD遍历规则先左后右北京林业大学信息学院先序遍历：中序遍历：后序遍历：ABCDEABDECDBEACDEBCA口诀：DLR—先序遍历，即先根再左再右LDR—中序遍历，即先左再根再右LRD—后序遍历，即先左再右再根北京林业大学信息学院+*A*/EDCB先序遍历+**/ABCDE前缀表示中序遍历A/B*C*D+E中缀表示后序遍历AB/C*D*E+后缀表示层序遍历+*E*D/CAB用二叉树表示算术表达式北京林业大学信息学院DLRADLRDLRBDCDLRADBC先序遍历序列：ABDC若二叉树为空，则空操作否则访问根结点(D)前序遍历左子树(L)前序遍历右子树(R)遍历的算法实现－先序遍历北京林业大学信息学院则三种遍历算法可写出:遍历的算法实现－－用递归形式格外简单！longFactorial(longn){if(n==0)return1;//基本项elsereturnn*Factorial(n-1);//归纳项}回忆:北京林业大学信息学院StatusPreOrderTraverse(BiTreeT){if(T==NULL)returnOK;//空二叉树else{coutT-data;//访问根结点PreOrderTraverse(T-lchild);//递归遍历左子树PreOrderTraverse(T-rchild);//递归遍历右子树}}先序遍历算法2020年1月17日北京林业大学信息学院StatusPreOrderTraverse(BiTreeT){if(T==NULL)returnOK;else{coutT-data;PreOrderTraverse(T-lchild);PreOrderTraverse(T-rchild);}}主程序Pre(T)返回返回pre(TR);返回返回pre(TR);ACBDTBprintf(B);pre(TL);BTAprintf(A);pre(TL);ATDprintf(D);pre(TL);DTCprintf(C);pre(TL);C返回T左是空返回pre(TR);T左是空返回T右是空返回T左是空返回T右是空返回pre(TR);先序序列：ABDC北京林业大学信息学院遍历的算法实现－中序遍历若二叉树为空，则空操作否则:中序遍历左子树(L)访问根结点(D)中序遍历右子树(R)ADBCLDRBLDRLDRADCLDR中序遍历序列：BDAC北京林业大学信息学院StatusInOrderTraverse(BiTreeT){if(T==NULL)returnOK;//空二叉树else{InOrderTraverse(T-lchild);//递归遍历左子树coutT-data;//访问根结点InOrderTraverse(T-rchild);//递归遍历右子树}}中序遍历算法北京林业大学信息学院遍历的算法实现－后序遍历若