性质3: 对任何一棵二叉树,若它含有n个叶 子结点、n2个度为2的结点,则必存在 关系式:n=n2+1。 证明 设二叉树上结点总数n=n+n1+n2 又二叉树上分支总数b=m1+2n2 而b=n-1=n0+n1+n2-1 由此,n=n2+1
性质 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 深度为k且含有2k-1个 5 6( 结点的二叉树。 8⑨9⑩0⑩1①2①31415 完全二叉树:树 中所含的n个结点 和满二叉树中编号 为1至n的结点 对应
两类特殊的二叉树： 满二叉树：指的是 深度为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
性质 具有n个结点的完全二叉树的深度 为llog2n/+1。 证明: 设完全二叉树的深度为k 则根据第二条性质得2k≤n<2k 即k-l≤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)若i1,则该结点是二叉树的根,无双亲, 否则,编号为∠i2)的结点为其双亲结点 (2)若2>n,则该结点无左孩子 否则,编号为i的结点为其左孩子结点 (3)若2计+1>n,则该结点无右孩子结点, 否则,编号为计+1的结点为其右孩子结点
性质 5 ： 若对含 n 个结点的完全二叉树从上到下且从左 至右进行 1 至 n 的编号，则对完全二叉树中任意 一个编号为 i 的结点： (1) 若 i=1，则该结点是二叉树的根，无双亲， 否则，编号为 i/2 的结点为其双亲结点； (2) 若 2i>n，则该结点无左孩子， 否则，编号为 2i 的结点为其左孩子结点； (3) 若 2i+1>n，则该结点无右孩子结点， 否则，编号为2i+1 的结点为其右孩子结点
6.3 二叉树的存储结构 二叉树的顺序 存储表示 、二叉树的链式 存储表示 基卖宝睡
6.3 二叉树的存储结构 二、二叉树的链式 存储表示 一、 二叉树的顺序 存储表示