合工大数据结构07-树和二叉树.

合肥工业大学计算机与信息学院1数据结构（第七章树和二叉树）DataStructures张晶计算机与信息学院2020/1/4合肥工业大学计算机与信息学院2第七章树和二叉树第七章树和二叉树7.1树的相关概念和术语7.2二叉树的定义、性质和存储结构7.3二叉树的遍历及其应用7.4线索二叉树7.5树和森林7.6哈夫曼树（Huffman）合肥工业大学计算机与信息学院37.1树的相关概念和术语家族关系示意图/单位机构组成示意图定义：树T是由n个结点组成的有限集合（n0）:其中有一个根结点，其余结点可划分成m个（m=0）互不相交的子集T1,T2,...,Tm，且这些子集也分别构成树。（注意：有无空树的概念）合肥工业大学计算机与信息学院47.1树的相关概念和术语术语关系术语孩子结点——子树的根父结点兄弟结点——同一个结点的孩子结点互为兄弟祖先结点后代结点层次类术语根的层次为1其余结点的层次为其父结点层次加1高度/深度——整个树中结点的最大层次度——结点的孩子数目称为结点的度叶子（终结点）——度为0分支结点----度不为0的结点（非叶子结点）树的度——最大的结点度森林——多棵树有序树/无序树——按照兄弟结点之间的排列是否有序合肥工业大学计算机与信息学院57.1树的相关概念和术语运算（1）初始化（2）查找——结点的父、兄弟、祖先、后代、根（3）插入——叶子，子树（4）删除——叶子，子树树的存储？合肥工业大学计算机与信息学院6相关习题1.画出由4个结点所构成的所有形态的树（假设是无序树）。2.已知一棵树的度为4，其中度为4的结点的数目为3，度为3的结点的数目为4，度为2的结点的数目为5，度为1的结点的数目为2，请求出该树中的叶子结点的数目。合肥工业大学计算机与信息学院77.2二叉树的定义、性质和存储结构7.2.1定义二叉树T：是n个结点组成的有限集合（n=0）:n=0时为空二叉树，否则：其中有一个根结点，其余结点可以划分成两个互不相交的子集TL,TR，且TL,TR也分别构成二叉树——左、右子树。合肥工业大学计算机与信息学院87.2二叉树的定义、性质和存储结构二叉树与树的区别：是两种不同性质的结构；二叉树存在空树，树不存在空树；二叉树恰有两个子树，树可有多个；二叉树子树有序，树无序。比较三个结点的树与二叉树的各有几种不同的形态。三个结点的树三个结点的二叉树AABBCCAAAAABBBBBCCCCC合肥工业大学计算机与信息学院97.2二叉树的定义、性质和存储结构由定义可知，依据结点数的多少可将二叉树划分为五种不同的形态：（1）空树，即结点数为0（2）单结点二叉树，即仅有一个结点（3）左子树为空右子树不空（4）右子树为空左子树不空（5）左右子树均不空合肥工业大学计算机与信息学院107.2二叉树的定义、性质和存储结构7.2.2二叉树的性质性质1：第i层的结点数≤2i-1；性质2：高度为k（k≥1）的二叉树的结点总数≤2k-1；性质3：设二叉树的叶子结点数为n0，度为2的结点数为n2，则n0=n2+1。证明：设总结点数为n，度为1的结点数为n1，则n=n0+n1+n2——结点数（1）n-1=n1+2n2——分支数（2）式（1）－（2）得n0=n2+1课堂练习：已知一棵二叉树中，有20个叶子结点，10个结点只有左孩子，15个结点只有右孩子，求该二叉树的总结点数。合肥工业大学计算机与信息学院117.2二叉树的定义、性质和存储结构定义1：称高度为k且有2k-1个结点的二叉树为满二叉树。例如，高度为1~4的满二叉树如下。ABCGFEDANOABCGFEHIDKJMLCBA(a)高度为1的满二叉树(b)高度为2的满二叉树(c)高度为3的满二叉树(d)高度为4的满二叉树合肥工业大学计算机与信息学院127.2二叉树的定义、性质和存储结构定义2：在满二叉树最下一层从右到左依次连续去掉若干个结点的二叉树称为完全二叉树。下面分别给出完全二叉树和非完全二叉树的示例。ABCGFEHIDKJML(a)完全二叉树示例MNABCGFEHIDKJL(b)非完全二叉树示例ON合肥工业大学计算机与信息学院137.2二叉树的定义、性质和存储结构对完全二叉树编号编号的方式：从上到下，每一层中从左到右，根节点编号为1。例：下面完全二叉树的编号ABCGFEHIDKJML12345678910111213合肥工业大学计算机与信息学院147.2二叉树的定义、性质和存储结构性质4：有n个（n≥1）结点的完全二叉树的高度为。性质5：对完全二叉树进行编号，则对编号为i的结点，若存在左孩子结点，则其左孩子结点的编号为2i，若存在右孩子结点，则其右孩子结点的编号为2i+1，若存在父结点，则其父结点的编号为。2/i.1log2nABCGFEHIDKJML12345678910111213合肥工业大学计算机与信息学院157.2二叉树的定义、性质和存储结构课堂练习：（1）求100个结点的完全二叉树的叶子结点数。解：根据性质4，从编号51到100都是叶子。共有50个叶子。（2）已知完全二叉树的第7层有10个结点，问共有多少个结点？多少个叶子结点？多少个度为1的结点？解：共有26-1+10=73个结点。叶子求法：方法1、37到73都是叶子，共37个叶子结点；方法2、第7层10个结点都是叶子，第6层有32个结点，其中5个结点是第7层10个结点的父亲，所以共有10+32-5=37个叶子结点。度为1的结点数为0。（3）判断题：完全二叉树最多有1个度为1的结点。（）（4）编号为i、j的两个结点是否在同一层的条件是。10050合肥工业大学计算机与信息学院167.2二叉树的定义、性质和存储结构7.2.3二叉树的存储存储一个结构时，不仅要存值，还要存储元素间的关系。1.顺序存储方式存储方式：用数组存储二叉树各结点的值，各结点在数组中的位置（元素下标）----就是其在完全二叉树中对应结点的编号。例如：右图二叉树的存储如下所示。012345678910111213ABCGFEHIDKJML12345678910111213ABCDEFGHIJKLM合肥工业大学计算机与信息学院177.2二叉树的定义、性质和存储结构分析：这种方法有其优点，但也有不足：优点：方便、简洁缺点：只适合完全二叉树或近似的完全二叉树。例如，对如下形状的二叉树，仅有n个结点，但需要的数组元素个数为2n-1。问题：若数组元素占一个单元，则在n=20、30时，分别需要多大的存储空间？练习：设计算法求出编号i、j的最小公共祖先。x2x3x1xn1372n-1合肥工业大学计算机与信息学院187.2二叉树的定义、性质和存储结构2.动态二叉链表存储方式：二叉树中每个结点用一个有两个分叉的结点（二叉结点）来存储，每个分叉指向左右孩子结点中的一个----左右孩子结点指针）。由此可得到二叉树的二叉链表结构。设二叉结点类型为bnode,其中：左右孩子指针分别为lchild和rchild，存储结点值的字段为data，则结点的类型描述如下：Structbnode{elementtypedata;bnode*lchild,*rchild;};lchilddatarchild指向左孩子的指针指向右孩子的指针bnode合肥工业大学计算机与信息学院197.2二叉树的定义、性质和存储结构例：下面二叉树对应的二叉链表结构如图所示。相关问题：（1）如图所示，根结点的指针为T，则如何表示其左右孩子指针的标识符？（2）从图中可知，二叉链表中有值为空的指针，有n个结点的二叉链表中有多少个这样的空指针？AGFEDCB^G^AB^E^C^^D^F^T合肥工业大学计算机与信息学院20相关习题3.如果已知一棵二叉树有20个叶子结点，有10个结点仅有左孩子，15个结点仅有右孩子，求出该二叉树的结点数目。4.如果已知完全二叉树的第6层有5个叶子，试画出所有满足这一条件的完全二叉树，并指出结点数目最多的那棵完全二叉树的叶子结点数目。5.在编号的完全二叉树中，判断编号为i和j的两个结点在同一层的条件是什么？合肥工业大学计算机与信息学院217.3二叉树的遍历及其应用7.3.1遍历的基本方法二叉树的遍历——按照某种次序依次访问二叉树T中每个结点一次且仅一次。分析：（1）若T为空，遍历结束；（2）否则，设二叉树的形态如右图所示。a.假设左右子树能分别遍历（用L，R分别表示其遍历），则整个二叉树可有如下形式的遍历：先左后右：DLRLDRLRD先右后左：DRLRDLRLD先根序中根序后根序b.对于左右子树的遍历，可按照与整个二叉树相同的方式遍历（递归调用）DLR合肥工业大学计算机与信息学院227.3二叉树的遍历及其应用有关遍历方法的例题：例：分别写出下图二叉树的先序、中序和后序序列ABCDEFGHICDBEFAHGIDCFEBHIGADEIAGFCBH先序中序：后序：求解过程讨论求解过程讨论求解过程讨论合肥工业大学计算机与信息学院237.3二叉树的遍历及其应用例：已知一棵二叉树的先序序列和中序序列，要求还原该二叉树。先序：ABCDEFG中序：CDBEAGFGFDCBCDECDBEFGGFCDCDBAAABEFGGFE合肥工业大学计算机与信息学院247.3二叉树的遍历及其应用结论：已知中序序列和后序序列，或中序序列和先序序列，可以唯一确定一棵二叉树；而已知先序序列和后序序列不能唯一确定二叉树。课堂练习：已知二叉树中序序列和后序序列，还原此二叉树。AGFEDCB中序：CBDAGEF后序：CDBGFEA合肥工业大学计算机与信息学院257.3二叉树的遍历及其应用7.3.2遍历算法遍历方法先序遍历二叉树T若T不空，则：访问根；先序访问其左子树；先序访问其右子树中序遍历二叉树T若T不空，则：中序访问其左子树；访问根；中序访问其右子树。遍历算法voidpreorder(bnode*t){if(t!=NULL){visit(t);preorder(t-lchild);preorder(t-rchlid);}}voidinorder(bnode*t){if(t!=NULL){inorder(t-lchild);visit(t);inorder(t-rchlid);}}合肥工业大学计算机与信息学院267.3二叉树的遍历及其应用后序遍历二叉树T若T不空，则：后序访问其左子树；后序访问其右子树。访问根；voidpostorder(bnode*t){if(t!=NULL){postorder(t-lchild);postorder(t-rchlid);visit(t);}}合肥工业大学计算机与信息学院277.3二叉树的遍历及其应用练习：（1）对前述二叉树，按照阅读递归算法的方法，模拟执行。（2）证明preorder(bnode*T)对二叉树遍历的正确性（所有结点访问一次仅且一次）（3）设计算法求二叉树的结点数合肥工业大学计算机与信息学院287.3二叉树的遍历及其应用7.3.3遍历算法的应用例题：设计算法输出二叉树的所有叶子结点的值设计算法输出从根结点到每个叶子结点的路径7.3.4遍历方法的应用1、求给定二叉树的高度：（1）若T为空，则高度为0，遍历结束；（2）否则，设二叉树的形态如右图所示。a、假设左右子树能分别求出高度为hl、hr，则整个二叉树的高度为：max(hl,hr)+1;b、对于左右子树高度的求解，可按照与整个二叉树相同的方式进行（递归调用）TLR(直观上的高度求解过程及难度)合肥工业大学计算机与信息学院297.3二叉树的遍历及其应用设函数inthigh(bnode*t)为求T的高度算法，则inthigh(bnode*T){if(T==NULL)return(0);elsereturnmax(high(T-lchild),high(T-rchild))+1;}或者inthigh(bnode*T){if(T==NULL)return(0);else{hl=high(T-lchild);hr=high(T-rchild);h=max(hl,hr)+1;return(h);}}注意：h