《叉树与树》PPT课件

《《叉树与树》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第五章二叉树与树树形结构是一种十分重要的数据结构。本章讨论的二叉树、树和树林都属于树形结构。在树形结构中每个结点最多只有一个前驱，但可有多个后继的结构。它们的共同之处是都表示了一种具有层次的分支关系。5.1二叉树及其抽象数据类型5.1.1基本概念二叉树可以定义为结点的有限集合，这个集合或者为空集，或者由一个根及两棵不相交的分别称作这个根的左子树和右子树的二叉树组成。二叉树的定义是个递归定义。二叉树可以是个空集合，这时的二叉树称为空二叉树。二叉树也可以是只有一个结点的集合，这个结点只能是根；它的左子树和右子树均是空二叉树。二叉树描述的是一种层次关系，除了根节点外其余节点都有且只有一个前驱节点

2、，所有节点可以有0到两个后继节点。二叉树的五种基本形态二叉树的相关术语父结点、左（右）子结点、边：若节点x是根节点，y是x的左（右）子树的根，则称x是y的父节点，y是x的左（右）子节点，有序对称作x到y的边。兄弟：具有同一个父节点的节点彼此称为兄弟。祖先、子孙：若节点y在以节点x为根的左（右）子树中，且x≠y，则称x是y的祖先，y是x的子孙。路径、路径长度：如果x是y的祖先，又有x=x0,x1,…,xn=y满足xi为xi+1的父节点，称x0,x1,…,xn为从x到y的一条路径，n称为路径长度。结点的层数：根的层数为1，其余节点的层数等于其父节点的措施加1。结点的度数：节点的非空子

3、树的个数称作节点的度数。二叉树中节点的最大度数为2。二叉树的高度：二叉树中结点的最大层数称为二叉树的高度。树叶、分支结点：左（右）子树均为空二叉树的节点称作树叶；否则称为分支节点。特殊的二叉树满二叉树：如果一棵二叉树的任何结点或者是树叶，或有两棵非空子树，则此二叉树称作满二叉树（离散数学中称此树是正则的)。完全二叉树：如果一棵二叉树至多只有最下面的两层结点度数可以小于2，其余各层结点度数都必须为2，并且最下面一层的结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树。完全二叉树不一定是满二叉树。满二叉树不一定是完全二叉树。扩充的二叉树：把原二叉树的结点都变为度数为2的分支结点，也就

4、是说，如果原结点的度数为2，则不变，度数为1，则增加一个分支，度数为0（树叶），则增加两个分支。新增加的结点（树叶结点）都用小方框表示，称为外部结点，树中原有的结点称为内部结点。由非空二叉树扩充的二叉树都是满二叉树。把空二叉树扩充得到的扩充二叉树规定为只有一个外部结点组成的二叉树。在扩充的二叉树中，外部路径长度E定义为在扩充的二叉树中从根到每个外部结点的路径长度之和。内部路径长度I定义为在扩充的二叉树中从根到每个内部结点的路径长度之和。如在图的扩充二叉树中：E=2+2+4+4+3+3+3=21I=0+1+1+2+2+3=95.1.2主要性质性质1在非空二叉树的i层上至多有2i个结点(i≥0

5、)。证明：用归纳法来证。性质2高度为k的二叉树中最多有2k+1-1个结点(k≥0)。证明：假设第i层上的最大结点个数是mi，由性质1可知，深度为k的二叉树中最大结点个数M为:性质3对于任何一棵非空的二叉树，如果叶结点个数为n0，度为2的结点个数为n2，则有：n0=n2+1。证明：设一棵非空二叉树中有n个结点，度为1的结点个数为n1，因为二叉树中所有结点的度均不大于2，所以n=n0+n1+n2(1)在二叉树中，除根结点外，其余每个结点都有一个分支进入，假设B为分支总数，则有B=n–1(2)又由于二叉树中的分支都是由度为1和2的结点发出，所以有B=n1+2n2(3)综合(1)、(2)、(3)式

6、可得n0=n2+1。性质4具有n个结点的完全二叉树的深度k为。证明：根据性质2和完全二叉树的定义可知2k-1＜n≤2k+1–1即：2k≤n＜2k+1对不等式取对数有：k≤＜k+1由于k为整数，所以有k=性质5对于具有n个结点的完全二叉树，如果按照从上（根结点）到下（叶结点）和从左到右的顺序对二叉树中的所有结点从0开始到n-1进行编号，则对于任意的下标为i的结点，有：如果i=0，则它是根结点，它没有父结点：如果i＞0，则它的父结点的下标为[(i-1)/2]；如果2i＋1≤n－1，则下标为i的结点的左子结点的下标为2i＋1；否则，下标为i的结点没有左子结点：如果2i+2≤n－1，则下标为i的结

7、点的右子结点的下标为2i+2；否则，下标为i的结点没有右子结点。性质6在满二叉树中，叶结点的个数比分支结点个数多1。性质7扩充二叉树中，外部结点的个数比内部结点的个数多1。性质8对任意扩充二叉树，外部路径长度E和内部路径长度I之间满足以下关系：E=I+2n，其中n是内部结点个数。5.1.3二叉树的抽象数据类型ADTBinTreeisoperationsBinTreecreateEmptyBinTree(void)创建一棵