第六章树和二叉树n.ppt

第六章 树和二叉树 ;学习目标 掌握树的定义、表示方法、基本性质、存储结构和遍历算法； 掌握二叉树的定义、基本性质、存储结构、和各种运算。;6.1 树的类型定义;6.1 树的类型定义;6.1 树的逻辑结构及其操作;A;树形结构;A;对比树型结构和线性结构的结构特点;~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~;数据对象 D：; 基本操作：; Root(T) // 求树的根结点 ;InitTree(T) // 初始化置空树 ; ClearTree(T) // 将树清空 ;基 本 术 语;结点:;内部结点:;祖先:;(从根到结点的)路径：;(１) 有确定的根； (２) 树根和子树根之间为有向关系。;任何一棵非空树是一个二元组 Tree = （root，F） 其中：root 被称为根结点 F 被称为子树森林;注意：;树的常见表示方法;树的常见表示方法;4、目录表示法 将树描述成一本书。书—章节—节—小节; 已知一棵二叉树的广义表表示为 a (b (c), d (e ( , g (h) ), f ) )，则该二叉树的高度为（ ）。假定根结点的高度为0 。 A. 3 B. 4 C. 5 D. 6 ;6.2 二叉树的类型定义 ;为何要重点研究每结点最多只有两个 “叉” 的树？ 二叉树的结构最简单，规律性最强； 可以证明，所有树都能转为唯一对应的二叉树，不失一般性。;A;二叉树的特点（和树比较） 二叉树有两棵子树（可以为空）；而树可以有多棵。 二叉树是有序树（有左右之分）；而树是无序树. 二叉树结点的度最大是2；;二叉树的五种基本形态：;问：具有3个结点的二叉树可能有几种不同形态？ ;应用举例 以用二叉树表示表达式; 二叉树的主要基本操作：; Root(T); Value(T, e); Parent(T, e); LeftChild(T, e); RightChild(T, e); LeftSibling(T, e); RightSibling(T, e); BiTreeEmpty(T); BiTreeDepth(T); PreOrderTraverse(T, Visit()); InOrderTraverse(T, Visit()); PostOrderTraverse(T, Visit()); LevelOrderTraverse(T, Visit());; InitBiTree(T); Assign(T, e, value); CreateBiTree(T, definition); InsertChild(T, p, LR, c);;ClearBiTree(T); DestroyBiTree(T); DeleteChild(T, p, LR);;二叉树的重要特性;用归纳法证明： 归纳基： 归纳假设： 归纳证明：;性质 2 ： 深度为 k 的二叉树上至多含 2k-1 个结点（k≥1）。;一棵高度为5的二叉树中，最多包含有______个结点。假定根结点的高度为0。 ; 性质 3 ： 对任何一棵二叉树，若它含有n0 个叶子结点、n2 个度为 2 的结点，则必存在关系式：n0 = n2+1。;?? 在一棵具有n个结点的二叉树中，所有结点的空子树个数等于（ ）。 A. n B. n-1 C. n+1 D. 2*n ;两类特殊的二叉树：;完全二叉树：树中所含的 n 个结点和满二叉树中编号为 1 至 n 的结点一一对应。; 完全二叉树的特点： 1、只有最后一层是不满的，不满层的结点最先出现在左边 2、至多只有最下面的两层结点的度小于2 3、任何左子树的高度不会小于右子树的高度，且左右子树的高度最大相差1； 4。叶子结点最多出现在最后2层上。; 性质4 ： 具有 n 个结点的完全二叉树的深度为 ? log2n? +1 。; 在一棵具有35个结点的完全二叉树中，该树的高度为（ ）。 A. 5 B. 6 C. 7 D. 8 ;性质 5 ：;1.?在一棵完全二叉树中，若编号为i的结点存在左孩子，则左子女结点的编号为（ ）。假定根结点的编号为0 A. 2i B. 2i-1 C. 2i+1 D. 2i