树和二叉树教案1.doc

1、教学过程一、导入树是一类重要的非线性数据结构，是以分支关系定义的层次结构。在日常生活同学们经常见到树。树有一个树根。有许多树枝，在树枝上长有很多树叶。就象我们今天要讲的树，是一种层次结构。二、新授(一)树1 树的定义树（tree）是由 n (n0) 个结点组成的有限集合。它是树型结构的简称，是一种重要的非线性数据结构，应用广泛。如：磁盘上的文件目录结构、家族成员关系、单位的组织机构、书的内容组织、算术表达式等。任何一棵非空树是一个二元组：Tree = （root，F）其中：root被称为根结点，F被称为子树森林2 基本术语森 林：是m（m0）棵互不相交的树的集合有 向 树：有确定的根，树根和子

2、树根之间为有向关系（自上到下，自左到右）有 序 树：树中结点的各子树从左到右是有次序的，不能互换无 序 树：树中结点的各子树从左到右是没有次序的子 女：结点的子树的根是该结点的孩子双 亲：孩子结点的根结点兄 弟：具有同一双亲的结点堂 兄 弟：双亲在同一层的结点祖 先：从根到该结点所经历分支上的所有结点子 孙：以某结点为根的子树中的任一结点学生活动：请同学门总结树形与线形的异同(二) 二叉树1.二叉树的定义二叉树(BinaryTree)是n(n0)个结点的有限集，它或者是空集(n=0)，或者由一个根结点及两棵互不相交的、分别称作这个根的左子树和右子树的二叉树组成。2二叉树的五种基本形态二叉树可以

3、是空集；根可以有空的左子树或右子树；或者左、右子树皆为空。3二叉树不是树的特例 （1）二叉树与无序树不同 二叉树中，每个结点最多只能有两棵子树，并且有左右之分。二叉树并非是树的特殊情形，它们是两种不同的数据结构。（2）二叉树与度数为2的有序树不同在有序树中，虽然一个结点的孩子之间是有左右次序的，但是若该结点只有一个孩子，就无须区分其左右次序。而在二叉树中，即使是一个孩子也有左右之分。4、满二叉树和完全二叉树是二叉树的两种特殊情形。a、满二叉树 一棵深度为k且有2k-1个结点的二又树称为满二叉树。满二叉树的特点：（1） 每一层上的结点数都达到最大值。即对给定的高度，它是具有最多结点数的二叉树。（

4、2） 满二叉树中不存在度数为1的结点，每个分支结点均有两棵高度相同的子树，且树叶都在最下一层上。b、完全二叉树(Complete BinaryTree)若一棵二叉树至多只有最下面的两层上结点的度数可以小于2，并且最下一层上的结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树。特点：（1） 满二叉树是完全二叉树，完全二叉树不一定是满二叉树。（2） 在满二叉树的最下一层上，从最右边开始连续删去若干结点后得到的二叉树仍然是一棵完全二叉树。（3） 在完全二叉树中，若某个结点没有左孩子，则它一定没有右孩子，即该结点必是叶结点。5、二叉树的性质性质1 二叉树第i层上的结点数目最多为2i-1(i1)。性质2 深度为k的二叉树至多有2k-1个结点(k1)。性质3 在任意-棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则no=n2+1。性质4 具有n个结点的完全二叉树的深度为 小结：这节课介绍了树的一些基本术语，二叉树的概念和二叉树的基本性质，希望同学们牢记二叉树的基本性质。作业：习题五 1,2