树和二叉树-数据结构课件

树和二叉树-数据结构本章学习要点本章学习要点z掌握1.树和二叉树的性质，相关术语及基本概念。2.二叉树的两种存储方法，重点是链式存储据。3.二叉树三种顺序遍历及其递归实现算法。4.二叉树的层次遍历5.创建链式存储的二叉树的算法。6.中序线索二叉树的算法：中序线索二叉树上基本算法（遍历、求指定结点的前驱和后继、查找指定值的结点）。7.树的遍历算法（先根遍历、后根遍历）；森林的遍历算法（前序遍历，后序遍历）8.哈夫曼树的概念；哈夫曼树的构造算法；哈夫曼编码9.通过本章的算法的学习，让学生认识到递归定义的数据结构之下求解相应问题，思路清晰和简洁算法设计方法是采用递归的方式。z理解1.二叉树三种遍历的非递归算法及其与栈的关系2.在中序线索树指定结点下插入新结点的算法，学会在复杂情形下分类讨论的方法。3.树的三种存储结构（双亲表示法、孩子表示法、孩子兄弟表示法）及各自的特点（优点、缺点）4.掌握树、森林和对应的二叉树相互转换算法。第第6章树和二叉树章树和二叉树z树型结构是一类重要的非线性非线性数据结构。其中常见的是树树和二叉树二叉树树是以分支关系定义的层次结构z树结构在客观世界中广泛存在人类社会的族谱社会组织结构z在计算机领域编译程序中表示源程序的语法结构数据库中是信息的重要组织形式之一操作系统中的进程管理z本章主要讨论二叉树的存储及各种操作研究树和森林与二叉树的转换关系树的应用6.1树的定义和基本术语树的定义和基本术语z树(tree)是n(n0)个结点的有限集。z在任意一颗非空树中有且仅有一个特定的称为根(root)的结点;当n1时，其余结点可分为m(m0)个互不相交互不相交的有限集T1,T2,Tm，其中每一个集合本身又是一颗树，并且称为根的子树子树(SubTree)。z特点没有结点的树称为空树树中各子树是互不相交的树的示例树的示例A只有根结点的树ABCDEFGHIJKLM有子树的树根根子树子树抽象数据类型树的定义抽象数据类型树的定义ADT Tree 数据对象D：D是具有相同特性的数据元素的集合。数据关系R：若D为空集，则称为空树若D仅含一个数据元素，则R为空集，否则R=H，H是如下二元关系：(1)在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；(2)若D-root，则存在D-root的一个划分，D1,D2,Dm(m0)，对任意jk(1j,km)有DjDk=，且对任意的i(1im)，唯一存在数据元素xiDi,有H。(3)对应于D-root的划分，H-,有唯一的一个划分H1,H2,Hm(m0)，对任意jk(1j,km)有DjDk=,且对任意的i(1im)，Hi是D上的二元关系，(Di,Hi)是一颗符合本定义的树，称为根root的子树 基本操作InitTree(&T)DestroyTree(&T)CreateTree(&T,definition)ClearTree(&T)TreeEmpty(T)TreeDepth(T);Root(T)Value(T,cur_e);Assign(T,cur_e,value)Parent(T,cur_e)LeftChild(T,cur_e)RightChild(T,cur_e)InsertTree(&T,&p,I,c)DeleteTree(&T,&p,i)TraverseTree(T,visit()/ADT Tree基本术语基本术语z结点(node)包括一个数据元素及若干指向其子树的分支z结点的度(degree)结点拥有的子树数z叶子(leaf)或终端结点度为0的结点z非终端结点或分支结点度不为0的结点z内部结点除根结点外的分支结点z树的度树中各结点度的最大值z孩子(child)结点的子树的根称为该结点的孩子z双亲(parents)孩子结点的上层结点叫该结点的双亲z兄弟(sibling)同一个双亲的孩子互为兄弟z祖先从根结点到该结点所经分支上的所有结点z子孙以某结点为根的子树中的任一结点称为根的子孙z结点的层次(level)从根结点算起，根为第一层，它的孩子为第二层z堂兄弟双亲在同一层的结点互为堂兄弟z深度(depth)或高度树中结点的最大层次数z有序树树中结点的子树从左到右是有序的第一孩子有序树中最左的子树的根最后孩子有序树中最右的子树的根z无序树树中结点的子树没有前后次序z森林(forest)m(m0)棵互不相交的树的集合术语示例术语示例ABCDEFGHIJKLM结点A的度：3结点B的度：2结点M的度：0叶子：K，L，F，G，M，I，J结点A的孩子：B，C，D结点B的孩子：E，F结点I的双亲：D结点L的双亲：E结点B，C，D为兄弟结点K，L为兄弟结点A的层次：1结点M的层次：4树的深度：4结点F，G为堂兄弟结点A是结点F，G的祖先6.2二叉树（二叉树（BinaryTree）z定义：二叉树是n(n0)个结点的有限集，它或为空树(n=0)，或由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成z特点每个结点至多有二棵子树(即不存在度大于2的结点)二叉树的子树有左、右之分，且其次序不能任意颠倒z基本形态A只有根结点的二叉树空二叉树AB右子树为空AB左子树为空ABC左、右子树均非空抽象数据类型二叉树的定义抽象数据类型二叉树的定义ADT BinaryTree数据对象D：D是具有相同特性的数据元素的集合。数据关系R：若D为空集，则称为空树若D仅含一个数据元素，则R为空集，否则R=H，H是如下二元关系：(1)在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；(2)若D-root，则存在D-root=Dl,Dr，且DlDr=；(3)若Dl,则D1中存在唯一的元素xl,H，且存在Dl上的关系HlH；若Dr,则Dr中存在唯一的元素xr,H，且存在Dr上的关系HrH；H=，Hl，Hr；(4)(Dl，Hl)是一颗符合本定义的二叉树，称为根的左子树；(Dr，Hr)是一颗符合本定义的二叉树，称为根的右子树；基本操作InitBiTree(&T)DestroyBiTree(&T)CreateBiTree(&T,definition)ClearBiTree(&T)BiTreeEmpty(T)BiTreeDepth(T);Root(T)Value(T,cur_e);Assign(T,cur_e,value)Parent(T,cur_e)LeftChild(T,cur_e)RightChild(T,cur_e)LeftBibling(T,e)RightSibling(T,e)InsertChild(T,p,LR,c)DeleteChild(T,p,LR,c)ProOrderTraverse(T,Visit()/先序遍历二叉树先序遍历二叉树InOrderTraverse(T,Visit()/中序遍历二叉树中序遍历二叉树PostOrderTraverse(T,Visit()/后序遍历二叉树后序遍历二叉树LevelOrderTraverse(T,Visit()/层次遍历二叉树层次遍历二叉树/ADT BinaryTree二叉树的性质（性质二叉树的性质（性质1）z在二叉树的第i层上至多有2i-1个结点(i1)。z归纳法证明i=1时，只有一个根结点，显然21-1=20=1,成立。假设对于所有的j，1=ji成立，即第j层最多2j-1个结点。那么可以证明j=i时成立。由归纳假设：第i-1层上至多2(i-1)-1个结点。由于二叉树的每个结点的度最多为2，故在第i层上的最大结点数为第i-1层上最大结点数的2倍，即2x2(i-1)-1=2i-1。证明完毕1231145897101415二叉树的性质（性质二叉树的性质（性质2）z深度为k的二叉树至多有2k-1个结点(k1)z证明由性质1可见，深度为k的二叉树的最大结点数为二叉树的性质（性质二叉树的性质（性质3）z对任何一颗二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1z证明设n1为二叉树T中度为1的结点数因为二叉树中所有结点的度均小于或等于2，则n=n0+n1+n2(1)分析分支数的关系，除了根结点外，其余结点都有且只有一个分支进入。设B为分支总数，则n=B+1由于这些分支都是由度为1或2的结点发出的，故B=n1+2n2于是：n=n1+2n2+1(2)由(1)和(2)得n0=n2+1z证毕几种特殊形式的二叉树几种特殊形式的二叉树z满二叉树定义：一颗深度为k且有2k-1个结点的二叉树称为满二叉树，特点：每一层上的结点数都是最大结点数z完全二叉树定义：深度为k，有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称为完全二叉树特点叶子结点只可能在层次最大的两层上出现对任一结点，若其右分支下子孙的最大层次为i，则其左分支下子孙的最大层次必为i 或i+11231145891213671014151231145891267101234567123456完全二叉树示例完全二叉树示例二叉树的性质（性质二叉树的性质（性质4）z具有n个结点的完全二叉树的深度为z证明假设深度为k，则根据性质2和完全二叉树的定义有于是k-1log2n1，则其双亲PARENT(i)是结点 。如果2in，则结点i无左孩子（结点i为叶子结点）；否则其左孩子LCHILD(i)是结点2i。如果2i+1n，则结点i无右孩子（结点i为叶子结点）；否则其右孩子RCHILD(i)是结点2i+1。二叉树的存储结构二叉树的存储结构顺序存储结构顺序存储结构z存储顺序存储结构实现：按满二叉树的结点层次编号，依次存放二叉树中的数据元素特点：结点间关系蕴含在其存储位置中浪费空间，适于存满二叉树和完全二叉树z#define MAX_TREE_SIZE 100 /二叉树的最大结点数z typedef TElemType SqBiTreeMAX_TREE_SIZE;/0号单元存储根结点zSqBiTree btabcdefga b c d e 0 0 0 0 f g1 2 3 4 5 6 7 8 9 10 11二叉树的存储结构二叉树的存储结构二叉链表二叉链表z二叉链表typedef struct BiTNodeTElemTypedata;struct BiTNode*lchild,*rchild;BiTNode,*BiTreeABCDEFG在在n个结点的二叉链表中，有个结点的二叉链表中，有n+1个空指针域个空指针域lchild data rchild AB C D E F G二叉树的二叉链表存储表示二叉树的二叉链表存储表示z-二叉树的二叉链表存储表示-ztypedef struct BiTNodez TElemTypedata;z struct BiTNode*lchild,*rchild;/左右孩子指针zBiTNode,*BiTree;z-基本操作的函数原型说明-zstatus CreateBiTree(Bitree&T)zStatus PreOrderTraverse(BiTree T,Status(*visit)(TElemType e)zStatus InOrderTraverse(BiTree T,Status(*visit)(TElemType e)zStatus PostOrderTraverse(BiTree T,Status(*visit)(TElemType e)zStatus LevelOrderTraverse(BiTree T,Status(*visit)(TElemType e)二叉树的存储结构二叉树的存储结构三叉链表三叉链表z三叉链表typedef struct TNodeTElemTypedata;struct TNode*lchild,*rchild,*parent;TNode,*TTreelchild data parent rchildABCDEFG A B C D E F G二叉树存储方式的比较二叉树存储方式的比较z在不同的存储结构中，实现二叉树的操作方法不同z具体应用中根据二叉树的形态结合操作采用合适的存储结构InitBiTree(&T)DestroyBiTree(&T)CreateBiTree(&T,definition)ClearBiTree(&T)BiTreeEmpty(T)BiTreeDepth(T)Root(T)Value(T,cur_e)Assign(T,cur_e,value)Parent(T,cur_e)LeftChild(T,cur_e)RightChild(T,cur_e)LeftBibling(T,e)RightSibling(T,e)InsertChild(T,p,LR,c)DeleteChild(T,p,LR,c)ProOrderTraverse(T,Visit()InOrderTraverse(T,Visit()PostOrderTraverse(T,Visit()LevelOrderTraverse(T,Visit()例题例题 选择题选择题 1/5z1.下面关于二叉树的结论正确的是A二叉树中，度为O的结点个数等于度为2的结点个数加1。B二叉树中结点个数必大于O。C完全二叉树中，任何一个结点的度，或者为O，或者为2。D二叉树的度是2。z分析：该题主要考查二叉树逻辑结构的特点。正确答案为A。二叉树中结点个数可以为O，称为空树，所以B错。满二叉树中，任何一个结点的度，或者为O，或者为2。完全二叉树中，任何一个结点的度，或者为O，或者为1，或者为2。所以C错。二叉树的度可以是O、1、2。所以D错。例题例题 选择题选择题 2/5z2.一棵三叉树中，已知度为3的结点数等于度为2的结点数，且树中叶结点的数目为13，则度为2的结点数目A.4B.2C.3D.5z分析：该题主要考查多叉树逻辑结构的特点。正确答案为A。例题例题 选择题选择题 3/5z3.对一个满二叉树，m个树枝，n个结点，深度为h，则A.n=h+mB.h+m=2nC.m=h-1D.n=2h-1z分析：该题主要考查满二叉树的定义正确答案为D。例题例题 选择题选择题 4/5z4.一棵有n个结点的k叉树，树中所有结点的度之和为A.n-1B.knC.n2D.2nz分析：该题要考查树的结点和度之间的关系由树的度的定义可知结点的度即为与之相连的子结点的个数，只有根结点不是连在其他结点上，所以和为n-1。答案为A。例题例题 选择题选择题 5/5z5.将含有150个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点的编号为1，则编号为69的结点的双亲结点的编号为A.33B.34C.35D.36z分析：该题主要考查完全二叉树的逻辑结构由二叉树的性质5可知，结点69的双亲结点编号为69/234。所以答案为B。例题例题 判断题判断题 1/1z1.完全二叉树中，若一个结点没有左孩子，则它必然是叶子结点。z正确z分析：该题口主要考查完全二叉树的逻辑结构。深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1到n的结点一一对应时，称为完全二叉树。根据此定义，若完全二叉树中某结点无左孩子，则其必定没有右孩子，因此是叶结点。所以这种说法是正确的例题例题 填空题填空题 1/4z1.一棵高度为H的满K叉树，按层次从1开始编号，则；z(1)第i层结点的数为()z(2)编号为n的结点的父结点的编号为()z(3)编号为n的结点的第i个孩子的编号为()z(4)编号为n的结点有右兄弟的条件是(),右兄弟的编号为()z分析：该题主要考查对二叉树定义和性质的理解。z ki-1k(n-1)+1+in+1例题例题 填空题填空题 2/4z2.如果某二叉树中有 30 个叶结点，另有 30 个结点仅有一个孩子结点，则该二叉树中共有()个结点。z分析：该题口主要考查二叉树结点之间的关系。设 i、j、k 分别为二叉树中度为 O、1、2 的结点数则 n=i+j+k。根据二叉树的性质，i=k+1，有 n=i+j+i-1=30+30+30-1=89，所以二叉树中有个 89 结点。89例题例题 填空题填空题 3/4z3.n个结点的完全二叉树，编号最大的非叶结点是()号结点，编号最小的叶结点是()号结点。z分析：该题主要考查完全二叉树的结构。n个结点的完全二叉树，编号最大的叶结点就是n号结点，它的双亲结点就是编号最大的非叶结点。根据完全二叉树的性质，n的双亲为n/2。编号最大的非叶结点的右边一个结点，即n/21号结点，是编号最小的叶结点。n/2n/21例题例题 应用题应用题 4/4z4.设一棵度为 k 的树中有 n1个度为 1 的结点，n2个度为 2 的结点，nk个度为k的结点，求该树上有多少叶子结点？z分析与解答：该题主要考查树的基本概念和结构。根据两个等式：求结点总数：n=n0+n1+nk求树枝总数：n-1=n1+2n2+knk因此，n0=1+0n1+1n2+(k-1)nkn0习题习题一、选择题z1.设树T的度为4，其中度为1，2，3，4的结点个数分别为4，2，1，1。则树T中叶子数为()A.5B.6C.7D.8z2.由4个结点可以构造出多少种不同的二叉树？()A.10B.12C.14D.16z3.一颗二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是()。A.9B.11C.15D.不确定二、填空题z1.已知二叉树有50个叶子结点，则该二叉树的总结点数至少是（99）。z2.在一颗二叉树中，度为0的结点的个数为n0，度为2的结点个数为n2，则有n0=（N2+1）。z3.设一颗完全二叉树叶子结点数为k，最后一层结点数为偶数时，则该二叉树的高度为（log(2k-1)+1）；最后一层结点为奇数时，则该二叉树的高度为（logk+2）。z4.深度为k的完全二叉树至少有（2(k-1)）个结点，至多有（2k-1）个结点。习题（续）习题（续）三应用题z1已知一棵树边的集合为(i,m),(i,n),(e,i),(b,e),(b,d),(a,b),(g,j),(g,k),(c,g),(c,f),(h,l),(c,h),(a,c)用树型表示法画出此树，并回答下列问题：(1)哪个是根结点?(2)哪些是叶结点?(3)哪个是g的双亲?(4)哪些是g的祖先?(5)哪些是g的孩子?(6)哪些是e的子孙?(7)哪些是e的兄弟?哪些是f的兄弟?(8)结点b和n的层次号分别是什么?(9)树的深度是多少?(10)以结点c为根的子树的深度是多少?(11)树的度是多少?课堂练习课堂练习z应用题1、若一颗二叉树中所有非叶子结点都有左右孩子，假设这颗二叉树有2009个叶子结点，则该树中共有多少结点？2、已知某完全二叉树有100个结点，则该二叉树的叶子数是多少？z判断题1、二叉树是度为2的有序树。2、完全二叉树一定存在度为1的结点。3、完全二叉树一定不存在度为1的结点。4、对于有N个结点的二叉树，其高度为log2n。5、没有度为0的二叉树6、二叉树中至少有一个结点的度为26.3 遍历二叉树和线索二叉树遍历二叉树和线索二叉树z遍历二叉树算法6.1 先序遍历二叉树算法6.2 中序遍历二叉树的非递归算法算法6.3 中序遍历二叉树的非递归算法算法6.4 先序创建二叉树z线索二叉树算法6.5 线索二叉树中序遍历算法6.6 中序线索二叉树算法6.7 中序线索二叉树遍历二叉树遍历二叉树z遍历按一定规律走遍二叉树的各个顶点，且使每一顶点仅被访问一次，即找一个完整而有规律的走法，以得到树中所有结点的一个线性排列z思路二叉树组成：左子树、根、右子树，如果能够依次遍历左子树、根和右子树这三部分，则能够遍历整个树z遍历方式：根据根的访问次序，分为3种先序遍历：访问根结点,先序遍历左子树先序遍历右子树中序遍历：中序遍历左子树访问根结点中序遍历右子树后序遍历：后序遍历左子树后序遍历右子树访问根结点按层次遍历：从上到下、从左到右访问各结点DLRLDR、LRD、DLRRDL、RLD、DRL先序遍历图例ADBCD L RAD L RD L RBDCD L R先序遍历序列：A B D C中序遍历图例ADBCL D RBL D RL D RADCL D R中序遍历序列：B D A C后序遍历图例ADBC L R DL R DL R DADCL R D后序遍历序列：D B C AB遍历二叉树示例遍历二叉树示例-+/a*b-efcd先序遍历：中序遍历：后序遍历：层次遍历：-+a*b-c d/e f-+a*b-cd/ef-+a*b-cd/e f-+a*b-c d/e f算法算法6.1 先序遍历二叉树的递归算法先序遍历二叉树的递归算法Status PreOrderTraverse(BiTree T,Status(*Visit)(TElemType)/先序遍历采用二叉链表存储的二叉树T if(T)if(Visit(T-LChild,Visit)/递归遍历左子树 if(PreOrderTraverse(T-RChild,Visit)reutrn OK;/递归遍历右子树 reutrn ERROR;else return OK;/PreOrderTraverse-Status PrintElem(TElemType e)printf(e);调用：ProOrderTraverse(T,PrintElement)中序、后序遍历二叉树的递归算法中序、后序遍历二叉树的递归算法Status InOrderTraverse(BiTree T,Status(*Visit)(TElemType)if(T)if(InOrderTraverse(T-LChild,Visit)if(Visit(T-RChild,Visit)reutrn OK;reutrn ERROR;else return OK;/InOrderTraverseStatus PostOrderTraverse(BiTree T,Status(*Visit)(TElemType)if(T)if(PostOrderTraverse(T-LChild,Visit)if(PostOrderTraverse(T-RChild,Visit)if(Visit(T-data);pre(T-lchild);pre(T-rchild);主程序主程序pre(T)返回返回pre(T R);返回返回pre(T R);ACBDTBVisit(B);pre(T L);BTAVisit(A);pre(T L);ATDVisit(D);pre(T L);DTCVisit(C);pre(T L);C返回T左是空返回pre(T R);T左是空返回T右是空返回T左是空返回T右是空返回pre(T R);先序序列：A B D C算法算法6.2 中序遍历二叉树非递归算法中序遍历二叉树非递归算法1Status InOrderTraverse(BitTree T,Status(*Visit(TElemType e)InitStack(S);Push(S,T);while(!Stack(S)while(GetTop(S,p)&p)Push(S,p-lchild);Pop(S,p);if(!StackEmpty(S)Pop(S);if(!Visit(P-data)return ERROR;Push(S,p-rchild);/if/whilereturn OK;/InOrderTraverse算法算法6.3 中序遍历二叉树非递归算法中序遍历二叉树非递归算法2Status InOrderTraverse(BitTree T,Status(*Visit(TElemType e)InitStack(S);p=T;while(p|!StackEmpty(S)if(p)Push(S,p);p=p-lchild;/ifelsePop(S,p)if(!Visit(p-data)reutrn ERROR;p=p-rchild;/else/whilereturn OK;/InOrderTraverse遍历算法应用遍历算法应用 算法算法6.4 CreateBiTreez按先序遍历序列建立二叉树的二叉链表，已知先序序列为：A B C#D E#G#F#Status CreateBiTree(BiTree&T)scanf(&ch);if(ch=#)T=NULL;elseif(!(T=(BiTNode*)malloc(sizeof(BiTNode)exit(OVERFLOW);T-data=ch;CreateBiTree(T-lchild);CreateBiTree(T-rchild);/else/CreateBiTree A B C D E F G 遍历算法应用遍历算法应用z统计二叉树中叶子结点个数算法z求二叉树深度算法6.3.2 线索二叉树线索二叉树z定义：前驱与后继：在二叉树的先序、中序或后序遍历序列中两个相邻的结点互称为前驱与后继线索：指向前驱或后继结点的指针称为线索线索二叉树：加上线索的二叉链表表示的二叉树叫线索二叉树线索化：对二叉树按某种遍历次序使其变为线索二叉树的过程叫线索化z实现在有n个结点的二叉链表中必定有n+1个空链域在线索二叉树的结点中增加两个标志域Ltag和Rtaglchild:若 LTag=0,指向左孩子；若Ltag=1,指向其前驱rchild:若 RTag=0,指向右孩子；若Rtag=1,指向其后继z结点定义：lchildLtagdataRTagrchild线索二叉树图例线索二叉树图例ABCDE A B D C ET先序序列：ABCDE先序线索二叉树00001111 11 A B D C ET中序序列：BCAED中序线索二叉树0000111111 A B D C ET后序序列：CBEDA后序线索二叉树0000111111线索二叉树图例线索二叉树图例ABCDE A B D C ET先序序列：ABCDE先序线索二叉树00001111 11 A B D C ET中序序列：BCAED中序线索二叉树0000111111 A B D C ET后序序列：CBEDA后序线索二叉树0000111111线索二叉树遍历线索二叉树遍历z在线索树上进行遍历，只要找到序列中的第一个结点，然后依次找结点的后继直到其后继为空为止。z如何找后继？（不是每个结点都记录了后继的。）z中序线索二叉树如果对应的TAG=1。则直接得到该结点的前驱或后继。否则：结点的后继：右子树遍历的第一个结点，即右子树最左下结点结点的前驱：左子树遍历的最后一个结点，即左子树最右下结点。z后序线索二叉树若结点为二叉树的根，后继为空。若结点是其双亲的右孩子或是其双亲的独生左孩子，后期为该结点的双亲若结点是其双亲的左孩子，且有右兄弟，则后继为双亲右子树上按后序遍历的第一个结点二叉树的二叉线索存储二叉树的二叉线索存储typedef enum PointerTagLink,Thread;typedef struct BiTNodeTElemType data;struct BiThrNode*lchild,*rchild;PointerTag LTag,RTag;BiThrNode,*BiThrTree;0 A 0 1 B 0 0 D 1 1 C 1 1 E 1 T中序序列：BCAED带头结点的中序线索二叉树 0 1ABCDE A B D C ET中序序列：BCAED中序线索二叉树0000111111算法算法6.5 中序遍历线索二叉树中序遍历线索二叉树Status InOrderTraverse_Thr(BiThrTree T,Status(*Visit)(TElemType e)p=T-lchild;while(p!=T)while(p-LTag=Link)p=p-lchild;if(!visit(p-data)return ERROR;while(p-RTag=Thread&p-rchild!=T)p=p-rchild;Visit(p-data);p=p-rchild;return OK;/InOrderTraverse_Thr二叉树的线索化算法二叉树的线索化算法Status InOrderThreading(BiThrTree&Thrt,BiThrTree T)if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode)exit(OVERFLOW);Thrt-LTag=Link;Thrt-RTag=Thread;Thrt-rchild=Thrt;if(!T)Thrt-lchild=Thrt;elseThrt-lchild=T;pre=Thrt;InThreading(T);pre-rchild=Thrt;pre-RTag=Thread;Thrt-rchild=pre;return OK;/InOrderThreadingvoid InThreading(BiThrTree p)if(p)InThreading(p-lchild);if(!p-lchild)p-LTag=Thread;p-lchild=pre;if(!pre-rchild)pre-RTag=Thread;pre-rchild=p;pre=p;InThreading(p-rchild);/InThreading例题例题 选择题选择题 1/5z1设n、m为一棵二叉树上的两个结点，在中序遍历时，n在m之前的条件是A.n在m右方B.n是m祖先C.n在m左方D.n是m子孙z分析：该题主要考查二叉树的遍历。根据二叉树的形态和中序遍历算法，当n在m左边时，结点n首先被遍历。当n是m祖先时，它们之间的关系无法确定，不妨假设n是根结点，m是其左孩子，则m在n之前；m是其右孩子，则n在m之前。z正确答案为C。例题例题 选择题选择题 2/5z2在一棵二叉树结点的先序序列、中序序列、后序序列中，所有叶子结点的先后顺序A都不相同B先序和中序相同，而与后序不同C完全相同D中序和后序相同，而与先序不同z分析：该题主要考查二叉树的遍历。z无论哪种遍历所得的序列都是在“左”、“右”两结点的空隙中插入“根”结点的排列，即左、右结点的顺序固定不变，改变的是“根”结点，叶子结点的先后顺序都不变。z答案为C。例题例题 选择题选择题 3/5z3欲实现任意二叉树的后序遍历的非递归算法而不必使用栈结构，最佳方案是二叉树采用存储结构。A三叉链表B广义表C二叉链表D顺序z分析：该题主要考查二叉树的存储结构和非递归遍历算法。z此题答案为A。三叉链表是将双亲表示法和孩子兄弟表示法结合起来，既能方便地从双亲查找孩子，又能方便地从孩子查找例题例题 选择题选择题 4/5z4一棵二叉树满足下列条件：对任一结点，若存在左、右子树，则其值都小于它的左子树上所有结点的值，而大于右子树上所有结点的值。现采用遍历方式就可以得到这棵二又树上所有结点的递减序列。A先序B中序C后序D层次z分析：该题主要考查二叉树的遍历。由于中序遍历的顺序是先中序遍历左子树，再访问根结点，最后中序遍历右子树。这样可以保证，对任一结点其左孩子总在它的左边，其右孩子总在它的右边。当二叉树满足题述条件时，其中序序列一定是个递减序列。z答案为B。例题例题 选择题选择题 5/5z5对含有几个结点的非空二叉树，采用任何一种遍历方式，其结点访问序列均相同。A.0B.1C.2D不存在这样的二叉树z分析：该题主要考查二叉树的三种遍历次序的关系。三种遍历方式的不同点，在于访问根结点的时机不同。当一棵二叉树仅含一个根结点时，不管采用哪种遍历方式，所得到的结点序列总是相同的。z此题答案为B。例题例题 判断题判断题 1/4z1按中序遍历二叉树时，某个结点（有右子树）的直接后继是它的右子树中第一个被访问的结点。z正确z分析：该题主要考查二叉树的中序遍历。这种说法正确。因为中序遍历按LDR的顺序进行，若以某结点为其直接后继，必须是右子树中第一个被访问的结点。例题例题 判断题判断题 2/4z2有1个以上结点的二叉树，已知先序和后序遍历序列，能唯一确定一棵二叉树。z错误z分析：该题主要考查二叉树的遍历的性质。这种说法不正确。如已知先序为 12，后序遍历为 21，则可以有两棵二叉树。例题例题 判断题判断题 3/5z3用二叉树的先序遍历和中序遍历可以导出二叉树的后序遍历。z正确z分析：该题主要考查二叉树的遍历和逻辑结构。用二叉树的先序遍历和中序遍历可以确定二叉树的逻辑结构，就可以进一步导出二叉树的后序遍历。通常已知二叉树的先序遍历和后序遍历，无法确定一棵二叉树。例题例题 判断题判断题 4/4z4若一个叶子结点是某二叉树中序遍历序列的最后一个结点，那么它也是该二叉树的先序遍历序列的最后一个结点。z正确z分析：该题主要考查二叉树的遍历。当一个叶子结点是某二叉树中序遍历的最后一个结点，则它一定位于二叉树的右子树上最右端，无论先序遍历或中序遍历，右子树上的最右端的叶子结点肯定最后访问。若题中的叶子结点替换成普通结点，则命题不成立。例题例题 填空题填空题z1.N个结点的二叉树按某种遍历规则对结点从1到N依次递增编号，如果z(1)任一结点的编号等于它的左子树中的最小编号减1，则为遍历；z(2)某结点右子树中最小编号等于左子树中的最大编号加1，则为遍历。z答案：先序，后序。z分析：该题主要考查二叉树的结构和遍历。z对于先序遍历，因为首先访问根结点，再先序遍历左子树，最后先序遍历右子树，所以根结点编号等于左子树的根结点编号减1。z对于后序遍历，因为首先后序遍历左子树，然后后序遍历右子树，最后访问根结点，所以右子树中最小编号等于左子树中的最大编号加1。例题应用题例题应用题 1/2z1满足下列条件的非空二叉树具有什么形状？(1)先序和中序相同(2)中序和后序相同(3)先序和后序相同z分析：该题主要考察二叉树的结构和遍历性质。(1)只有一个结点或没有左子树的二叉树(2)只有一个结点或没有右子树的二叉树(3)只有一个结点的二叉树例题应用题例题应用题 2/2z2已知二叉树左右子树都含有m个结点，当m鹅时，试构造满足如下要求的所有二叉树。z(1）左右子树的先序与中序序列相同。z(2）左子树的中序与后序序列相同，右子树的先序与中序序列相同。z分析：该题由上题引中得到，主要考查二叉树的结构和遍历的性质如图。例题算法设计题例题算法设计题z设两棵二叉树的根结点地址分别为P及Q，采用二叉链表的形式存储这二棵树上所有的结点。请编写程序，判断它们是否相似。z分析：该题主要考查二叉树遍历算法的应用。所谓二棵二叉树S和t相似，要求：它们都为空或都只有一个根结点；或它们的根结点及左右子树均相似。Status BiLike(BiTree P,BiTree Q)if(P=NULL&Q=NULL)return TRUE;if(P=NULL|Q=NULL)return FALSE;like1=BiLike(p-lchild,q-rchild);like2=BiLike(p-rchild,q-rchild);return(like1&like2);/BiLike习题习题 填空题z1 某二叉树的先序遍历序列和后序遍历序列正好相反，则此二叉树一定是()A空或只有一个结点B完全二叉树C单支树D高度等于结点数z2在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序()。A都不相同B完全相同C先序和中序相同，而与后序不同D中序和后序相同，而与先序不同填空题z1有()种不同形态的二叉树可以按照中序遍历得到相同的abc序列。z2已知二叉树先序为ABDEGCF，中序为DBGEACF，则后序一定是()判断题z1二叉树线索化后一定不存在空指针域。z2非空的二叉树一定满足：某结点若有左孩子，则其中序前驱一定没有右孩子。z3由先序和后序遍历序列不能唯一确定一棵二叉树。z4一个树的叶结点，在前序遍历和后序遍历下，皆以相同的相对位置出现。算法设计题z1设计一个将二叉树中每个结点的左右孩子互换的算法。z2试编写算法判断两棵二叉树是否等价。称二叉树T1和T2是等价的：如果T1和T2都是空的二叉树；或者T1和T2的根结点的值相同，并且T1的左子树与T2的左子树是等价的，T1的右子树与T2的右子树是等价的。课堂练习课堂练习z假设一棵二叉树的层次序列是ABCDEFGHIJ和中序序列是DBGEHJACIF,请画出该树。ABCDEFGHIJ6.4 树和森林树和森林z树的存储结构z森林和二叉树的转换z树和森林的遍历树的存储结构树的存储结构-双亲表示法双亲表示法z双亲表示法以一组地址连续空间存储树的结点，同时在每个节点中附设一个指示器指示其双亲节点在链表中的位置。#define MAX_TREE_SIZE 100typedef struct PTNode/结点结构 TElemType data;int parent;/双亲位置域PTNode;typedef struct/树结构 PTNode nodesMAX_TREE_SIZE;int r,n;/根的位置和结点数PTreez利用除了根以外每个结 点有唯一的双亲的特点。abcdefhgi6012345789dataparentacdefghib012235551R-1可以方便地找某可以方便地找某个结点的双亲。个结点的双亲。如何找某个结点的如何找某个结点的孩子？孩子？树的存储结构树的存储结构-多重链表多重链表z思路多重链表：每个结点有多个指针域，分别指向其子树的根结点同构：结点的指针个数相等，为树的度D结点不同构：结点指针个数不等，为该结点的度dz分析同构方案：有大量空指针域异构方案：操作不方便data child1 child2 .childDdata degree child1 child2 .childd树的存储结构树的存储结构-孩子表示法孩子表示法z孩子链表：每个结点的孩子结点用单链表存储，再用含n个元素的结构数组指向每个孩子链表z树的孩子链表存储表示typedef struct CTNode int child;/该结点在表头数组中下标 struct CTNode*next;/指向下一孩子结点*ChildPtr;typedef struct TELemType data;/数据域 ChildPtr*firstchild;/指向第一个孩子结点CTBox;typedef struct CTBox nodeMAX_TREE_SIZE int n,rCTree;abcdefhgi6012345789acdefghibdata f.c.2 3 4 5 9 7 8 6如何找双亲如何找双亲结点结点孩子链表孩子链表612345789acdefghibdataf.c.2 3 4 5 9 7 8 6012235551parentabcdefhgi带双亲的孩子链表带双亲的孩子链表孩子兄弟表示法（二叉树表示法）孩子兄弟表示法（二叉树表示法）abcdefhgi a b c d e f g h iz用二叉链表作树的存储结构，链表中每个结点的两个指针域分别指向其第一个孩子结点和下一个兄弟结点typedef struct CSNode TElemTypedata;struct node *firstchild,*nextsibling;CSNode,*CSTree;z特点：操作容易、破坏了树的层次森林与二叉树的转换森林与二叉树的转换z由于树和二叉树都可以用二叉链表作为存储结构，则以二叉链表作为媒介可导出树与二叉树之间的一个对应关系z同样可以导出森林与二叉树的对应关系树与二叉树对应树与二叉树对应ACBED树ABCDE二叉树 A B C D E A B C D E A B C D E 对应存储存储解释解释森林与二叉树的对应森林与二叉树的对应森 林ACBDEFGIHJ各树对应的二叉树EFACBDGIHJ森林对应的二叉树EFACBDGIHJ将树根相连ABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHI树转换成的二叉树其右子树一定为空将树转换成二叉树将树转换成二叉树z加线：在兄弟之间加一连线z抹线：对每个结点，除了其左孩子外，去除其与其余孩子之间的关系z旋转：以树的根结点为轴心，将整树顺时针转45ABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHI将二叉树转换成树将二叉树转换成树z加线：若p结点是双亲结点的左孩子，则将p的右孩子，右孩子的右孩子，沿分支找到的所有右孩子，都与p的双亲用线连起来z抹线：抹掉原二叉树中双亲与右孩子之间的连线z调整：将结点按层次排列，形成树结构ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ森林转换成二叉树森林转换成二叉树z将各棵树分别转换成二叉树z将每棵树的根结点用线相连z以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树型结构ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ二叉树转换成森林二叉树转换成森林z抹线：将二叉树中根结点与其右孩子连线，及沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树z还原：将孤立的二叉树还原成树森林转换为二叉树的形式定义森林转换为二叉树的形式定义z如果F=T1,T2,Tm是森林，则可按如下规则转换成一棵二叉树B=(root,LB,RB)。若F为空，即m=0，则B为空树若F非空，即m!=0，则B的根root为森林中第一颗树的根ROOT(T1)；B的左子树LB是从T1中根结点的子树森林F1=T11,T12,T1m1 转换而成的二叉树B的右子树RB是从森林F1=T2,T3,Tm 转换而成的二叉树二叉树转换为森林的形式定义二叉树转换为森林的形式定义z如果B=(root,LB,RB)是一棵二叉树，则可按如下规则转换成森林F=T1,T2,Tm。若B为空，则F为空若B非空，则F中第一颗树T1的根ROOT(T1)即为二叉树B的根root；T1中根结点的子树森林F1是由B的左子树LB转换而成的森林F中除T1外其余的树组成的森林F=T2,T3,Tm是由B的右子树RB转换而成的森林树和森林的遍历树和森林的遍历z树的遍历先根（序）遍历：先访问树的根结点，然后依次先根遍历根的每棵子树后根（序）遍历：先依次后根遍历每棵子树，然后访问根结点按层次遍历：先访问第一层上的结点，然后依次遍历第二层，第n层的结点z森林的遍历先序遍历森林访问森林中第一颗树的根结点先序遍历第一颗树中根结点的子树森林先序遍历除去第一颗树之后剩余的树构成的森林中序遍历森林中序遍历森林中第一颗树的根结点的子树森林访问第一颗树的根结点中序遍历除去第一颗树之后剩余的树构成的森林遍历的关系遍历的关系z当森林转换为二叉树时森林的先序和中序遍历等于对应的二叉树的先序和中序遍历z当以二叉链表作为树的存储结构时树的先根遍历和后根遍历可借用二叉树的先序遍历和中序比那里的算法实现例题例题 选择题选择题 1/3z设X是树T中的一个非根结点，B是T所对应得二叉树，在B中，X是其双亲的右孩子，下列结论正确的是A在树T中，X是其双亲的第一个孩子。B在树T中，X一定无右边兄弟。C在树T中，X一定是叶子结点。D在树T中，X一定有左边兄弟。z分析：该题口主要考查树和二叉树的转换。根据树和二叉树转换的规则可以得到D为正确答案。例题例题 选择题选择题 2/3z设森林中有3棵树，其中第1、第2和第3棵树的结点个数分别为n1、n2、n3，则与森林对应的二叉树中根结点的右子树上的结点个数是A.n1B.n1+n2C.n3D.n2+n3z分析：该题主要考查森林和二叉树之间的转换关系。森林中的第一棵树对应于二叉树根结点及其左子树，第2和第3棵树对应于二叉树中根结点的右子树，则其结点个数为n2+n3。答案为D。例题例题 选择题选择题 3/3z树的先根序列和其对应的二叉树的 是一样的，树的后根序列和其对应的二叉树的 是一样的。A先序序列B中序序列C后序序列D按层次遍历序列z分析该题主要考查树和二叉树的转换关系。考虑树的根结点及其n个子树，当转换为二叉树后，根结点和最左子树的根结点的位置不变，而其它子树的根结点都成为其相邻左子树根结点的右孩子。这样的转换是递归过程。观察这样的结构变化，答案为A,B。例题例题 判断题判断题 1/1z将一棵树转换成二叉树后，根结点没有左子树。z错误z分析：该题主要考查树和二叉树的转换。树转换成二叉树满足“左孩子，右兄弟”规则。只有当树结点个数为1时，树转换成二叉树后，根结点没有左子树。例题例题 填空题填空题 z1森林T转化为二叉树B,B中某结点在森林中为叶子结点的条件为 。B中左子树为空的结点分析：该题主要考查森林和二叉树的转化。当B中左子树为空时，意味着该结点没有孩子结点。z设F是一个森林，B是由F转换得到的二叉树，F中有n个非终端结点，则B中右指针域空的结点有 个。n+1分析该题主要考查森林和二叉树的转化。例题例题 应用题应用题 1/2z将该树转换为二叉树例题例题 应用题应用题 2/2z求各树的先根序列和后根序列z求森林的先序和后序序列ABCDEFGHIJKLMPQRNOBDEFCA IJKHG QRPMNOLABCDEFGHIJKLMPQRNOBDEFCAIJKHGQRPMNOL习题习题z填空题1如果T1是由树T转换而来的二叉树，那么对T中结点的后序遍历就是对T1中结点的 遍历。2树在计算机内的存储结构有 ，和 。z应用题将该森林转换为二叉树6.6 哈夫曼树及其应用哈夫曼树及其应用z最优二叉树（哈夫曼树）z哈夫曼编码算法6.12算法6.13*z哈夫曼编码实例最优二叉树最优二叉树z从树的一个结点到另一个结点之间的分支构成两个结点之间的路径路径z路径上的分支数称为路径长度路径长度z从树根到每一个结点的路径长度之和称为树的树的路径长度路径长度z完全二叉树是路径长度最短的二叉树z结点的带权路径长度结点的带权路径长度为从该结点到树根之间的路径长度与结点上权的乘积z树的带权路径长度树的带权路径长度为树中所有叶子结点的带权路径长度之和。记为WPLzWPL最小的二叉树称为最优二叉树最优二叉树或哈夫曼树哈夫曼树具有不同带权路径长度的二叉树具有不同带权路径长度的二叉树z4个叶子结点a、b、c、d，分别带权7、5、2、4。它们的带权路径长度计算。z(a)WPL=7x2+5x2+2x2+4x2=36z(b)WPL=7x3+5x3+2x1+4x2=46z(c)WPL=7x1+5x2+2x3+4x3=35abcd7524abcd7524abcd7524最优二叉树应用之一最优二叉树应用之一z用哈夫曼树可以得到判定问题的最佳判定算法a60不及格a70a80a90及格中等良好优秀分数0-5960-6970-7980-8990-100等级(概率)不及格(5%)及格(15%)中等(40%)良好(30%)优秀(10%)a60不及格a80a70a90及格中等良好优秀构造哈夫曼树构造哈夫曼树z哈夫曼算法根据给定的n个权值w1,s2,wn构成n颗二叉树的集合F=T1,T2,Tn,其中每颗二叉树Ti中只有一个带权为wi的根结点，其左右子树均空。在F中选取两颗根结点的权值最小的树作为左右子树构造一颗新的二叉树，且置新的二叉树的根结点的权值为其左右子树上根结点的权值之和。在F中删除这两颗树，同时将新得到的二叉树插入F中重复以上两步，直到F只含一颗树为止，即哈夫曼树例a7b5c2d4a7b5c2d46a7b5c2d4611a7b5c2d461118a7b5c2d4例 w=5,29,7,8,14,23,3,1151429 7823 3111429 7823 1135887151429233581111358191429238715113581929 23148715292914871529113581923421135819234229148715295811358192342291487152958100等级分数段比例ABCDE05960697079 8089 901000.050.150.400.300.10a60a90a80a70EYNDYNCYNBYNA70a80a60CYNBYNDYNEYNA80a9060a70EADECa80a70a60a90EYNDYNCYNBYNAHuffman树应用树应用 最佳判定树最佳判定树编码思想编码思想z前缀编码任何一个字符的编码都不是另一个字符的编码的前缀的编码方案z利用二叉树可以实现前缀编码从根到叶子的路径即为叶子所