授课时间1024第13次课

1、 授课时间 10 24 第 13 次课 授课章节第六章 树和二叉树任课教师及职称郑志华教学方法与手段多媒体课时安排2使用教材和主要参考书数据结构（C语言版）严蔚敏著，清华大学出版社教学目的与要求：第六章 树和二叉树6.1 树的定义和基本术语：6.2 二叉树6.2.1二叉树定义；教学重点，难点：1.树和二叉树的定义；二叉树的性质教学内容：第六章 树和二叉树6.1 树的定义和基本术语一、树的定义说明数据结构中允许空树存在。一、树的定义二、树的几个基本术语二、树的几个基本术语三、树的基本运算四、树的ADT五、树的三种表示树形表示文氏图表示凹入表表示嵌套括号表示例 一棵具有如下逻辑结构的树 T=(K,

2、V) K=a, b, c, d, e, f, g, h, i, j N=<a, b>, <a, c>, <b, d>, <b, e>, <b, f>, <c, g>, <c, h>, <e, i>, <e, j> 例 一棵具有如下逻辑结构的树 T=(K,V) K= a, b, c, d, e, f, g, h, i, j N= <a, b>, <a, c>, <b, d>, <b, e>, <b, f>, <c, g>

3、;, <c, h>, <e, i>, <e, j> 树形表示例 一棵具有如下逻辑结构的树 T=(K,V) K= a, b, c, d, e, f, g, h, i, j N= <a, b>, <a, c>, <b, d>, <b, e>, <b, f>, <c, g>, <c, h>, <e, i>, <e, j> 文氏图表示例 一棵具有如下逻辑结构的树 T=(K,V) K= a, b, c, d, e, f, g, h, i, j N= <a,

4、 b>, <a, c>, <b, d>, <b, e>, <b, f>, <c, g>, <c, h>, <e, i>, <e, j> 凹入表表示例 一棵具有如下逻辑结构的树 T=(K,V) K= a, b, c, d, e, f, g, h, i, j N= <a, b>, <a, c>, <b, d>, <b, e>, <b, f>, <c, g>, <c, h>, <e, i>, <e,

5、 j> 嵌套括号表示a ( b ( d, e ( i, j ) , c (g, h)6.2 二叉树6.2.1 二叉树的定义定义：二叉树是 n(n>=0)个结点的有限集合，此集合 或是一个空集，或是由一个根结点及分别称为 左子树和右子树的互不相交的二叉树组成。注 二叉树的定义也是递归的，且二叉树可以为空。6.2.1 二叉树的定义二叉树的5种基本形态 二叉树结点的子树要区分左子树和右子树，即使只有一棵子树也要进行区分，说明它是左子树，还是右子树。这是二叉树与树的最主要的差别。6.2.1 二叉树的定义二叉树的运算求一个结点的父亲求一个结点的左儿子、右儿子创建一个二叉树插入左子树或右子树遍

6、历二叉树6.2.2 二叉树的性质性质1 在二叉树的第i层上至多有2i-1个结点(i>=1)。性质2 深度为k的二叉树至多有2k1个结点（k>=1)。性质3 对任何一棵二叉树，如果其终端结点数为n0， 度为2的结点数为n2，则n0n21。 否则，其左孩子是结点2i。 （3）如果2i1>n，则结点i无右孩子； 否则，其右孩子是结点2i1。完全二叉树的特点是：（1)所有的叶结点都出现在第k层或k1层。（2）对任一结点，如果其右子树的最大层次为1，则其左子树的最大层次为1或l1。 性质4：具有n个结点的完全二叉树的深度为 log2n1。符号x表示不大于x的最大整数。假设此二叉树的深度

7、为k，则根据性质2及完全二叉树的定义得到： 2k-11<n<=2k-1 或 2k-1<=n<2k取对数得到：k1<log2n<k 因为k是整数。所以有：klog2n1。性质5： 如果对一棵有n个结点的完全二叉树的结点按层序编号（从第1层到第【log2n】+1层，每层从左到右),则对任一结点i（1<=i<=n),有： （1）如果i1，则结点i无双亲，是二叉树的根；如果i>1，则其双亲是结点【i/2】。 （2）如果2i>n，则结点i为叶子结点，无左孩子；否则，其左孩子是结点2i。 （3）如果2i1>n，则结点i无右孩子；否则，其右孩

8、子是结点2i1。 在此过程中，可以从（2）和（3）推出（1），所以先证明（2）和（3）。 对于i1，由完全二叉树的定义，其左孩子是结点2，若2>n，即不存在结点2，此是，结点i无孩子。结点i的由孩子也只能是结点3，若结点3不存在，即3>n，此时结点i无右孩子。对于i>1，可分为两种情况： （1）设第j（1<=j<=log2n)层的第一个结点的编号为i，由二叉树的性质2和定义知i2j-1结点i的左孩子必定为的j1层的第一个结点，其编号为2j2×2j-12i。如果2i>n，则无左孩子：其右孩子必定为第j1层的第二个结点，编号为2i1。若2i+1>n，则无右孩子。 （2）假设第j（1<=j<=log2n)层上的某个结点编号为i（2e(j-1)<=i<=2ej-1),且2i1<n，其左孩子为2i，右孩子为2i1，则编号为i1的结点时编号为i的结点的右兄弟或堂兄弟。若它有左孩子，则其编号必定为2i22×（i1）：若它有右孩子，则其编号必定为2i32×（i1）1。当i1时，就是根，因此无双亲，当i>1时，如果i为左孩子，即2×（i/2)=i,则i/2是i的双亲；如果i为右孩子，i2p+1,i的双亲应为p，p（i1）/2=i/2. 证毕