算法与数据结构(c语言)_第5章_二叉树与树VIP免费

第五章二叉树与第五章二叉树与树树树形结构是一种十分重要的数据结构。树形结构是一种十分重要的数据结构。本章讨论的二叉树、树和树林都属于树形本章讨论的二叉树、树和树林都属于树形结构。结构。在树形结构中每个结点最多只有一个在树形结构中每个结点最多只有一个前驱，但可有多个后继的结构。前驱，但可有多个后继的结构。它们的共同之处是都表示了一种具有它们的共同之处是都表示了一种具有层次的分支关系。层次的分支关系。5.15.1二叉树及其抽象数据类二叉树及其抽象数据类型型二叉树是一类简单而又重要的树形结构。本节先介绍它的基本概念和重要性质，然后引入二叉树的抽象数据类型。5.1.15.1.1基本概念基本概念•二叉树可以定义为结点的有限集合，这个集合或者为空集，或者由一个根及两棵不相交的分别称作这个根的左子树和右子树的二叉树组成。•二叉树的定义是个递归定义。•二叉树可以是个空集合，这时的二叉树称为空二叉树。二叉树也可以是只有一个结点的集合，这个结点只能是根；它的左子树和右子树均是空二叉树。•下图表示的是二叉树的五种基本形态。二叉树相关的一组术语:父结点、左（右）子结点、边兄弟祖先、子孙路径、路径长度结点的层数结点的度数二叉树的高度：二叉树中结点的最大层数称为二叉树的高度。例如，二叉树t的高度为3。树叶、分支结点•满二叉树：如果一棵二叉树的任何结点或者是树叶，或有两棵非空子树，则此二叉树称作满二叉树（离散数学中称此树是正则的)。•完全二叉树：如果一棵二叉树至多只有最下面的两层结点度数可以小于2，其余各层结点度数都必须为2，并且最下面一层的结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树。•完全二叉树不一定是满二叉树。•扩充的二叉树：把原二叉树的结点都变为度数为2的分支结点，也就是说，如果原结点的度数为2，则不变，度数为1，则增加一个分支，度数为0（树叶），则增加两个分支。•新增加的结点（树叶结点）都用小方框表示，称为外部结点，树中原有的结点称为内部结点。把空二叉树扩充得到的扩充二叉树规定为只有一个外部结点组成的二叉树。•在扩充的二叉树中，外部路径长度E定义为在扩充的二叉树中从根到每个外部结点的路径长度之和。内部路径长度I定义为在扩充的二叉树中从根到每个内部结点的路径长度之和。•如在图的扩充二叉树中：E=2+2+4+4+3+3+3=21I=0+1+1+2+2+3=95.1.25.1.2主要性质主要性质•性质1在非空二叉树的i层上至多有2i个结点(i≥0)。证明：用归纳法来证。•性质2高度为k的二叉树中最多有2k+1-1个结点(k≥0)。证明：假设第i层上的最大结点个数是mi，由性质1可知，深度为k的二叉树中最大结点个数M为:kikkiiimM010122＝•性质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)式可得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的结点，有：(1)如果i=0，则它是根结点，它没有父结点：如果i＞0，则它的父结点的下标为[(i-1)/2]；(2)如果2i＋1≤n－1，则下标为i的结点的左子结点的下标为2i＋1；否则，下标为i的结点没有左子结点：(3)如果2i+2≤n－1，则下标为i的结点的右子结点的下标为2i+2；否则，下标为i的结点没有右子结点。•性质6在满二叉树中，叶结点的个数比分支结点个数多1。•性质7在扩充二叉树中，外部结点的个数比内部结点的个数多1。•性质8对任意扩充二叉树，外部路径长度E和内部路径长度I之间满足以下关系：E=I+...