第四章树课件.pptVIP

第四章 树 树形结构（包括树和二叉树）是一种非常重要的结构。由于树形结构中的各子结构与整个结构具有相似的特性，因而其算法大多采用递归形式，这对许多初学者来说是一个难点。 主要内容 树 树的定义 树T是n个结点构成的有限集合(n0)，其中有一个结点叫根，其余结点可划分为m个互不相交的子集T1,T2……Tm (m≥0)，并且这m个子集本身又构成树，称为T的子树。 注意：本书没有给出空树的概念，即节点数至少为1。 树结构的表现形式及相关概念 嵌套集合表示法 凹入表表示法：类似于目录形式 广义表表示法：（A,(B,(C),(D),(E)),(F,(G),(H))） 树的运算 初始化树：initial_tree(T) 插入子树：insert_tree (T, S) 插入兄弟结点：insert_sibling(T, S) 查询根结点：rootof(T) 查询父结点：fatherof(T) 查询孩子结点：childof(T) 。 查询兄弟结点：siblingof(T) 主要内容 树 二叉树定义 二叉树T是n个结点的有限集合，其中n≥0,当n=0时，为空树，否则，其中有一个结点为根结点，其余结点划分为两个互不相交的子集TL、TR，并且TL、TR分别构成叫作左、右子树的二叉树。 树与二叉树的区别 二叉树每个结点的孩子都有左右之分，每个结点都有左右两个子树，与树结构明显不同。 以三个节点的树为例说明： 二叉树的五种形态 空树，节点数为0 单节点二叉树，只有一个结点 左子树为空，右子树不空 右子树为空，左子树不空 左右子树均不空 二叉树性质 性质1：在二叉树的第i层上的结点数≤2i-1（i0） 所谓满二叉树是指每层都有最大数目结点的二叉树，即高度为k的满二叉树中有2k-1个结点。 完全二叉树则是指在满二叉树的最下层从右到左连续地删除若干个结点所得到的二叉树。 二叉树性质应用---例题 已知完全二叉树有100个结点，则该二叉树有多少个叶子结点？ 若认为每个结点均已编号，则最大的编号为100，其父结点编号为50（见图4-9），从51到100均为叶子，因此叶子数为100-50=50。如下图： 二叉树存储---顺序存储 按完全二叉树的编号次序进行，即编号为i的结点存储在数组中下标为i的元素中； 二叉树存储---二叉链表 二叉链表结构描述： typedef char datatype； typedef struct { datatype data; struct Bnode *lchild, *rchild; } Bnode; 二叉树及对应的二叉链表 主要内容 树 基本遍历方法 遍历二叉树是指按某种次序访问二叉树中每个节点一次且仅一次。 遍历算法例题（1） 假设访问二叉树T的结点的操作是打印结点的值，请分别写出图4-14所示的二叉树的先序、中序和后序序列。 遍历算法例题（2） 已知二叉树的先序和中序序列如下，试构造出相应的二叉树。 先序：ABCDEFGHIJ 中序：CDBFEAIHGJ 原理：先序序列的第一个节点是根节点 中序序列根结点处于左右子树的中序序列之间 注意：二叉树的先序和后序序列不能唯一确定一棵二叉树，但由先序和中序或后序和中序序列能唯一确定一棵二叉树。 遍历算法---递归 后序遍历算法： void postorder(Bnode *T) { if (T!=NULL) { postorder(T-lchild); //后序遍历T的左子树 postorder(T-rchild); //后序遍历T的右子树 visite(T); //访问T的根结点 } } 遍历算法的执行过程---例题说明 模拟算法对如图所示二叉树的中序遍历的执行过程。 二叉树遍历算法应用---例题（1） 设计算法按中序次序输出二叉树Ｔ中度为2的结点的值。 二叉树遍历算法应用---例题（2） 设计算法求二叉树Ｔ的结点数。 将某一遍历算法中的访问结点的操作改为计数操作，即将该结点的数目１累加到一个全局变量ｎ中 void inorder(Bnode *T) { if (T!= NULL) { inorder(T-lchild); n++; //对当前结点计数 inorder(T-rchild);} } 遍历算法思想的应用---步骤 要明确所要编写的算法的功能描述（包括所涉及的各参数或变