·性质3对于一棵非空的二叉树,如果叶子结点数为n, 度数为2的结点数为n2,则有 n=n2+1 证明设n为二叉树的结点总数,n1为二叉树中度为1的结 点数,则有: n=no+n,+n 6-1) 在二叉树中,除根结点外,其余结点都有唯一的一个进 入分支。设B为二叉树中的分支数,那么有 B=n-1 (6-2) 这些分支是由度为1和度为2的结点发出的,一个度为1 的结点发出一个分支,一个度为2的结点发出两个分支,所 以有: B=n1+2n2 (6-3) 综合(6-1)、(6-2)、(6-3)式可以得到: 0=n2+1 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 11 • 性质3 对于一棵非空的二叉树，如果叶子结点数为n0， 度数为2的结点数为n2，则有: n0 ＝n2＋1。 证明 设n为二叉树的结点总数，n1为二叉树中度为1的结 点数，则有： n＝n0＋n1＋n2 （6-1） 在二叉树中，除根结点外，其余结点都有唯一的一个进 入分支。设B为二叉树中的分支数，那么有： B＝n－1 （6-2） 这些分支是由度为1和度为2的结点发出的，一个度为1 的结点发出一个分支，一个度为2的结点发出两个分支，所 以有： B＝n1＋2n2 （6-3） 综合（6-1）、（6-2）、（6-3）式可以得到： n0 ＝n2＋1
性质4具有n个结点的完全二叉树的深度k为 Lloga nh+1。 证明根据完全二又树的定义和性质2可知,当一棵完全 二叉树的深度为k、结点个数为n时,有 2k-1-1<n≤2k-1 即 2k-1≤ 对不等式取对数,有 k-1≤log2n<k 由于k是整数,所以有 k=Llog,nh 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 12 • 性质4 具有n个结点的完全二叉树的深度k为log2n+1。 证明 根据完全二叉树的定义和性质2可知，当一棵完全 二叉树的深度为k、结点个数为n时，有 2 k－1－1<n≤2 k -1 即 2 k－1≤n<2 k 对不等式取对数，有 k－1≤log2n<k 由于k是整数，所以有 k＝log2n+1
性质5对于具有n个结点的完全二叉树,如果按照从上至 下和从左到右的顺序对二叉树中的所有结点从1开始顺序编号 则对于任意的序号为的结点,有: (1)如果i1,则序号为i的结点的双亲结点的序号为i/2(/ 表示整除):如果i=1,则序号为的结点是根结点,无双亲 结点。 (2)如果2i≤n,则序号为i的结点的左孩子结点的序号为2i 如果2in,则序号为i的结点无左孩子 (3)如果2i+1≤n,则序号为i的结点的右孩子结点的序号为 2i+1:如果2i+1>n,则序号为的结点无右孩子。 此外,若对二叉树的根结点从0开始编号,则相应的i号结 点的双亲结点的编号为(i-1)/2,左孩子的编号为2i+1, 右孩子的编号为2i+2。 此性质可采用数学归纳法证明。证明略。 2021年1月21日 数据结构讲义 13
2021年1月21日 数据结构讲义 13 • 性质5 对于具有n个结点的完全二叉树，如果按照从上至 下和从左到右的顺序对二叉树中的所有结点从1开始顺序编号 ，则对于任意的序号为i的结点，有： ⑴如果i>1，则序号为i的结点的双亲结点的序号为i/2(“/” 表示整除)；如果i＝1，则序号为i的结点是根结点，无双亲 结点。 ⑵如果2i≤n，则序号为i的结点的左孩子结点的序号为2i ；如果2i>n，则序号为i的结点无左孩子。 ⑶如果2i＋1≤n，则序号为i的结点的右孩子结点的序号为 2i＋1；如果2i＋1>n，则序号为i的结点无右孩子。 此外，若对二叉树的根结点从0开始编号，则相应的i号结 点的双亲结点的编号为（i－1）/2，左孩子的编号为2i＋1， 右孩子的编号为2i＋2。 此性质可采用数学归纳法证明。证明略
6.2基本操作与存储实现 二叉树的存储 ◆二又树的基本操作及实现 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 14 6.2 基本操作与存储实现 二叉树的存储 二叉树的基本操作及实现
6.2.1二叉树的存储 1.顺序存储结构 ◆所谓二叉树的顺序存储,就是用一组连续的存储单元存 放二叉树中的结点。一般是按照二叉树结点从上至下、从 左到右的顺序存储。这样结点在存储位置上的前驱后继关 系并不一定就是它们在逻辑上的邻接关系,然而只有通过 些方法确定某结点在逻辑上的前驱结点和后继结点,这 种存储才有意义。因此,依据二叉树的性质,完全二叉树 和满二叉树采用顺序存储比较合适,树中结点的序号可以 唯一地反映出结点之间的逻辑关系,这样既能够最大可能 地节省存储空间,又可以利用数组元素的下标值确定结点 在二叉树中的位置,以及结点之间的关系。 2021年1月21日 数据结构讲义 15
2021年1月21日 数据结构讲义 15 6.2.1 二叉树的存储 1．顺序存储结构 所谓二叉树的顺序存储，就是用一组连续的存储单元存 放二叉树中的结点。一般是按照二叉树结点从上至下、从 左到右的顺序存储。这样结点在存储位置上的前驱后继关 系并不一定就是它们在逻辑上的邻接关系，然而只有通过 一些方法确定某结点在逻辑上的前驱结点和后继结点，这 种存储才有意义。因此，依据二叉树的性质，完全二叉树 和满二叉树采用顺序存储比较合适，树中结点的序号可以 唯一地反映出结点之间的逻辑关系，这样既能够最大可能 地节省存储空间，又可以利用数组元素的下标值确定结点 在二叉树中的位置，以及结点之间的关系