若设度为1的结京有M1个,总结点个数 为n,总泌数为e,则根据二叉树的定义, n=no+,+n e=2i 2 n n-1 因此,有2m2+n1=n0+n1+n2-1 2 0 0 2 +1
证明： 若设度为1的结点有n1个，总结点个数 为n，总边数为e，则根据二叉树的定义， n = n0 + n1 + n2 e = 2n2 + n1 = n – 1 因此，有 2n2 + n1 = n0 + n1 + n2 – 1 n2 = n0 - 1 n0 = n2 + 1
定义1满二叉树( Full Binary Tree) 一棵深度为k且有2k-1个结点的二叉树称为 满二叉树。 定义2完全二叉树( omplete Binary Tree) 深度为k,有n个结点的二叉树,当且仅当其 每一个结点都与深度为k的满二叉树中编号从1至 n的结点一一对应时,称之为完全二叉树。 或者:若设二叉树的深度为h,则共有h层 除第h层外,其它各层(0~h-1)的结点数都达到最 大个数,第h层从右向左连续缺若千结点
定义1 满二叉树(Full Binary Tree) 一棵深度为k且有2 k -1个结点的二叉树称为 满二叉树。 定义2 完全二叉树(Complete Binary Tree) 深度为k，有n个结点的二叉树，当且仅当其 每一个结点都与深度为k的满二叉树中编号从1至 n的结点一一对应时，称之为完全二叉树。 或者：若设二叉树的深度为h，则共有h层。 除第h层外，其它各层(0h-1)的结点数都达到最 大个数，第h层从右向左连续缺若干结点
7(8(9⑩①23⑦③8(9 (a)满二又树 b)完全二叉树 完全二叉树的特点是: 1)只允许最后一层有空缺结点且空缺在右边, 即叶子结点只能在层次最大的两层上出现; 2)对任一结点,如果其右子树的深度为j,则其 左子树的深度必为或+1
完全二叉树的特点是： 1）只允许最后一层有空缺结点且空缺在右边， 即叶子结点只能在层次最大的两层上出现； 2）对任一结点，如果其右子树的深度为j，则其 左子树的深度必为j或j+1
性质4具有n个结点的完全二叉树的深度为 Llog2 n]+1 证明:设完全二叉树的深度为则有 2k-1-1<n≤2k-12k1<n<2ke 取对数k-1≤log2n<k 因为k为薏数,所以k=Llog2n」+1 说明:常出现在选择题中
性质4 具有n个结点的完全二叉树的深度为 log2n +1 证明：设完全二叉树的深度为k，则有 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,2,…,n,然后按此结点编号将树中各结点顺 序地存放于一个一维数组中,并简称编号为的结 点为结点(1≤≤m)则有以下关系 若i==1,则i是二叉树的根,无双亲 着>1,则i的双亲为i2」 若2*≤n,则i的左孩子为2*,否则无左孩子 若2计1≤n,则i的右孩子为2计1,否则无右 孩子 若i为偶数,且i!=n,则其右兄弟为计1 若i为奇数,且i!=1,则其左兄弟为i-1 i所在层次为Llog2i+1
性质5 如果将一棵有n个结点的完全二叉树的结 点按层序(自顶向下，同一层自左向右）连续编 号1, 2, …, n，然后按此结点编号将树中各结点顺 序地存放于一个一维数组中, 并简称编号为i的结 点为结点i (1 i n)。则有以下关系： ◼ 若i == 1, 则 i 是二叉树的根，无双亲 若i > 1, 则 i 的双亲为i /2 ◼ 若2*i ≤ n, 则 i 的左孩子为2*i，否则无左孩子 若2*i+1 ≤ n, 则 i 的右孩子为2*i+1，否则无右 孩子 ◼ 若 i 为偶数, 且i != n, 则其右兄弟为i+1 若 i 为奇数, 且i != 1, 则其左兄弟为i-1 ◼ i 所在层次为 log2 i +1