第7章二叉树 二叉树的基本概 >二叉树的基本运算 二叉树的存储结构 二叉树的遍历 二叉树其它运算的实现 >穿线二叉树 >树、森林和二叉树的转换
第7章 二叉树 ➢二叉树的基本概念 ➢二叉树的存储结构 ➢二叉树的基本运算 ➢二叉树其它运算的实现 ➢穿线二叉树 ➢树、森林和二叉树的转换 ➢二叉树的遍历
7.1二叉树的基本概念 二叉树的定义为:二叉树是一个由结点构成的有 限集合,这个集合或者为空,或者由一个根结点及 两棵互不相交的分别称作这个根的左子树和右子树 的二叉树组成。当二叉树的结点集合为空时,称为 空二叉树。 b d(e(g
7.1 二叉树的基本概念 二叉树的定义为：二叉树是一个由结点构成的有 限集合，这个集合或者为空，或者由一个根结点及 两棵互不相交的分别称作这个根的左子树和右子树 的二叉树组成。当二叉树的结点集合为空时，称为 空二叉树 。 a b d e c h f g
二叉树有以下五种基本形态 (a)空二叉树(b)根和空的左、右子树(c)根和非空左子树、空右子树 (d)根和空左子树、非空右子树(e)根和非空的左、右子树
二叉树有以下五种基本形态： (a) 空二叉树 (b) 根和空的左、右子树 (c) 根和非空左子树、空右子树 (d) 根和空左子树、非空右子树 (e) 根和非空的左、右子树
树型结构中使用的术语如父母(双亲或前件) 子女(后件)、祖先、子孙、兄弟和路径等在二叉树 中仍然可以沿用,但值得注意的是,二叉树并非一般 树型结构的特殊形式,它们为两种不同的数据结构。 叉树与一般树型结构的主要区别在于: (1)二叉树中每个非空结点最多只有两个子女,而 般的树型结构中每个非空结点可以有0到多 个子女; (2)二叉树中结点的子树要区分左子树和右子树, 即使在结点只有一棵子树的情况下也要明确指 出是左子树还是右子树
树型结构中使用的术语如父母（双亲或前件）、 子女（后件）、祖先、子孙、兄弟和路径等在二叉树 中仍然可以沿用，但值得注意的是，二叉树并非一般 树型结构的特殊形式，它们为两种不同的数据结构。 二叉树与一般树型结构的主要区别在于： （1）二叉树中每个非空结点最多只有两个子女，而 一般的树型结构中每个非空结点可以有0到多 个子女； （2）二叉树中结点的子树要区分左子树和右子树， 即使在结点只有一棵子树的情况下也要明确指 出是左子树还是右子树
二叉树具有以下重要性质: 性质1一棵非空二叉树的第层上至多有21个结点 ≥1) 证明:当i1时,只有根结点,此时21=20=1,显然 上述性质成立;又由于在二叉树中每个结点最多只 能具有两个子女,因而第层上结点的最大个数是第 i-层上结点的最大个数的两倍。于是第2层上结点的 最大个数为2,第3层上结点的最大个数为4, 则第层上结点的最大个数即为21 性质2深度为h的二叉树至多有21个结点(h>1)。 根据性质1,深度为h的二叉树最多具有的结点的个 数为20+21+2+.+2h1=2h-1
二叉树具有以下重要性质： 性质1 一棵非空二叉树的第i层上至多有2 i-1个结点 （i≥1）。 证明：当i=1时，只有根结点，此时2 1-1=20=1，显然 上述性质成立；又由于在二叉树中每个结点最多只 能具有两个子女，因而第i层上结点的最大个数是第 i-1层上结点的最大个数的两倍。于是第2层上结点的 最大个数为2，第3层上结点的最大个数为4，……, 则第i层上结点的最大个数即为2 i-1 。 性质2 深度为h的二叉树至多有2 h -1个结点（h>1）。 根据性质1，深度为h的二叉树最多具有的结点的个 数为2 0+21+22+…+2h-1=2h -1
性质3对于任何一棵二叉树T,如果其终端结点数为 n0,度为2的结点数为n2,则n0=n2+1。 证明:假设二叉树中总的结点个数为n,度为1的结 点个数为n1,则有 n=n0+n1+n2 又由于在二叉树中除根结点外,其它结点均通过一条 树枝且仅通过一条树枝与其父母结点相连,即除根结 点外,其它结点与树中的树枝存在一一对应的关系; 而二叉树中树枝的总条数为n1+2*n2,因而二叉树 总结点的个数为 n=n1+2*n2+1 于是有 n0+n1+n2=n1+2*n2+1 显然n0=n2+1成立
性质3 对于任何一棵二叉树T，如果其终端结点数为 n0，度为2的结点数为n2，则n0=n2+1。 证明：假设二叉树中总的结点个数为n ，度为1的结 点个数为n1，则有： n=n0+n1+n2 又由于在二叉树中除根结点外，其它结点均通过一条 树枝且仅通过一条树枝与其父母结点相连，即除根结 点外，其它结点与树中的树枝存在一一对应的关系； 而二叉树中树枝的总条数为n1+2*n2，因而二叉树 总结点的个数为： n=n1+2*n2+1 于是有： n0+n1+n2=n1+2*n2+1 显然n0=n2+1成立
如果一棵二叉树中所有终端结点均位于同一层次 而其它非终端结点的度数均为2,则称此二叉树为满 二叉树。在满二叉树中,若其深度为h,则其所包含 的结点个数必为2-1。下图中的二叉树即为一棵深度 为3的满二叉树,其结点的个数为23-1=7 3 6)6⑦
如果一棵二叉树中所有终端结点均位于同一层次， 而其它非终端结点的度数均为2，则称此二叉树为满 二叉树。在满二叉树中，若其深度为h，则其所包含 的结点个数必为2 h -1。下图中的二叉树即为一棵深度 为3的满二叉树，其结点的个数为2 3 -1=7。 1 4 2 5 3 6 7
如果一棵二叉树扣除其最大层次那层后即成为一棵 满二叉树,且层次最大那层的所有结点均向左靠齐, 则称该二叉树为完全二叉树。通俗地说,完全二叉树 中只有最下面的两层结点的度数可以小于2,且最下 面一层的结点都集中在该层最左边的若干位置上。下 图所示的二叉树即为一棵深度为3的完全二叉树。 2 3 5)(6 若对深度相同的满二叉树和完全二叉树中的所有结 点按自上而下、同一层次按自左向右的顺序依次编号, 则两者对应位置上的结点编号应该相同
如果一棵二叉树扣除其最大层次那层后即成为一棵 满二叉树，且层次最大那层的所有结点均向左靠齐， 则称该二叉树为完全二叉树。通俗地说，完全二叉树 中只有最下面的两层结点的度数可以小于2，且最下 面一层的结点都集中在该层最左边的若干位置上。下 图所示的二叉树即为一棵深度为3的完全二叉树。 若对深度相同的满二叉树和完全二叉树中的所有结 点按自上而下、同一层次按自左向右的顺序依次编号， 则两者对应位置上的结点编号应该相同。 1 4 2 5 3 6
对于完全二叉树,具有以下性质: 性质4对于具有n个结点的完全二叉树,如果按照从 上到下、同一层次上的结点按从左到右的顺序对二叉 树中的所有结点从1开始顺序编号,则对于序号为i的 结点,有: (1)如果i>1,则序号为的结点其双亲结点的序号 为i2」(Li/2表示对/2的值取整);如果 1,则结点为根结点,没有双亲; (2)如果2i>n,则结点无左子女(此时结点为终 端结点);否则其左子女为结点2i (3)如果2i+1>n,则结点无右子女;否则其右子 女为结点2i+1
对于完全二叉树，具有以下性质： 性质4 对于具有n个结点的完全二叉树，如果按照从 上到下、同一层次上的结点按从左到右的顺序对二叉 树中的所有结点从1开始顺序编号，则对于序号为i的 结点，有： （1）如果i>1，则序号为i的结点其双亲结点的序号 为i/2 （i/2表示对i/2的值取整）；如果 i=1, 则结点i为根结点，没有双亲； （2）如果2i>n，则结点i无左子女（此时结点i为终 端结点）；否则其左子女为结点2i； （3）如果2i+1>n，则结点i无右子女；否则其右子 女为结点2i+1
7.2二叉树的基本运算 ADT bintree i 数据对象D:D是具有相同性质的数据元素构成的集合 数据关系R:如果D为空或D仅含一个元素,则R为空 否则D中存在一个特殊的结点root称之为根结点, 其无前驱;其它结点被分成互不相交的两个集合, 分别构成root的左子树和右子树r;岩l和r库空, 则它们的根结点root和 rroot分别称为整棵二叉 树根结点root的后继结点;左子树l和右子树r也 是二叉树,因而它们中数据元素间的关系也同样 满足R的定义。 二叉树的基本操作如下: (Icreatebitree(t) (2)destroybitree(t
7.2 二叉树的基本运算 ADT bintree { 数据对象D：D是具有相同性质的数据元素构成的集合。 数据关系R：如果D为空或D仅含一个元素，则R为空； 否则D中存在一个特殊的结点root,称之为根结点， 其无前驱；其它结点被分成互不相交的两个集合， 分别构成root的左子树l和右子树r；若l和r非空， 则它们的根结点lroot和rroot分别称为整棵二叉 树根结点root的后继结点；左子树l和右子树r也 是二叉树，因而它们中数据元素间的关系也同样 满足R的定义。 二叉树的基本操作如下： (1)createbitree(t) (2)destroybitree(t)