数据结构第07次课_树A.pptVIP

每课一贴：一个人去买鹦鹉，看到一只鹦鹉前标：此鹦鹉会两门语言，售价二百元。另一只鹦鹉前则标有：此鹦鹉会四门语言，售价四百元。该买哪只呢？两只都毛色光鲜，非常灵活可爱。这人转啊转，拿不定主意。结果突然发现一只老掉了牙的鹦鹉，毛色暗淡散乱，标价八百元。这人赶紧将老板叫来：这只鹦鹉是不是会说八门语言？店主说：不。这人奇怪了：那为什么又老又丑，又没有能力，会值这个数呢？店主回答：因为另外两只鹦鹉叫这只鹦鹉老板。这故事告诉我们，真正的领导人，不一定自己能力有多强，只要懂信任，懂放权，懂珍惜，就能团结比自己更强的力量，从而提升自己的身价。相反许多能力非常强的人却因为过于完美主义，事必躬亲，什么人都不如自己，最后只能做最好的攻关人员，销售代表，成不了优秀的领导人。 ;数据结构课程的内容;第6章 树和二??树（ Tree Binary Tree ）;6.1 树的基本知识;1. 树的定义;2. 若干术语;2. 若干术语（续）;树的表示法有几种：;图形表示法：;广义表表示法;左孩子－右兄弟表示法; 树的抽象数据类型定义;3. 树的逻辑结构 ;讨论3：树的链式存储方案应该怎样制定？;解决思路：先研究最简单、最有规律的树，然后设法把一般的树转化为这种简单的树。;5. 树的运算 ;6.2 二叉树;1. 二叉树的定义;2. 二叉树的性质 (3+2);讨论3：二叉树的叶子数和度为2的结点数之间有关系吗？;满二叉树：一棵深度为k 且有2k -1个结点的二叉树。 （特点：每层都“充满”了结点）;对于两种特殊形式的二叉树（满二叉树和完全二叉树），还特别具备以下2个性质：;性质5: 对完全二叉树，若从上至下、从左至右编号，则编号为i 的结点，其左孩子编号必为2i，其右孩子编号必为2i＋1；其双亲的编号必为i/2（i＝1 时为根,除外）。 ;3. 深度为9的二叉树中至少有 个结点。 Ａ)２9 Ｂ)２8 Ｃ)９ Ｄ)２9－1;课堂讨论：;请注意叶子结点总数≠末层叶子数！ 还应当加上第k-1层（靠右边）的0度结点个数。 分析：末层的489个叶子只占据了上层的245个结点（?489/2? ) 上层（k=9)右边的0度结点数还有29-1-245=11个！