第6章二叉树和树1.ppt
1,第6章 二叉树和树1,前面的章节主要讨论的是线性结构，二叉树和树属于非线性的结构。遍历非线性结构比线性结构要麻烦。 二叉树及树的遍历技术是本章各种算法的核心，而且大多是以递归的形式表现的，阅读和编写递归算法是学习本章的难点。 讲授本章课程大约需8课时。,2,树结构的特点及基本术语 6.1 二叉树,3,树结构的特点及基本术语,4,线性结构,树型结构,第一个数据元素 (无前驱),根结点 (无前驱),最后一个数据元素 (无后继),多个叶子结点 (无后继),其它数据元素 (一个前驱、 一个后继),其它数据元素 (一个前驱、 多个后继),对比树型结构和线性结构的结构特点,5,结点:数据元素+若干指向子树的分支,结点的度:分支的个数,树的度:树中所有结点的度的最大值,叶子结点:度为零的结点,分支结点:度大于零的结点,基本术语,6,(从根到结点的)路径：,孩子结点、双亲结点 兄弟结点、堂兄弟 祖先结点、子孙结点,由从根到该结点所经分支和结点构成,结点的层次:假设根结点的层次为1,第l 层的结点的子树根结点的层次为l+1,树的深度：树中叶子结点所在的最大层次,7,6.1 二叉树,一、二叉树的定义和基本术语 二、二叉树的几个基本性质 三、二叉树的存储结构,8,一、二叉树的定义和基本术语,9,二叉树的定义 二叉树是n（n0）个元素的有限集，它或为空树，或是由一个根结点加上两棵分别称为左子树和右子树的、互不交的二叉树组成。,根结点,左子树,右子树,B,10,二叉树可以表现出五种基本形态：,11,二叉树的基本操作：,查 找 类 的 操 作,插 入 类 的 操 作,删 除 类 的 操 作,12,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); InOrderTraverse(T); PostOrderTraverse(T); LevelOrderTraverse(T);,查找类的操作：,13,InitBiTree(,插入类的操作：,14,ClearBiTree(,删除类的操作：,15,二、二叉树的几个基本性质,16,性质 1 ： 在二叉树的第 i 层上至多有2i-1 个结点 (i1) 。,用归纳法证明： 归纳基： 归纳假设： 归纳证明：,i = 1 层时，只有一个根结点： 2i-1 = 20 = 1；,假设对所有的 j，1 j i，命题成立；,二叉树上每个结点至多有两棵子树， 则第 i 层的结点数 = 2i-2 2 = 2i-1 。,17,性质 2 ： 深度为 k 的二叉树上至多含 2k-1 个结点（k1）。,证明：,基于上一条性质，深度为 k 的二叉树上的结点数至多为 20+21+ +2k-1 = 2k-1 。,18,性质 3 ： 对任何一棵二叉树，若它含有n0 个叶子结点、n2 个度为 2 的结点，则必存在关系式：n0 = n2+1。,证明：,设 二叉树上结点总数 n = n0 + n1 + n2 又 二叉树上分支总数 b = n1+2n2 而 b = n-1 = n0 + n1 + n2 - 1 由此， n0 = n2 + 1 。,19,两类特殊的二叉树：,满二叉树：指的是深度为k且含有2k-1个结点的二叉树。,完全二叉树：树中所含的 n 个结点和满二叉树中编号为 1 至 n 的结点一一对应。,20,性质 4 ： 具有 n 个结点的完全二叉树的深度为 log2n +1 。,证明：,设完全二叉树的深度为 k 则根据第二条性质得 n 2k-1，得n 2k 前k-1层是满二叉树，因而2k-1 -1n，得 2k-1 n，从而得到2k-1 n2k 即 k-1 log2 n k 因为 k 只能是整数，因此， k =log2n + 1 。,21,性质 5 ：,若对含 n 个结点的完全二叉树从上到下且从左至右进行 1 至 n 的编号，则对完全二叉树中任意一个编号为 i 的结点： (1) 若 i=1，则该结点是二叉树的根，无双亲， 否则，编号为 i/2 的结点为其双亲结点；,22,性质 5 ：,(2) 若 2in，则该结点无左孩子， 否则，编号为 2i 的结点为其左孩子结点； (3) 若 2i+1n，则该结点无右孩子结点， 否则，编号为2i+1 的结点为其右孩子结点。,23,三、二叉树的存储结构,二叉树顺序存储表示 二叉树链式存储表示,24,const MAXSIZE = 100; / 暂定二叉树的最大结点数 typedef struct TElemType *data; / 存储空间基址 int nodenum; /树中结点数 SqBiTree ;,二叉树顺序存储表示,25,例如:,A B D C E F,0 1 2 3 4 5 6 7 8 9 10 11 12 13,26,第7次书面作业,6.1 6.2 6.3 6.4,练习和理解 p179 1. p180 5. 6. 7.,
