性质2 深度为k的二叉树上至多含21 个结点(k≥1)。 证明 基于上一条性质,深度为k的二叉 树上的结点数至多为 20+21+………+2k1=2k-1。 四川大学计算机(软件)学院
四川大学 计算机(软件)学院 • 性质 2 ： 深度为 k 的二叉树上至多含 2 k -1 个结点（k≥1）。 证明： 基于上一条性质，深度为 k 的二叉 树上的结点数至多为 2 0+21+ +2k-1 = 2k -1
性质3 对任何一棵二叉树,若它含有n个叶 子结点、n2个度为2的结点,则必存在 关系式:nn=n2+1。 证明 设二叉树上结点总数n=n0+n1+n2 又二叉树上分支总数b=n1+2n2 而b=n-1=n0+n1+n2-1 由此,〃D四的大学计算机(软件学院
四川大学 计算机(软件)学院 • 性质 3 ： 对任何一棵二叉树，若它含有n0 个叶 子结点、n2 个度为 2 的结点，则必存在 关系式：n0 = n2+1。 证明： 设 二叉树上结点总数 n = n0 + n1 + n2 又 二叉树上分支总数 b = n1+2n2 而 b = n-1 = n0 + n1 + n2 - 1 由此， n0 = n2 + 1
两类特殊的二叉树: 满二叉树:指的是 2 ③ 深度为且含有个456⑦ 结点的二叉树。 8⑨9⑩①①20314⑩5 完全二叉树:树 人a 中所含的n个结点 b 和满二叉树中编号 为1至n的结点 对应。 h①① 四川大学计算机(软件)学院
四川大学 计算机(软件)学院 两类特殊的二叉树： 满二叉树：指的是 深度为k且含有2 k -1个 结点的二叉树。 完全二叉树：树 中所含的 n 个结点 和满二叉树中编号 为 1 至 n 的结点一 一对应。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 a b c d e f g h i j
性质4: 具有n个结点的完全二叉树的深度为 L log,n/+1。 证明 设完全二叉树的深度为k 则根据第二条性质得2″k≤n<2k 即k-1≤log2n<k 因为k只能是整数,因此,k=ogn/+1 四川大学计算机(软件学院
四川大学 计算机(软件)学院 • 性质 4 ： 具有 n 个结点的完全二叉树的深度为 log2n +1 。 证明： 设完全二叉树的深度为 k 则根据第二条性质得 2 k-1≤ n < 2 k 即 k-1 ≤ log2 n < k 因为 k 只能是整数，因此， k =log2n + 1
性质5 若对含n个结点的完全二叉树从上到下且从左 至右进行1至n的编号,则对完全二叉树中任意 个编号为i的结点 (1)若1,则该结点是二叉树的根,无双亲 否则,编号为∠i2)的结点为其双亲结点 (2)若2>n,则该结点无左孩子 否则,编号为2的结点为其左孩子结点 (3)若2计+1>n,则该结点无右孩子结点, 否则,编号为2计+的结点为其有孩子结点 四川大学
四川大学 计算机(软件)学院 • 性质 5 ： 若对含 n 个结点的完全二叉树从上到下且从左 至右进行 1 至 n 的编号，则对完全二叉树中任意 一个编号为 i 的结点： (1) 若 i=1，则该结点是二叉树的根，无双亲， 否则，编号为 i/2 的结点为其双亲结点； (2) 若 2i>n，则该结点无左孩子， 否则，编号为 2i 的结点为其左孩子结点； (3) 若 2i+1>n，则该结点无右孩子结点， 否则，编号为2i+1 的结点为其右孩子结点