高中二年级下学期信息科技《用抽象数据类型表示二叉树》教学课件

选择性必修1《数据与数据结构》4.3用抽象数据类型表示二叉树|一、树tree|树tree|线性关系：即每一个数据元素通常只有一个前驱（除第一个元素外）和一个后继（除最后一个元素外）；如：队列，栈非线性结构：至少存在一个结点（数据元素）有多于一个前驱或后继的数据结构；如：树，图树tree|在我们日常生活中，树形结构广泛存在。王贵王永胜王家莉王永前王家栋王家梁王家辉家族成员关系树树tree1.树的定义树是n(n>0)个结点的有限集，在任意一棵非空树中：①有且仅有一个特定的结点称为根；②当n>1时，其余结点分为m(m>0)棵互不相交的有限子树，每棵子树又是一棵树。树tree2.结点的分类

①根结点：没有父亲的结点。在树中有且仅有一个根结点。②分支结点：除根结点外，有孩子的结点称为分支结点。③叶结点：没有孩子的结点称为叶结点。如w,h,e等为叶结点3.有关度的定义①结点的度：一个结点的子树数目称为该结点的度。如图中结点i度为3，结点t的度为2，结点b的度为1，所有树叶的度为0。②树的度：所有结点中最大的度称为该树的度(也叫树的宽度），图中树的度为3。树tree4.树的深度（高度）树是分层次的。结点所在的层次是从根算起的。根结点在第一层，根的儿子在第二层，其余各层依次类推。同一父结点的所有结点构成兄弟关系树的层数称为树的深度(也称为树的高度)。上图中树的深度为55.森林所谓森林，是指若干棵互不相交的树构成的集合。如图去掉根结点r，其原来的三棵子树Ta，Tb，Tc就构成了森林，如图(c)二、二叉树Binarytree||二叉树Binarytree二叉树是一种很重要的树结构特点：每个结点最多有两个孩子，且其子树有左右之分（称为有序树，其次序不能任意颠倒）1256743|二叉树Binarytree1.二叉树的递归定义和基本形态二叉树是以结点为元素的有限集，可为空，或者满足以下条件：⑴有一个特定的结点称为根；⑵余下的结点分为互不相交的两个子集L和R，其中L是根的左子树；R是根的右子树；L和R分别又是一棵二叉树；由上述定义可以看出，二叉树和树是两个不同的概念，其区别为：⑴树的每一个结点可以有任意多个后继，而二叉树中每个结点的后继不能超过2个⑵树的子树可以不分次序（除有序树外）；而二叉树的子树有左右之分。我们称二叉树中结点的左后继为左儿子，右后继为右儿子。1256743|二叉树Binarytree下图列出二叉树的五种基本形态：空二叉树只有一个根结点的二叉树只有左子树的二叉树只有右子树的二叉树左、右子树均有的二叉树|二叉树Binarytree2.常见的两种二叉树⑴满二叉树：如果一棵深度为K的二叉树，共有2K-1个结点，即第i层有2i-1的结点，则称为满二叉树⑵完全二叉树：如果一棵二叉树最多只有最下面两层结点度数可以小于2，并且最下面一层的结点都集中在该层最左边的若干位置上，则称为完全二叉树注意：满二叉树一定是完全二叉树，但是完全二叉树不一定是满二叉树136754213675428910三、二叉树的抽象数据类型Abstractdatatypeofbinarytree|二叉树的抽象数据类型Abstractdatatypeofbinarytree|二叉树的抽象数据类型的数据部分为一棵用任一种方式表示的二叉树操作部分包括初始化二叉树、建立二叉树、遍历二叉树、查找二叉树、输出二叉树和清除二叉树等常用操作。下面给出二叉树的抽象数据类型的参考定义:二叉树的抽象数据类型Abstractdatatypeofbinarytree|四、二叉树的基本操作方法Basicoperationmethodofbinarytree|二叉树的基本操作方法Basicoperationmethodofbinarytree|二叉树的基本操作较多，下面以遍历为例，了解二叉树的基本操作方法。遍历是二叉树的一种基本操作，是指按一定的次序访问树中所有结点，并且每个结点的值仅被访问一次的过程。由于二叉树是非线性结构，因此二叉树的遍历实质上是将二叉树的所有结点转换成一个线性序列的过程。根据二叉树的递归定义，一棵非空二叉树由根结点、左子树和右子树所组成。因此，遍历一棵非空二叉树的问题可分解为三个子问题：访问根结点、遍历左子树、遍历右子树。若用L、D、R分别表示遍历左子树、访问根结点和遍历右子树，则对一棵二叉树的遍历有DLR、LDR、LRD、DRL、RDL、RLD六种情况，若限定先左后右，则只有前三种情况，分别称为前序遍历(或先根遍历)、中序遍历(或中根遍历)、后序遍历(或后根遍历)。二叉树的基本操作方法Basicoperationmethodofbinarytree|（1）前序遍历：根左右。即先遍历根结点，再遍历左子树，最后遍历右子树acfhgedbabdegcfh（2）中序遍历：左根右。即先遍历左子树，再遍历根结点，最后遍历右子树dbgeafhc（3）后序遍历：左右根。即先遍历左子树，再遍历右子树，最后遍历根结点dgebhfca课后任务|【表达式树】：我们可以分别用先序、中序、后序的遍历方法得出完全不同的遍历结果，如对于右图3种遍历结果如下，它们正好对应着表达式的3种表示方法。①-+a*b-cd/ef(前缀表示、波兰式)②a+b*c-d