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

1、树和二叉树-数据结构本章学习要点本章学习要点z掌握树和二叉树的性质，相关术语及基本概念。二叉树的两种存储方法，重点是链式存储据。二叉树三种顺序遍历及其递归实现算法。二叉树的层次遍历创建链式存储的二叉树的算法。中序线索二叉树的算法：中序线索二叉树上基本算法（遍历、求指定结点的前驱和后继、查找指定值的结点）。树的遍历算法（先根遍历、后根遍历）；森林的遍历算法（前序遍历，后序遍历）哈夫曼树的概念；哈夫曼树的构造算法；哈夫曼编码通过本章的算法的学习，让学生认识到递归定义的数据结构之下求解相应问题，思路清晰和简洁算法设计方法是采用递归的方式。z理解二叉树三种遍历的非递归算法及其与栈的关系在中序线索树指定

2、结点下插入新结点的算法，学会在复杂情形下分类讨论的方法。树的三种存储结构（双亲表示法、孩子表示法、孩子兄弟表示法）及各自的特点（优点、缺点）1.掌握树、森林和对应的二叉树相互转换算法。本章作业本章作业z6.3 6.5 6.7 6.12 z6.13 6.19 6.21 6.27 z6.29 6.42 6.43 本章教学重点和难点本章教学重点和难点z教学重点二叉树的性质；二叉树的链式存储。二叉树三种顺序遍历算法，遍历算法的应用。中序线索二叉树的算法及其简单应用。哈夫曼树的构造和编码算法注意程序实现方法教学难点二叉树性质的运用二叉树三种遍历的非递归算法。中序线索二叉树的理解及先序后序线索算法的实现。

3、1.二叉树中，学会递归的思想求解问题，用遍历的典型算法解决一些具体问题。第第6章树和二叉树章树和二叉树z树型结构是一类重要的非线性非线性数据结构。其中常见的是树树和二叉树二叉树树是以分支关系定义的层次结构z树结构在客观世界中广泛存在人类社会的族谱社会组织结构z在计算机领域编译程序中表示源程序的语法结构数据库中是信息的重要组织形式之一操作系统中的进程管理z本章主要讨论二叉树的存储及各种操作研究树和森林与二叉树的转换关系树的应用6.1树的定义和基本术语树的定义和基本术语z树(tree)是n(n0)个结点的有限集。z在任意一颗非空树中有且仅有一个特定的称为根(root)的结点;当n1时，其余结点可分

4、为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)

5、，对任意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)Pare

6、nt(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兄弟(

7、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

8、，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 Bin

9、aryTree数据对象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(&

10、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()/先序遍历二叉树先序遍历二叉

11、树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个结点。由于二叉树的每个结点的

12、度最多为2，故在第i层上的最大结点数为第i-1层上最大结点数的2倍，即2x2(i-1)-1=2i-1。证明完毕1231145897101415二叉树的性质（性质二叉树的性质（性质2）z深度为k的二叉树至多有2k-1个结点(k1)z证明由性质1可见，深度为k的二叉树的最大结点数为122)i(kk1ik1i1i层上的最大结点数第二叉树的性质（性质二叉树的性质（性质3）z对任何一颗二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1z证明设n1为二叉树T中度为1的结点数因为二叉树中所有结点的度均小于或等于2，则n=n0+n1+n2(1)分析分支数的关系，除了根结点外，其余结点都有

13、且只有一个分支进入。设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+1123114589

14、1213671014151231145891267101234567123456完全二叉树示例完全二叉树示例二叉树的性质（性质二叉树的性质（性质4）z具有n个结点的完全二叉树的深度为z证明假设深度为k，则根据性质2和完全二叉树的定义有于是k-1log2n1，则其双亲PARENT(i)是结点 。如果2in，则结点i无左孩子（结点i为叶子结点）；否则其左孩子LCHILD(i)是结点2i。如果2i+1n，则结点i无右孩子（结点i为叶子结点）；否则其右孩子RCHILD(i)是结点2i+1。1log2n1log2n2/i二叉树的存储结构二叉树的存储结构顺序存储结构顺序存储结构z存储顺序存储结构实现：按满

15、二叉树的结点层次编号，依次存放二叉树中的数据元素特点：结点间关系蕴含在其存储位置中浪费空间，适于存满二叉树和完全二叉树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,*r

16、child;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(

17、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*lch

18、ild,*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,

19、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完全

20、二叉树中，任何一个结点的度，或者为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个树枝

21、，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.36

22、z分析：该题主要考查完全二叉树的逻辑结构由二叉树的性质5可知，结点69的双亲结点编号为69/234。所以答案为B。例题例题 判断题判断题 1/1z1.完全二叉树中，若一个结点没有左孩子，则它必然是叶子结点。z正确z分析：该题口主要考查完全二叉树的逻辑结构。深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1到n的结点一一对应时，称为完全二叉树。根据此定义，若完全二叉树中某结点无左孩子，则其必定没有右孩子，因此是叶结点。所以这种说法是正确的例题例题 填空题填空题 1/4z1.一棵高度为H的满K叉树，按层次从1开始编号，则；z(1)第i层结点的数为()z(2)编号为

23、n的结点的父结点的编号为()z(3)编号为n的结点的第i个孩子的编号为()z(4)编号为n的结点有右兄弟的条件是(),右兄弟的编号为()z分析：该题主要考查对二叉树定义和性质的理解。z kn/)1(ki-1k(n-1)+1+ikknn/)1(n+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，所以二叉树中有个

24、 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分析与解答：该题主要考查树的基本概念和结构。根据两个等

25、式：求结点总数：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的结

26、点个数为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)哪

27、些是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、二叉树中至

28、少有一个结点的度为26.3 遍历二叉树和线索二叉树遍历二叉树和线索二叉树z遍历二叉树算法6.1 先序遍历二叉树算法6.2 中序遍历二叉树的非递归算法算法6.3 中序遍历二叉树的非递归算法算法6.4 先序创建二叉树z线索二叉树算法6.5 线索二叉树中序遍历算法6.6 中序线索二叉树算法6.7 中序线索二叉树遍历二叉树遍历二叉树z遍历按一定规律走遍二叉树的各个顶点，且使每一顶点仅被访问一次，即找一个完整而有规律的走法，以得到树中所有结点的一个线性排列z思路二叉树组成：左子树、根、右子树，如果能够依次遍历左子树、根和右子树这三部分，则能够遍历整个树z遍历方式：根据根的访问次序，分为3种先序遍历：访问

29、根结点,先序遍历左子树先序遍历右子树中序遍历：中序遍历左子树访问根结点中序遍历右子树后序遍历：后序遍历左子树后序遍历右子树访问根结点按层次遍历：从上到下、从左到右访问各结点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先序遍历：中序遍历：后序遍历：层次遍历

30、：-+a*b-c d/e f-+a*b-cd/ef-+a*b-c d/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-St

31、atus 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

32、(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);

33、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/whil

34、ereturn 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 Cr

35、eateBiTreez按先序遍历序列建立二叉树的二叉链表，已知先序序列为：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 线索二叉树

36、线索二叉树z定义：前驱与后继：在二叉树的先序、中序或后序遍历序列中两个相邻的结点互称为前驱与后继线索：指向前驱或后继结点的指针称为线索线索二叉树：加上线索的二叉链表表示的二叉树叫线索二叉树线索化：对二叉树按某种遍历次序使其变为线索二叉树的过程叫线索化z实现在有n个结点的二叉链表中必定有n+1个空链域在线索二叉树的结点中增加两个标志域Ltag和Rtaglchild:若 LTag=0,指向左孩子；若Ltag=1,指向其前驱rchild:若 RTag=0,指向右孩子；若Rtag=1,指向其后继z结点定义：lchildLtagdataRTagrchild线索二叉树图例线索二叉树图例ABCDE A B

37、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在线索树上进行遍历，只要找到序列中的第一个结点，然后依次找结点的后继直到其后继为空

38、为止。z如何找后继？（不是每个结点都记录了后继的。）z中序线索二叉树如果对应的TAG=1。则直接得到该结点的前驱或后继。否则：结点的后继：右子树遍历的第一个结点，即右子树最左下结点结点的前驱：左子树遍历的最后一个结点，即左子树最右下结点。z后序线索二叉树若结点为二叉树的根，后继为空。若结点是其双亲的右孩子或是其双亲的独生左孩子，后期为该结点的双亲若结点是其双亲的左孩子，且有右兄弟，则后继为双亲右子树上按后序遍历的第一个结点二叉树的二叉线索存储二叉树的二叉线索存储typedef enum PointerTagLink,Thread;typedef struct BiTNodeTElemType

39、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

40、-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-R

41、Tag=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-r

42、child=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都不相同

43、B先序和中序相同，而与后序不同C完全相同D中序和后序相同，而与先序不同z分析：该题主要考查二叉树的遍历。z无论哪种遍历所得的序列都是在“左”、“右”两结点的空隙中插入“根”结点的排列，即左、右结点的顺序固定不变，改变的是“根”结点，叶子结点的先后顺序都不变。z答案为C。例题例题 选择题选择题 3/5z3欲实现任意二叉树的后序遍历的非递归算法而不必使用栈结构，最佳方案是二叉树采用存储结构。A三叉链表B广义表C二叉链表D顺序z分析：该题主要考查二叉树的存储结构和非递归遍历算法。z此题答案为A。三叉链表是将双亲表示法和孩子兄弟表示法结合起来，既能方便地从双亲查找孩子，又能方便地从孩子查找例题例题 选

44、择题选择题 4/5z4一棵二叉树满足下列条件：对任一结点，若存在左、右子树，则其值都小于它的左子树上所有结点的值，而大于右子树上所有结点的值。现采用遍历方式就可以得到这棵二又树上所有结点的递减序列。A先序B中序C后序D层次z分析：该题主要考查二叉树的遍历。由于中序遍历的顺序是先中序遍历左子树，再访问根结点，最后中序遍历右子树。这样可以保证，对任一结点其左孩子总在它的左边，其右孩子总在它的右边。当二叉树满足题述条件时，其中序序列一定是个递减序列。z答案为B。例题例题 选择题选择题 5/5z5对含有几个结点的非空二叉树，采用任何一种遍历方式，其结点访问序列均相同。A.0B.1C.2D不存在这样的二

45、叉树z分析：该题主要考查二叉树的三种遍历次序的关系。三种遍历方式的不同点，在于访问根结点的时机不同。当一棵二叉树仅含一个根结点时，不管采用哪种遍历方式，所得到的结点序列总是相同的。z此题答案为B。例题例题 判断题判断题 1/4z1按中序遍历二叉树时，某个结点（有右子树）的直接后继是它的右子树中第一个被访问的结点。z正确z分析：该题主要考查二叉树的中序遍历。这种说法正确。因为中序遍历按LDR的顺序进行，若以某结点为其直接后继，必须是右子树中第一个被访问的结点。例题例题 判断题判断题 2/4z2有1个以上结点的二叉树，已知先序和后序遍历序列，能唯一确定一棵二叉树。z错误z分析：该题主要考查二叉树的

46、遍历的性质。这种说法不正确。如已知先序为 12，后序遍历为 21，则可以有两棵二叉树。例题例题 判断题判断题 3/5z3用二叉树的先序遍历和中序遍历可以导出二叉树的后序遍历。z正确z分析：该题主要考查二叉树的遍历和逻辑结构。用二叉树的先序遍历和中序遍历可以确定二叉树的逻辑结构，就可以进一步导出二叉树的后序遍历。通常已知二叉树的先序遍历和后序遍历，无法确定一棵二叉树。例题例题 判断题判断题 4/4z4若一个叶子结点是某二叉树中序遍历序列的最后一个结点，那么它也是该二叉树的先序遍历序列的最后一个结点。z正确z分析：该题主要考查二叉树的遍历。当一个叶子结点是某二叉树中序遍历的最后一个结点，则它一定位

47、于二叉树的右子树上最右端，无论先序遍历或中序遍历，右子树上的最右端的叶子结点肯定最后访问。若题中的叶子结点替换成普通结点，则命题不成立。例题例题 填空题填空题z1.N个结点的二叉树按某种遍历规则对结点从1到N依次递增编号，如果z(1)任一结点的编号等于它的左子树中的最小编号减1，则为遍历；z(2)某结点右子树中最小编号等于左子树中的最大编号加1，则为遍历。z答案：先序，后序。z分析：该题主要考查二叉树的结构和遍历。z对于先序遍历，因为首先访问根结点，再先序遍历左子树，最后先序遍历右子树，所以根结点编号等于左子树的根结点编号减1。z对于后序遍历，因为首先后序遍历左子树，然后后序遍历右子树，最后访

48、问根结点，所以右子树中最小编号等于左子树中的最大编号加1。例题应用题例题应用题 1/2z1满足下列条件的非空二叉树具有什么形状？(1)先序和中序相同(2)中序和后序相同(3)先序和后序相同z分析：该题主要考察二叉树的结构和遍历性质。(1)只有一个结点或没有左子树的二叉树(2)只有一个结点或没有右子树的二叉树(3)只有一个结点的二叉树例题应用题例题应用题 2/2z2已知二叉树左右子树都含有m个结点，当m鹅时，试构造满足如下要求的所有二叉树。z(1）左右子树的先序与中序序列相同。z(2）左子树的中序与后序序列相同，右子树的先序与中序序列相同。z分析：该题由上题引中得到，主要考查二叉树的结构和遍历的

49、性质如图。例题算法设计题例题算法设计题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);r

50、eturn(like1&like2);/BiLike习题习题 填空题z1 某二叉树的先序遍历序列和后序遍历序列正好相反，则此二叉树一定是()A空或只有一个结点B完全二叉树C单支树D高度等于结点数z2在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序()。A都不相同B完全相同C先序和中序相同，而与后序不同D中序和后序相同，而与先序不同填空题z1有()种不同形态的二叉树可以按照中序遍历得到相同的abc序列。z2已知二叉树先序为ABDEGCF，中序为DBGEACF，则后序一定是()判断题z1二叉树线索化后一定不存在空指针域。z2非空的二叉树一定满足：某结点若有左孩子，则其中序前驱一