6.2二叉树 6.2二叉树-性质(1) ■二叉树的定义（递归定义） 。二叉树的性质 ·特点：毒个结点重多只有两暴子批，子树有左友之分 ,性质1：二叉树的第层至多有21个结点（≥1） ·二叉树v5度不大于2的有序树 ·性质2：深度为h的二叉树至多有2-1个结点(h≥) .ADT BinaryTree 思考：性质1和性质2推广到k见树，结果会如何？ (-1)/-1) ,性质3：m。一2+1 结点总数n+西十m 分支数m-1■m1+2n2 思考：若包含有个结点的树中只有叶子结点和度为店 的站点，则过树中有多少叶子站点？ 二叉树 有序树 囵 n■。+ng广1■kng>H。■-(0-1)Vk 13/106 147106 图 6.2二叉树-性质(2) 主6.2二又树-性质(3) ,满二叉树：一棵深度为k且有2-1个结点的二叉树 ·性质4：具有m个结点的完全二叉树的深度为Llog,n小+1 (k≥0) 由性质221.1<n≤21或2-5n<2 ,完全二义树：对于深度为的完全二叉树，则 )前层为满二树： 于是k-1≤og2n<k 2)幕k层站燕依次占据最左边的位置： 3)一个站燕有右棋于，则它必有左孩子： 例：若一个完全二又树有1450个站点，则度为1的结点 4)度为1的结点个散为0成1 个数为1，度为2的结点个数为724，叶子结点的个 5)叶子结点只可能在层次最大的两层上出现： 数为725，有725个结点有左抗于，有724个结点 若其右分支下的于孙的最大层次为弘则 有右就子；被树的高度为1山。（性质3、性质4以及完 其左分支下的于孙的最大层次必为成+1，Q 全二叉树的特征) 15/106 圆 16/106 图 6.2二叉树-性质(4) 6.2二叉树-顺序存储结构(1) ,性质5：如果对一棵有个结点的完全二叉树的结点按层 ,二叉树的顺序存储结构 序编号（从第1层到第10g2n+1层，每层从左到右），则 ,类型定义 对任一结点i(1SiSm),有 typedef ElemType SqBiTree[MAX_TREE_SIZE]; (1)如果1，则结点i是二又树的根，无双亲；如果i>L, /0号单元存情根结点 则其双亲是结点山/2： 1)依帮性质5，用一组地址连埃的存储草元依次自上而 (2)如果2i>m,则结点无左孩于（结点为叶于结燕）否 下、自左至右存储完全二叉树上的结点元素； 则其左孩于是结燕2i: —结点在存储区中的相时位置反映它们辽辑上的关系 (3)如果21+1>n,则站点无右就子；否则其右雅子是 2)仅道用于完全二又抛 结点2i+1. ·一般二叉树的顺序存储方法 思考：性质5推广到k又树，站果会如何？ 通过补应站点，将一敝的二义树变成完全二义树 图 空间开铺大！ 17/106 18/106 图13/106 6.2 二叉树 „ 二叉树的定义(递归定义) „ 特点：每个结点至多只有两棵子树，子树有左右之分 „ 二叉树 vs 度不大于2的有序树 „ ADT BinaryTree 二叉树 有序树 14/106 6.2 二叉树-性质(1) „ 二叉树的性质 „ 性质1：二叉树的第i层至多有2i-1个结点(i≥1) „ 性质2：深度为h的二叉树至多有2h –1个结点(h≥1) 思考：性质1和性质2推广到k叉树，结果会如何？ „ 性质3：n0 = n2 + 1 结点总数 n = n0 + n1 + n2 分支数 n-1 = n1 + 2n2 思考：若包含有n个结点的树中只有叶子结点和度为k 的结点，则该树中有多少叶子结点？ ki-1 (kh-1)/(k-1) n = n0+nk, n-1 = knk => n0 = n-(n-1)/k 15/106 6.2 二叉树-性质(2) „ 满二叉树：一棵深度为k且有2k –1个结点的二叉树 (k≥0) „ 完全二叉树：对于深度为k的完全二叉树，则 1) 前k-1层为满二叉树； 2) 第k层结点依次占据最左边的位置； 3) 一个结点有右孩子，则它必有左孩子； 4) 度为1的结点个数为0或1 5) 叶子结点只可能在层次最大的两层上出现； 6) 对任一结点，若其右分支下的子孙的最大层次为l, 则 其左分支下的子孙的最大层次必为l或l+1。 16/106 6.2 二叉树-性质(3) „ 性质4：具有n个结点的完全二叉树的深度为 由性质2 2k-1-1 < n ≤ 2k-1 或 2k-1 ≤ n < 2k 于是 k-1 ≤ log2n < k 例：若一个完全二叉树有1450个结点，则度为1的结点 个数为 1 ，度为2的结点个数为 724 ，叶子结点的个 数为 725 ，有 725 个结点有左孩子，有 724 个结点 有右孩子；该树的高度为 11 。(性质3、性质4以及完 全二叉树的特征) ⎣log2 n⎦ +1 17/106 6.2 二叉树-性质(4) „ 性质5：如果对一棵有n个结点的完全二叉树的结点按层 序编号(从第1层到第 层，每层从左到右)，则 对任一结点i (1 ≤ i ≤ n)，有 (1) 如果i=1，则结点i是二叉树的根，无双亲；如果i >1, 则其双亲是结点 ； (2) 如果2i > n，则结点i无左孩子(结点i为叶子结点)；否 则其左孩子是结点2i ； (3) 如果2i + 1> n，则结点i无右孩子；否则其右孩子是 结点2i + 1。 思考：性质5推广到k叉树，结果会如何？ ⎣ ⎦ log2 n +1 ⎣ ⎦ i / 2 18/106 6.2 二叉树-顺序存储结构(1) „ 二叉树的顺序存储结构 „ 类型定义 typedef ElemType SqBiTree[MAX_TREE_SIZE]; //0号单元存储根结点 1) 依据性质5，用一组地址连续的存储单元依次自上而 下、自左至右存储完全二叉树上的结点元素； ——结点在存储区中的相对位置反映它们逻辑上的关系 2) 仅适用于完全二叉树 „ 一般二叉树的顺序存储方法 通过补虚结点，将一般的二叉树变成完全二叉树 空间开销大！