数据结构(树和叉树).pptVIP

数据结构 第6章树和二叉树 知识点 1、二叉树及二叉树的存储结构 2、二叉树的遍历 3、树的基本概念 树的遍历 4、哈夫曼树 难 点 1、二叉树遍历算法的设计 2、修改二叉树遍历算法，进行二叉树其它相关的操作，解决实际应用问题 第6章树和二叉树（要求） 1.???? 熟练掌握二叉树的结构特性，了解相应的证明方法。 2.???? 熟悉二叉树的各种存储结构的特点及适用范围。 3.???? 熟练掌握各种遍历策略的递归和非递归算法，了解遍历过程中“栈”的作用和状态，而且能灵活运用遍历算法实现二叉树的其它操作。层次遍历是按另一种有哪些信誉好的足球投注网站策略进行的遍历(补充)。 4.???? 熟练掌握二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法。二叉树的线索化过程是基于对二叉树进行遍历，而线索二叉树上的线索又为相应的遍历提供了方便。 5.???? 熟悉树的各种存储结构及其特点，掌握树和森林与二叉树的转换方法。建立存储结构是进行其它操作的前提，因此读者应掌握1至2种建立二叉树和树的存储结构的方法。 6.???? 学会编写实现二叉树的各种操作的算法。 7. 掌握建立哈夫曼编码的方法。 第6章树和二叉树 目录 6.1 树的定义和基本术语 6.2 二叉树 6.3 遍历二叉树和线索二叉树 6.4 树和森林 6.6 赫夫曼树及其应用 小结 习题与练习 6.1 树的定义和基本术语 一、树的定义 二、树的抽象数据类型定义 三、树的基本术语 一、 树的定义 非线性数据结构（树和图）：结构（定义）中至少存在一个结点，它不只一个前驱或后继； 树形结构是一类重要的非线性结构，其中以二叉树最为常用； 树形结构是结点间有分支的、层次关系的结构； 树形结构特点：每个结点可有不只一个直接后继，除根外的所有结点都有且只有一个直接前驱； 树结构在客观世界中广泛存在，如人类社会的族谱和各种社会组织机构等都可用树来形象表示。 树的图示： 一、树的定义 树（Tree）（递归定义）： 树是 n（n≥0）个结点的有限集。 在任意一棵非空树中：（1）有且仅有一个特定的称为根（Root）的结点；（2）当n1时，其余结点可分为 m（m0）个互不相交的有限集T1、T2、…、Tm，其中每一个集合本身又是一棵树，并且称为根的子树(SubTree)。 说明：树中，每个结点被定义为它的每个子树的根结点的前驱，它的每个子树的根结点为它的后继。 一、树的定义 树的表示形式： （1）树形表示法：（最常用） 树的表示 （2）嵌套集合表示法：（集合的集体，对于任两个集合，或不相交，或一个包含另一个） 树的表示 （3）广义表：根作为由子树森林组成的表的名字写在表的左边。A(B(E(K,L),F),C(G),D(H(M),I,J)) 树的表示 （4）凹入表示法： 二、抽象数据类型树的定义 抽象数据类型树的定义：（P118-119） 三、树的基本术语 1、结点 2、结点的度(Degree) 3、叶子(Leaf)（终端结点） 4、分支结点（非终端结点） 5、内部结点 6、树的度 7、孩子(Child)、双亲(Parent) 8、兄弟(Sibling) 9、祖先、子孙 10、结点的层次(Level) 11、堂兄弟 12、树的深度(Depth) 13、有序树、无序树 14、森林(Forest) 树的概念 示例 6.2 二叉树 一、二叉树的定义 二、二叉树的性质 三、二叉树的存储结构 一、 二叉树的定义 1、二叉树（Binary Tree）：每个结点至多只有两棵子树的树型结构。 特点：（１）不存在度大于２的结点； 　　　（２）子树次序不能颠倒，有左右之分。 　　　（３）与一般树的区别：当只有一个孩子结点时，二叉树区分左右顺序，一般树不区分。 2、二叉树的抽象数据类型定义（P121-123） 一、二叉树的定义 3、二叉树的五种基本形态 二、二叉树的性质 性质1 在二叉树的第 i 层上至多有2 i-1 个结点(i≥1)。 性质2 深度为k的二叉树至多有2k-1个结点(k ≥1)。 证明：由性质１得： 最多的结点数（每一层为最大结点数）： 　　2０＋21 ＋ 2２ ＋…＋ 2k-1 ＝ 2k-1 （等比数列求和） 性质3 对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1 二、二叉树的性质 完全二叉树和满二叉树 满二