性质2:深度为k的二叉树至多有2-1个结点(k≥1)。 证明: 深度为k的二叉树的最大的结点时为二叉树中每层上的 最大结点数之和,由性质1得到每层上的最大结点数。 k ∑241=2k-1 ③⑨① ④③ 计算机教研宦 第16页 2021/2/19
Data Structure 数 据 结 构—— 第 6 章 树 和 二 叉 树 胡建华 2021/2/19 计算机教研室 第16页 性质2：深度为k的二叉树至多有2 k－1个结点（k≥1)。 证明： 深度为k的二叉树的最大的结点时为二叉树中每层上的 最大结点数之和，由性质1得到每层上的最大结点数。 2 2 1 1 1 = − = − k k i i 1 2 4 5 8 9 10 11 3 6 7 12 13 14 15
⑨性质3:对任何一棵二叉树,如果其终端结点数为n,度 回为2的结点数为n2,则no=n2+1。 证明: 设二叉树中度为1的结点数为n1,二叉树中总结点数为n, 则有:n=n+n1+n2 (6-1) 再看二叉树中的分支数,除根结点外,其余结点都有 个进入分支,设B为二叉树中的分支总数,则有:n=B+1 由于这些分支都是由度为1和2的结点产生的,则有: B=n1+2*n2 n=B+1=n1+2×n2+1(6-2) 由式(6-1)和(6-2)得到: no+n1+n2=n1+2*n2+1 0=n2+1 第17页 ∠U∠I∠19
Data Structure 数 据 结 构—— 第 6 章 树 和 二 叉 树 胡建华 2021/2/19 计算机教研室 第17页 性质3：对任何一棵二叉树，如果其终端结点数为n0，度 为2的结点数为n2，则n0＝n2＋1。 证明： 设二叉树中度为1的结点数为n1，二叉树中总结点数为n， 则有：n＝n0＋n1＋n2 (6-1) 再看二叉树中的分支数，除根结点外，其余结点都有一 个进入分支，设B为二叉树中的分支总数，则有：n＝B＋1 由于这些分支都是由度为1和2的结点产生的，则有： B＝n1+2*n2 n＝B＋1＝n1＋2×n2＋1 （6－2) 由式（6－1）和（6－2）得到： n0+n1+n2=n1+2*n2+1 n0＝n2＋1
性质4:具有n个结点的完全二叉树的深度为: og n+ 1 证明:假设完全二又树的深度为k。 由性质2和完全二叉树的定义可知: 24-1<n≤2-1或者2k-1≤n<2k 对上式取对数则有: ③ k-1≤log2n<k 由于k是整数,则:k=1L102+1 计算机教研宦 第18页 2021/2/19
Data Structure 数 据 结 构—— 第 6 章 树 和 二 叉 树 胡建华 2021/2/19 计算机教研室 第18页 性质4：具有n个结点的完全二叉树的深度为： log2 n + 1。 证明：假设完全二叉树的深度为k。 由性质2和完全二叉树的定义可知： 或者 对上式取对数则有： 由于k是整数，则：k = log2 n + 1 2 1 2 1 1 − − k− k n k k 2 n 2 1 − k − n k 2 1 log 1 2 4 5 8 9 10 11 3 6 7 12
性质5:具有n个结点的完全二叉树,如果从根结点开始, 从上到下为每一个结点从左到右进行编号,那么就有: 点()若i=1,则结点为二叉树的根,无双亲结点。否则,若 6i1,则i结点父结点的编号为i/2」 缩(2)若2i≤n,则结点的左孩子结点的编号为2i;否则结点i 无左孩子(叶子结点) 3)若2i+1≤n,则结点的左孩子结点的编号为2i+1;否则 意无有孩子 证明:可以采用数学归纳法。 正是由于完全二又树具有如此膨备 6 :满二叉 第19页树可以采用一个一维数组来存储。 机教研室 2021/2/19
Data Structure 数 据 结 构—— 第 6 章 树 和 二 叉 树 胡建华 2021/2/19 计算机教研室 第19页 性质5：具有n个结点的完全二叉树，如果从根结点开始， 从上到下为每一个结点从左到右进行编号，那么就有： ⑴ 若i=1，则结点为二叉树的根，无双亲结点。否则，若 i>1，则i结点父结点的编号为i/2； ⑵ 若2i≤n，则结点的左孩子结点的编号为2i；否则结点i 无左孩子（叶子结点） ⑶ 若2i+1≤n，则结点的左孩子结点的编号为2i+1；否则 无有孩子 证明：可以采用数学归纳法。 正是由于完全二叉树具有如此特点，所以完全或满二叉 树可以采用一个一维数组来存储。 1 2 4 5 8 9 10 11 3 6 7 12
@6.1.3二叉树的存储结构 1.顺序存储方法: 它是用一组连续的存储单元存储二叉树的数据 元素。因此,必须把二叉树的所有结点安排成为 个恰当的序列,结点在这个序列中的相互位置 能反映出结点之间的逻辑关系,用编号的方法。 #define maxsize 100 typedef teletype sabitree lmaxsizel Sabitree b 计算机教研宦 第20页 2021/2/19
Data Structure 数 据 结 构—— 第 6 章 树 和 二 叉 树 胡建华 2021/2/19 计算机教研室 第20页 6.1.3 二叉树的存储结构 1.顺序存储方法： 它是用一组连续的存储单元存储二叉树的数据 元素。因此，必须把二叉树的所有结点安排成为 一个恰当的序列，结点在这个序列中的相互位置 能反映出结点之间的逻辑关系，用编号的方法。 #define maxsize 100 typedef telemtype sqbitree[maxsize]; Sqbitree bt；