[工学]数据结构C语言第六章.ppt

第六章 树和二叉树 本章主要内容: 树的概念和基本术语 二叉树 遍历二叉树和线索二叉树 树与森林 哈夫曼树与哈夫曼编码 树的结构定义是一个递归的定义，即在树的定义中又用到树的概念，它表明了树的固有特性。树还可有其它的表示形式： (1)树型表示法：〇结点，连线，结点间关系，隐含方向。 (2)以嵌套集合的形式表示（文氏图） (即是一些集合的集体，对于其中任何两个集合，或者不相交，或者一个包含另一个) ； (3) 以广义表的形式表示：根作为由子树森林组成的表的名字写在表的左边； (A(B(E(K , L) , F) , C(G) ,D(H(M) , I , J))) (4) 凹入表示法(类似书的编目) 二、树的基本术语 结点：数据元素的内容及其指向其子树的分支统称为结点。 结点的度：结点的分支数（或某结点的子树个数）。 终端结点（叶子）： 度为0的结点。 非终端结点（分支结点）：度不为0的结点。 树的度：树中所有结点的度的最大值。 结点的层次： 树中根结点的层次为1，根结点的子树的根为第2层，以此类推。 树的深度或高度：树中所有结点层次的最大值。 有序树、无序树：如果树中各结点的子树从左向右的排列有一定的顺序，不得互换，则称为有序树，否则称为无序树。 森林：是m（m≥0）棵互不相交的树的集合。 在树结构中，结点之间的关系又可以用家族关系描述，定义如下： 孩子、双亲：结点的子树的根称为该结点的孩子，而该结点又被称为孩子的双亲。 子孙：以某结点为根的子树中的所有结点都称为该结点的子孙。 结点的祖先：从根结点到该结点路径上的所有结点。 兄弟：同一个双亲的孩子之间互为兄弟。 堂兄弟：双亲在同一层的结点互为堂兄弟。 树和线性结构的比较 推论： 树的四个性质 性质1：树中的结点数等于所有结点的度数加1。 性质2：度为m的树中第i层上至多有mi-1个结点（i ? 1）。 性质3：高度为h的m叉树至多有(mh-1)/(m-1)个结点。 性质4：具有n个结点的m叉树的最小高度为「logm(n(m-1)+1) 。 性质2：深度（或高度）为 k 的二叉树至多有2k-1个结点(k ? 1)。 证明：由性质1可见，深度为k的二叉树的最大结点数为 从以上性质可以得到结论： 1.有n个结点的二叉树最多有n层，最少有?log2n? +1层（完全二叉树达到最少值）； 2. 完全二叉树中度为1的结点最多为1个； 3.?具有n个结点的完全二叉树，编号最大的非叶子结点是?n/2? ，编号最小的叶子结点是?n/2?+1 ； 4.完全二叉树中度为1的结点数为(n+1)mod 2，度为0的结点数为?n/2?，度为2的结点数为?n/2?-1 。 5.完全二叉树中的叶子结点只可能在层次最大的两层上出现；对任意结点，若右分支下子孙的最大层次为L，则其左分支下子孙的最大层次必为L或L+1。 例1：假定一棵树的广义表表示为（A（B（C，D（E，F，G），H（I，J）））），则度为3的结点数有( )个。 例2：在一棵度为3的树中，度为3的结点数为2，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（ ）。 例3：一棵深度为6的完全二叉树的第6层有7个结点，则共有（ ）个结点，其中度为1的结点有（ ）个，度为0的结点有（ ）个，度为2的结点有（ ）个，编号最大的非叶子结点是（ ），编号最小的叶子结点是（ ）。 例4：深度为k的完全二叉树至少有( )个结点，至多有( )个结点。 例5：深度为7的完全二叉树，第7层上有5个结点，该树共有 个结点。 例6：按二叉树的定义，具有3个结点的二叉树有( ) 种。 ? A、3 B、4 C、5 D、6 例7：一棵深度为5的完全二叉树的第5层有5个结点，则叶子结点有 个。 三、二叉树的存储结构 上节内容复习：树和二叉树的定义， 树和二叉树的性质， 二叉树的存储方法。 本节内容：二叉树的遍历和线索二叉树 教学重点难点： 掌握遍历二叉树的方法 6.3 遍历二叉树 二叉树是一种非线性的数据结构，在对它进行操作时，总是需要逐一对每个数据元素实施操作，这样就存在一个操作顺序问题，由此提出了二叉树的遍历操作。 所谓遍历二叉树(Traversing Binary Tree)就是按某种顺序访问二叉树中的结点，使得每个结点均被访问一次，而且仅被访问一次。 遍历对线性结