大学数据结构课件--第6章 树和二叉树

1F6.1树的定义和基本术语F6.2二叉树F6.3遍历二叉树和线索二叉树F6.4树和森林F6.6赫夫曼树及其应用特点：非线性结构，一个直接前驱，但可能有多个直接后继（1：n）第6章树和二叉树21.树的定义注：树的定义具有递归性，即树中还有树。由一个或多个（n≥0）结点组成的有限集合。在任何一棵非空树T中：（1）有且仅有一个结点称为根（root）；（2）当n1时，其余的结点分为m（m≥0）个互不相交的有限集合T1、T2…Tm。每个集合本身又是棵树，被称作这个根的子树。6.1树的定义和基本术语3A只有根结点的树ABCDEFGHIJKLM根子树6.1树的定义和基本术语4树的抽象数据类型定义D是具有相同特性的数据元素的集合。ADTTree{}Tree数据对象D:数据操作P:数据关系R:若D是空集，则称为空树；//允许n=0若D中仅含一个数据元素，则R为空集；其他情况下的R存在二元关系：①Root唯一//关于根的说明②Dj∩Dk=//关于子树不相交的说明③…//关于数据元素的说明//至少15个6.1树的定义和基本术语5•图形表示法•嵌套集合表示法•广义表表示法•凹入表示法（目录表示法）树的表示方法6.1树的定义和基本术语6①图形表示法：…大连工业大学信息学院生物与食品学院外语学院数学物理电信计算机根子树ABCDEFGH6.1树的定义和基本术语7②广义表表示法：ABCDEFGH根作为由子树森林组成的表的名字写在表的左边A（B，C，D）A（B，C（E,F,G,H），D）③凹入表示法：ABCDEFGH6.1树的定义和基本术语8ABCDEFGH④嵌套表示法：ABDCEGFH6.1树的定义和基本术语92.若干术语ABCDJEFGHIKLM根----根结点（没有前驱）森林----指m棵不相交的树的集合有序树----结点各子树从左至右有序，不能互换（左为第一）无序树----结点各子树可互换位置双亲----上层的那个结点（直接前驱）孩子----下层结点的子树的根（直接后继）兄弟----同一双亲下的同一层结点（孩子之间互称兄弟）堂兄弟----双亲位于同一层的结点（但并非同一双亲）祖先----从根到该结点所经分支的所有结点子孙----该结点下层子树的任一结点6.1树的定义和基本术语10ABCDJEFGHIKLM结点----树中的数据元素结点的度----结点拥有的子树的数目（有几个直接后继度就是几）结点的层次----从根到该结点的层数（根结点算第一层）叶子----度为0的点（终端结点）分支结点----度不为0的点（非终端结点）树的度----所有结点度中的最大值（Max{各结点的度}）树的深度----所有结点中最大的层数（Max{各结点的层次}）（或高度）6.1树的定义和基本术语11二叉树的结构最简单，规律性最强；可以证明，所有树都能转化为唯一对应的二叉树，不失一般性。1.二叉树的定义2.二叉树的性质3.二叉树的存储结构6.2二叉树121、二叉树的定义①每个结点最多只有两棵子树（不存在度大于2的结点）；②左子树和右子树次序不能颠倒（有序树）。基本特征：基本形态：①②③④⑤•具有3个结点的二叉树可能有几种不同形态？普通树呢？6.2二叉树---定义132、二叉树的性质性质1：在二叉树的第i层上至多有2i-1个结点（i0）。问：第i层上至少有个结点？性质2：深度为k的二叉树至多有2k-1个结点（k0）。性质3：对于任何一棵二叉树，若度2的结点数有n2个，叶子结点数为n0，则n0=n2+1。6.2二叉树---性质14证明性质3：∵二叉树中全部结点数n=n0+n1+n2(叶子数+度1的结数+度为2的结点数)又∵二叉树中全部结点数n=B+1(总分支数+根结点)（除根结点外，每个结点必有一个直接前驱，即一个分支）而总分支数B=n1+2n2(度为1必有1个直接后继，度为2必有2个直接后继)三式联立可得：n0+n1+n2=n1+2n2+1，即n0=n2+16.2二叉树---性质15满二叉树：深度为k且有2k-1个结点的二叉树。特点：每一层上的结点数都是最大结点数。可以对满二叉树的结点进行连续编号。489510116121371415231完全二叉树：深度为k，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称之为完全二叉树。特点:（1）叶子结点只可能在层次最大的两层上出现；（2）对任一结点，若其右分支下的子孙的最大层次为h，则其左分支下的子孙的最大层次数必为h或h+1。489510672316.2二叉树---特例1612311458912136710141512311458912671012345671234566.2二叉树---特例17对于特殊性质的二叉树，还具备以下2个性质：性质4：具有n个结点的完全二叉树的深度必为log2n＋1。性质5：如果对一棵有n个结点的完全二叉树(其深度为log2n＋1)的结点按层序编号，则对任一结点i（1≤i≤n），有：1）如果i=1，则结点i是二叉树的根，无双亲；如果i1，则其双亲parent（i）是结点i/2；2）如果2in，则结点i无左孩子(结点i为叶子结点)；否则其左孩子lchild（i）是结点2i；3）如果2i+1n，则结点i无右孩子；否则其右孩子rchild(i)是结点2i+1。489510672316.2二叉树---性质18一、顺序存储结构3、二叉树的存储结构用一组地址连续的存储单元依次自上而下、自左至右存储二叉树上的结点元素。DHIEFGBCA0123456789ABCDEFGHIDFEBCA0123456789ABCDE0000F仅适合于完全二叉树对于非完全二叉树：将各层空缺处全部补上“虚结点”，其内容为0缺点：①浪费空间；②插入、删除不便6.2二叉树---存储结构19二、链式存储结构二叉链表中包含2个指针域。一般从根结点开始存储。DATAPARENTLCHILDRCHILDlchilddatarchildlchilddataparentrchild为了便于找到结点的双亲，可再增加一个双亲域指针，将二叉链表变成三叉链表。链表的头指针指向二叉树的根结点。6.2二叉树---存储结构20例：CEFDBGAA^BCD^^EF^G^^^^AB^^CD^^EF^G^^^^二叉链表三叉链表在含有n个结点的二叉链表中有n+1个空链域空指针个数：2*n0+1*n1+0*n2=2n0+n1=n0+n1+n0=n0+n1+n2+1=n+16.2二叉树---存储结构21一、遍历二叉树按某条搜索路径访问树中每个结点，使得每个结点均被访问一次，而且仅被访问一次。二叉树由根、左子树、右子树构成，三者的组合可构成6种遍历方案：根左右、根右左、左根右、左右根、右根左、右左根若限定“先左后右”，则有3种实现方案：根左右左根右左右根先序遍历中序遍历后序遍历6.3遍历二叉树和线索二叉树22DHIFGBCA1、先序遍历2、中序遍历3、后序遍历①访问根结点②先序遍历左子树③先序遍历右子树ABDCFGHI①中序遍历左子树②访问根结点③中序遍历右子树DBAFCHGI①后序遍历左子树②后序遍历右子树③访问根结点DBFHIGCA例1：6.3遍历二叉树和线索二叉树231、先序遍历2、中序遍历3、后序遍历+**/ABCDEA/B*C*D+EAB/C*D例2：*AB/C*E+D*E+前缀表达式中缀表达式后缀表达式6.3遍历二叉树和线索二叉树24例：已知一棵二叉树的中序序列和后序序列分别是BDCEAFHG和DECBHGFA，请画出这棵二叉树。讨论：若已知先序序列（或后序序列）和中序序列，能否恢复出对应的二叉树？分析：①由后序遍历特征，根结点必在后序序列尾部（即A）②由中序遍历特征，根结点必在其中间，而且其左部必全部是左子树的子孙（即BDCE），其右部必全部是右子树的子孙（即FHG）③继而，根据后序中的DECB子树可确定B为A的左孩子，根据HGF子串可确定F为A的右孩子；以此类推6.3遍历二叉树和线索二叉树25已知中序遍历：BDCEAFHG已知后序遍历：DECBHGFA（BDCE）（FHG）A（DCE）BFGHCDEAABC6.3遍历二叉树和线索二叉树26已知先序遍历序列如下：ABØDØØCEØFØØØABCEFD6.3遍历二叉树和线索二叉树27二、线索二叉树普通二叉树只能找到结点的左右孩子的信息，而该结点的直接前驱和直接后继只能在遍历过程中获得。若将遍历后对应的有关前驱和后继预存起来，则从第一个结点开始就能很快地遍历整个树了。例如中序遍历结果：A/B*C*D+E，实际上已将二叉树转为线性排列，显然具有唯一前驱和唯一后继。如何预存这类信息呢？增加两个域:前驱指针、后继指针利用n+1个空链域6.3遍历二叉树和线索二叉树28规定：1）若结点有左子树，则lchild指向其左孩子；否则，lchild指向其直接前驱（即线索）；2）若结点有右子树，则rchild指向其右孩子；否则，rchild指向其直接后继（即线索）；lchilddatarchild约定：当Tag域为0时，表示孩子情况；当Tag域为1时，表示线索情况。lchildLTagdataRTagrchild6.3遍历二叉树和线索二叉树29有关线索二叉树的几个术语：线索链表：用上述结点构成的二叉链表线索：指向前驱和后继结点的指针线索二叉树：同加上线索的二叉树（图形式样）线索化：对二叉树以某种次序遍历使其变为线索二叉树的过程线索化过程就是在遍历过程中修改空指针的过程：将空的lchild改为结点的直接前驱；将空的rchild改为结点的直接后继。非空指针呢？仍然指向孩子结点（称为“正常情况”）6.3遍历二叉树和线索二叉树30例：画出下列二叉树所对应的中序线索二叉树HIFGBCADE中序遍历结果：HDIBEAFCGNILNIL6.3遍历二叉树和线索二叉树31HIFGBCADENILNIL010A00B00C00D01E11F11G11H11I16.3遍历二叉树和线索二叉树中序遍历结果：HDIBEAFCG321.树的存储结构2.森林与二叉树的转换3.树和森林的遍历6.4树和森林33一、树的存储结构树有三种常用存储方式：①双亲表示法②孩子表示法③孩子兄弟表示法1、用双亲表示法来存储方法：用一组连续空间来存储树的结点，同时在每个结点中附设一个指示器，指示其双亲结点在链表中的位置。6.4树和森林---树的存储34例1：双亲表示法HDEFGBCA双亲表示法缺点：求结点的孩子时需要遍历整个结构01234567DataParentA-1B0C0D1E1F4G4H46.4树和森林---树的存储352、用孩子表示法来存储方法：将每个结点的孩子排列起来，形成一个带表头（装父亲结点）的线性表（n个结点要设立n个链表），再将n个表头用数组存放起来，这样就形成一个混合结构。HDEFGBCA孩子表示法BC^ADE^BC^D^FGH^EF^G^H^012345676.4树和森林---树的存储36HDEFGBCA带双亲的孩子表示法ParentData01234567ABCDEFGH-10011444BC^DE^FGH^^^^^^6.4树和森林---树的存储373、用孩子兄弟表示法来存储方法：用二叉链表来存储树，但链表的两个指针域含义不同。firstchilddatanextsibling指向结点的第一个孩子指向结点的第一个兄弟HDEFGBCA孩子兄弟表示法AB^DC^^^EF^^GH^^^6.4树和森林---树的存储38二、森林与二叉树的转换转换步骤：①结点的第一孩子做为其左孩子②结点的右邻近兄弟做为其右孩子HDEFGBIACABCIDEFGH二叉树1、树与二叉树的转换6.4树和森林---树与二叉树的转换392、二叉树与树的转换转换步骤：把所有右孩子都变成其双亲的兄弟ABCIDEFGHABICDEFHG6.4树和森林---树与二叉树的转换403、森林与二叉树的转换转换步骤：①各树要先各自转为二叉树②依次连接到前一个二叉树的右子树上BDACIGHJEF①ABIFCJDEGHIJGHFEA