数据结构-树与二叉树讲解.ppt

本章主要内容： 1．二叉树的定义、性质和存储结构。 2．二叉树的遍历和线索化以及遍历算法的各种描述形式。 3．树和森林的定义、存储结构与二叉树的转换、遍历。 4．树的应用。 本章学习重点： 1．掌握二叉树的存储结构及其各种操作。 2．掌握树和森林与二叉树的转换关系。; 第六章???树和二叉树; 第六章???树和二叉树; 6.1 树的定义和基本术语;一、树的定义;一、树的定义;一、树的定义;3.树型结构的例子 (1)家族的血缘关系 ;(2)计算机磁盘目录 ;1．图形表示法：以图1中的树为例。;2.形式化表示 对于一个T的形式化表示为： T=(D，R) D为T中结点的集合；R为T中结点之间关系的集合。 以上图为例。 D={A,B,C,D,E,F,G,H,I,J,K,L,M} R={A,B,A,C,A,D,B,E,B,F,C,G,D,H,D,I,D,J,E,K,E,L,H,M} ;1．结点：包含一个数据元素及若干指向其子树的分支。 图1所示的树有13个结点。 2．结点的度(degree)：结点拥有的子树数。A结点的度为3。 3．叶子或终端结点(leaf)：度为0的结点。K,L,F,G,M,I,J皆为叶子。 4．分支结点或非终端结点：度不为0的结点。 5．树的度：树内各结点的度的最大值。图1所示的树的度为3。 6．双亲结点(parent)：结点的前驱结点。A是B,C,D的双亲。 ;三、基本术语;13．树的深度(depth)或高度：树中结点的最大层次。上图所示树的深度为4。 14．有序树和无序树：树中结点的各子树从左至右排列，不可对换，称这种树为有序树，且把各子树分别称为第一子树，第二子树，最左边的子树为第一孩子，最右边子树为最后一个孩子。否则称为无序树。 15．森林(forest)：是m(m≥0)棵互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林。如图，若删除A，就得到三棵子树构成的森林。 ; 可以用森林和树相互递归的定义来描述树。 树的逻辑结构采用二元组形式： T=(root,F) root:根结点，数据元素 F:m棵数的森林，F=（T1，T2，…，Tm） Ti=（ri，Fi）是第i棵子树 树根和子树之间的关系：RF={root,ri |i=1,2,…,m,m0 };;一、二叉树的定义;1．抽象数据类型二叉树的定义 ADT BinaryTree{ 数据对象D：D是具有相同特性的数据元素的集合。 数据关系R： 若D=Φ，则R=Φ，称BinaryTree为空二叉树； 若D?Φ，则R={H}，H是如下二元关系集： (1)在D中存在唯一的称为根的数据元素root，它在关系H下无前驱； (2)若D-{root}?Φ，则存在D-{root}={Dl，Dr}，且Dl∩Dr=Φ； ; (3)若Dl?Φ，则Dl中存在唯一的元素xl, root,xl?H，且存在Dl上的关系H1?H；若Dr?Φ，则Dr中存在唯一的元素xr,root,xr?H,且存在Dr 上的关系Hr?H；H={root,xl，root,xr,Hl,Hr}； (4)(Dl，{Hl})是一棵符合本定义的二叉树，称为根的左子树，(Dr，{Hr})是一棵符合本定义的二叉树，称为根的右子树。 基本操作P： 略。 }ADT BinaryTree ;4.二叉树的五种基本形态 ;5. 特殊的二叉树 (1)满二叉树 如果二叉树的叶子结点都在同一层，且其它各层的结点都包含左、右子树，则称该二叉树为满二叉树。;(2)完全二叉树 如果一棵深度为k的有i(1≤i≤n)个结点的二叉树，对树中的结点自上而下、自左而右连续编号，若编号为i的结点与满二叉树中编号为i的结点的位置相同，则称此二叉树为完全二叉树。;性质1 在二叉树的第i(i≥1)层上至多有2i-1个结点。 用数学归纳法就可以证明。 满二叉树的第i层上共有2i-1个结点。 深度为k的完全二叉树，除了第k层外，其余各层也均 有2i-1个结点(1≤Ik)。 性质2 深度为k的二叉树最多有2k-1个结点。 证明：最多结点数为各层结点个数相加，即 1+2+4+…+2k-1=2k-1 ;性质3 对任意二叉树T，如果其终端结点数为n0(度数为0的结 点数), n1,n2分别表示度数为1,2的结点个数，则n0=n2+1。 证明：设n为二叉树T的结点总数，则有： n=n0+n1+n2 设除根结点外的结点数为B，则B=n-1。又B= n1+2*n2 所以，n-1= n1+2*n2 n0+n1+n2= n1+2*n2+1 求得