资源描述：
《第六章+树和二叉树》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第六章树和二叉树6.1树的定义和基本概念6.2二叉树6.2.1二叉树的定义6.2.2二叉树的性质6.2.3二叉树的存储结构6.3遍历二叉树6.3.1遍历二叉树6.3.2线索二叉树16.4树和森林6.4.1树的存储结构6.4.2森林与二叉树的转换6.4.3树和森林的遍历6.6赫夫曼树及其应用6.6.1最优二叉树（赫夫曼树）6.6.2赫夫曼编码2学习重点了解二叉树的结构特性线熟悉二叉树的各种存储结构的特点熟练掌握二叉树的三种遍历算法线索二叉树了解最优树的特性,掌握建立最优树及哈夫曼编码的方法3树型结构是一类重要的非线性结构。树型结构是结点之间有分支，并且具有层次关系的结
2、构，它非常类似于自然界中的树。树结构在客观世界中是大量存在的，例如家谱、行政组织机构都可用树形象地表示。树在计算机领域中也有着广泛的应用，例如在编译程序中，用树来表示源程序的语法结构；在数据库系统中，可用树来组织信息；在分析算法的行为时，可用树来描述其执行过程等等。4树的定义：树是n（n≥0）个结点的有限集合，在任一棵非空树中：(1)有且仅有一个称为根(root)的结点。(2)其余结点可分为m个互不相交的子集T1,T2,T3…Tm，其中每个子集又是一棵树，并称其为子树(Subtree)。特点：树中至少有一个结点——根树中各子树是互不相交的集合1.树的定义5A只有根结
3、点的树ABCDEFGHIJKLM有子树的树根子树6下图是一棵树T：T={A,B,C,D,E,F,G,H,I,J,K,L,M}A是根，其余结点可以划分为3个互不相交的集合T1={B,E,F,K,L},T2={C,G},T3={D,H,I,J,M}集合T1,T2,T3本身又是一棵树,它们是A的子树。JIACBDHGFEKLMT11={E,K,L}，T12={F}，T11,T12是B的子树。例如,对于T1，B是根，其余结点可以划分为2个互不相交的集合：7从逻辑结构看：1）每棵树有且仅有一个根结点；2）除根结点外，其余结点都有且仅有一个直接前驱；3）树的每个结点可以有零个或
4、多个后继4）除根外的其他结点，都存在唯一一条从根到该结点的路径；5）树是一种分支结构。JIACBDHGFEKLM82.树的应用1）树可表示具有分支结构关系的对象例1学校的组织结构图：…经管学院软件学院外语学院软件工程专业软件背景专业软件+桥梁软件+道铁华东交通大学92）树是常用的数据组织形式：有些数据元素之间并不存在分支结构关系，但是为了便于管理和使用数据，将它们用树的形式来组织。例2计算机的文件系统：文件夹文件夹文件夹文件夹11121314文件夹1文件夹2文件3文件4C103.树的表示方法1）图示表示：2）嵌套集合表示：JIACBDHGFEKLMAEDHJIKLM
5、FGCB113）广义表的表示形式：(A(B(E(K,L),F)),C(G),D(H(M),I,J))ABEKLFCGDHMJI4）凹入表示法：3.树的表示方法12树的结点(node)：包含一个数据元素，及若干指向其子树的分支。4.树的有关术语JIACBDHGFEKLM例如：结点B,C,D是A的孩子，A是B,C,D的双亲。结点K,L是E的孩子，E是K,L的双亲。双亲结点：B结点是A结点的孩子，则A结点是B结点的双亲；孩子结点：结点的子树的根称为该结点的孩子；13兄弟结点：同一双亲的孩子之间互称兄弟；B,C,D互为兄弟；E,F互为兄弟；H,I,J互为兄弟.JIACBDH
6、GFEKLM祖先结点：从根到该结点所经分支上的所有结点。M的祖先为A,D,H。G的祖先为A,C。子孙结点：以某结点为根的子树中任一结点都称为该结点的子孙。例如：B的子孙为E,K,L,F。A的子孙为：B,C,D,E,F,G,H,I,J,K,L,M堂兄弟结点：其双亲在同一层的结点互称堂兄弟,结点G与E,F,H,I,J互为堂兄弟。14结点的度：结点拥有的子树的个数。结点A的度为3;结点B的度为2;结点M的度为0。叶子结点(终端结点)：是度为0的结点。叶子有：K，L，F，G，M，I，J。分支结点(非终端结点)：度不为0的结点。树的度：树内各结点的度的最大值。图示的树的度为3
7、。JIACBDHGFEKLM15结点的层次：根结点为第一层，根的孩子结点为第二层，依次类推。若某结点在第L层，其子树的根就在第L＋1层。树的深度：树中结点的最大层次。图示的树的深度为4。JIACBDHGFEKLM16有序树：其子树从左至右是有次序的，不能互换。最左边的子树的根称为第一个孩子，最右边的子树的根称为最后一个孩子。如：二叉树。无序树：不考虑子树的顺序；森林：互不相交的树集合；森林和树之间的联系是：一棵树去掉根后，其子树构成一个森林；一个森林增加一个根结点成为树。17二叉树的概念二叉树的性质二叉树的存储结构二叉树的遍历二叉树18二叉树在树结构的应用中起着
