二叉树教案.ppt

二叉树 二叉树 主要内容 二叉树定义、基本概念和性质 二叉树的存储结构 二叉树的操作（遍历、查找、删除） 实践项目：二叉树操作演示程序 项目拓展：对二叉树操作演示程序进行修改 二叉树定义 二叉树(Binary Tree)：或者是一棵空树，或者是一棵由一个根结点和两棵互不相交的左子树和右子树所组成的非空树，左子树和右子树又同样都是二叉树 特征： 每个结点最多只有两棵子树 子树有左右之分，其次序不能任意颠倒 二叉树的五种基本形态 满二叉树 除了叶结点外每一个结点都有左右孩子且叶结点都处在最底层的二叉树称为满二叉树。如右上图。 满二叉树的特点： （1） 每一层上的结点数都达到最大值。即对给定的高度，它是具有最多结点数的二叉树 （2） 满二叉树中不存在度数为1的结点，每个分支结点均有两棵高度相同的子树，且树叶都在最下一层上。 完全二叉树 只有最下面的两层结点度小于2，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树称为完全二叉树 。如右上图。 完全二叉树的特征： （1）在满二叉树的最下一层上，从最右边开始连续删去若干结点后得到的二叉树仍然是一棵完全二叉树。 （2） 在完全二叉树中，若某个结点没有左孩子，则它一定没有右孩子，即该结点必是叶结点 。 平衡二叉树 平衡二叉树，又称AVL树。它或者是一棵空树，或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的高度之差之差的绝对值不超过1，这样的二叉树就是平衡二叉树。 右图是一个平衡二叉树。 二叉树的性质 (1) 一颗非空二叉树的第i层的结点总数不超过2i-1（i=0）； (2) 深度为h的二叉树最多有2h-1个结点(h=1)，最少有h个结点； (3) 对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0= N2+1； (4) 具有n个结点的完全二叉树的深度k为Log2n+1 二叉树的存储结构 顺序存储结构 链式存储结构 顺序存储结构 顺序存储结构 顺序存储结构 顺序存储结构的优点和缺点分析 （1）对完全二叉树而言，顺序存储结构既简单又节省存储空间。 （2）一般的二叉树采用顺序存储结构时，虽然简单，但易造成存储空间的浪费。最坏的情况下，一个深度为k且只有k个结点的右单支树需要2k-1个结点的存储空间。 (3) 在对顺序存储的二叉树做插入和删除结点操作时，要大量移动结点。 二叉树的链式存储结构 二叉树的遍历 前序遍历二叉树 中序遍历二叉树 后序遍历二叉树 层序遍历二叉树 前序遍历 中序遍历 后序遍历 层序遍历 ABCDEFG 课堂练习 写出左图二叉树前序、中序、后序、层序遍历的序列。 前序遍历递归算法步骤 if(当前结点不为空){ 访问该结点 递归遍历该结点的左子树 递归遍历该结点的右子树 } 中序遍历递归算法步骤 if(当前结点不为空){ 递归遍历该结点的左子树 访问该结点 递归遍历该结点的右子树 } 后序遍历递归算法步骤 if(当前结点不为空){ 递归遍历该结点的左子树 递归遍历该结点的右子树 访问该结点 } 层序遍历算法步骤 1 建立一个队列Queue 2 根结点进队 3 While(队列不空){ 1）出队一个结点 2）输出该结点信息 3）该结点左孩子进队 4）该结点右孩子进队 } 前序遍历的非递归算法步骤 1创建一个栈stack 2根结点进栈 3while(栈不空){ 出栈一个结点 输出该结点信息 该结点右孩子进栈 该结点左孩子进栈 } 二叉树的查找 按照某一种遍历方式来查找结点: C 二叉树的删除 实践项目：二叉树操作演示程序 例题4-2：编一程序实现对右图给出的二叉树进行遍历、查询和删除。 1 调试程序 2 讨论分析代码 3 总结设计思路与实现步骤 4 改造拓宽，对程序进行修改 项目拓展 修改程序 在BTree 类中增加方法,可计算树中结点总数 在BTree 类中增加方法,可计算树中叶子结点结点个数 小结 二叉树基本概念和性质 二叉树的遍历(四种,算法思路和实现代码) * * 二叉树 (1) (2) (3) (4) (5) B D E A C F G G F E D C B A 对于完全二叉树，树中结点序号与数组下标之间可以建立唯一的逻辑关系，既能节省存储空间，又能利用数组下标来确定结点在二叉树中的位置，以及结点之间的关系。 0 1 2 3 4 5 6 B D E A C F G 对于非完全二叉树，将树中结点按其在相应的完全二叉树中的位置序号编号，然后按照结点序号与数组下标之间建立唯一的逻辑关系。可