“完全二叉树中,只存在度为2的结点和度为0的结点”

完全二叉树中,只存在度为2的结点和度为0的结点,而二叉树的性质中有一条是：n0=n2+1；n0指度为0的结点,即叶子结点,n2指度为2的结点,所以2n2+1=699 n2=349；n0=350

pow(2,i-1)
pow(2,i)-1

完全二叉树定义完全二叉树(Complete Binary Tree)若设二叉树的深度为h,除第 h 层外,其它各层 (1～h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树.完全二叉树是由满二叉树而引出来的.对于深度为K的,有N个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树.若一棵二叉树至多只有最下面的两层上的结点的度数可以小于2,并且最下层上的结点都集中在该层最左边的若干位置上,则此二叉树成为完全二叉树.完全二叉树特点叶子结点只可能在最大的两层上出现,对任意结点,若其右分支下的子孙最大层次为L,则其左分支下的子孙的最大层次必为L 或 L+1；出于简便起见,完全二叉树通常采用数组而不是链表存储,其存储结构如下:var tree:array[1..n]of longint;{n:integer;n>=1}对于tree[i],有如下特点：（1）若i为奇数且i>1,那么tree的左兄弟为tree[i-1]；（2）若i为偶数且i1,tree的双亲为tree[i div 2]；（4）若2*i

看看我画的图吧!

二叉树性质：n0 = n2 + 1
因为n0 + n1 + n2 = 1001
所以2n2 + 1 + n1 = 1001
由于该等式右边为奇数,左边的n1只能是偶数
又因为完全二叉树中度为1结点个数n1要么是0要么是1
所以只能是0
因此n2 = 500
所以n0 = 501

B：350
首先你得知道什么叫完全二叉树!
完全二叉树(Complete Binary Tree)
若设二叉树的高度为h,除第 h 层外,其它各层 (1～h-1) 的结点数都达到最大个数,第 h 层所有的节点都连续集中在最左边,这就是完全二叉树. 完全二叉树是由满二叉树而引出来的.对于深度为K的,有N个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树.
做这种题目你要知道二叉树的两个特点!第k层的节点个数最多2^(k-1)个,高度为k层的二叉树,最多2^k-1个节点!
则在本题目中,共699个节点,因为是完全二叉树,2^10-1>699>2^9-1,所以高度为10,可以确定1到9层全满,节点总算为511,剩下的188个肯定为叶子节点!第10层上的188个节点挂在第九层的188/2=94个节点上,则第九层剩下的2^（9-1）-94=162个也为叶子节点,最后总共188+162=350个叶子节点!

25分就象得到这种高难度的东西,没门!不信你看,到问题过期了都每人答.
建议你悬赏200分试试.

答案不对.
可以根据公式进行推导,假设n0是度为0的结点总数（即叶子结点数）,n1是度为1的结点总数,n2是度为2的结点总数,由二叉树的性质可知：n0＝n2＋1,则n= n0＋n1＋n2（其中n为完全二叉树的结点总数）,由上述公式把n2消去得：n= 2n0+n1－1,由于完全二叉树中度为1的结点数只有两种可能0或1,由此得到n0＝（n＋1）/2或n0＝n/2,合并成一个公式：n0＝（n＋1）/2 ,就可根据完全二叉树的结点总数计算出叶子结点数.

如果根的层次算1,则1580个结点的完全二叉树有11层,因为2^10

错误

选C.

你没错,错的是印刷, 2h-1+1 明显是 2^(h-1)+1

根据“二叉树的第i层至多有2^(i − 1)个结点；深度为k的二叉树至多有2^k − 1个结点（根结点的深度为1）”这个性质：
因为2^9-1 < 700 < 2^10-1 ,所以这个完全二叉树的深度是10,前9层是一个满二叉树,
这样的话,前九层的结点就有2^9-1=511个；而第九层的结点数是2^(9-1)=256
所以第十层的叶子结点数是700-511=189个；
现在来算第九层的叶子结点个数.
由于第十层的叶子结点是从第九层延伸的,所以应该去掉第九层中还有子树的结点.因为第十层有189个,所以应该去掉第九层中的（189+1）/2=95个；
所以,第九层的叶子结点个数是256-95=161,加上第十层有189个,最后结果是350个.

为9啊
255个结点排满8层
多一个结点
所以一共有9层

命题正确.
对完全二叉树的编号是由上而下,由左而右进行的,所以若某节点无左孩子,则必然无右孩子.即为叶子结点.

完全二叉树的节点数是奇数,说明此完全二叉树也是满二叉树,也就是说每个内部节点正好都有2个叶结点.
设内部节点数为a,叶节点数为b,结点总数为m,明显有a+b=m (1)
非空满二叉树中所有节点的出度正好等于入度,每个内部节点出度为2,叶节点出度为0,所有节点的出度和为2a；根节点入度为0,其他节点的入度为1,所有节点的入度和为a+b-1;因此有2a=a+b-1 (2)
由(1),(2)得 b=(m+1)/2,a=(m-1)/2,b=a+1
也就是说,非空满二叉树的叶节点数正好比内部节点数多1
此完全二叉树的结点总数为2n-1,因此其叶结点数为n.

二叉树的性质4 具有n个结点的完全二叉树的深度为int(log2 n)+1
int(log2 100)+1=7
性质5：如果对一棵有n个结点的完全二叉树的结点按层序编号,则对任一结点i(1n,则结点i无左孩子；如果2in,则结点i无右孩子；如果2i+1

一棵有512个结点的完全二叉树的高度为10（独根树高度为1）
在一棵非空二叉树中,若度为0的结点的个数n,度为2的结点个数为m,则有n=m+1

一个有4层结点的完全二叉树.按前序遍历周游给结点从1开始编号,则第21号结点的父结点是19号（注释：根的层数为0）
假设一棵二叉树中,度为2的结点有20个,度为1的结点有10个,度为0的结点有多少个?度为0的结点=度为2的结点+1=21某二叉树中序序列为A,B,C,D,E,F,G, 前序序列为E,A,C,B,D,G,F, 则后序序列是?BDCAFGE

完全二叉树,所以第k曾只有1个节点,其他几层节点都是满的,就这样算就行了

具有n个结点的完全二叉树的深度为「log2n」+1 !
二叉树的计算方法：
若一棵二叉树为空,则其深度为0,否则其深度等于左子树和右子树的最大深度加1,即有如下递归模型:
depth(b)=0 /*如果b=NULL*/
depth(b)=max(depth(b->left,b->right)+1 /*其它*/
因此求二叉树深度的递归函数如下:
int depth(btree *b)
{
int dep1,dep2;
if(b==NULL)return(0);
else
{ dep1=depth(b->left);
dep2=depth(b->right);
if(dep1>dep2)return(dep1+1);
else return(dep2+1);
}
}
二叉树的基本性质
★树的基本定义
1、树是n(n>=0)个结点的有限集
2、树的结点包含一个数据元素及若干指向其子树的分支
3、结点拥有的子树数称为结点的度
4、度为0的结点称为叶子或终端结点
5、树的度是树内各结点的度的最大值
6、结点的层次从根开始定义起,根为第一层,根的孩子为第二层
7、树中结点的最大层次称为树的深度或高度
8、如果将树中结点的各子树看成从左至右是有次序的（即不能互换）,则称该树为有序树,否则称为无序树.在有序树中,最左边的子树的根称为第一个孩子,最右边的称为最后一个孩子.
★二叉树的定义
二叉树是一种树型结构,它的特点是每个结点至多只有二棵子树（即二叉树中不存在度大于2的结点）,并且,二叉树的子树有左右之分,其次序不能任意颠倒.
★二叉树的性质
性质一 在二叉树的第i层上至多有2i-1个结点
性质二 深度为k的二叉树至多有2k-1个结点（k>=1）
性质三 对任何一棵二叉树T,如果其终端结点数为n0,度为2的结点数为n2,则n0=n2+1
性质四 具有n个结点的完全二叉树的深度为「log2n」+1
性质五 如果对一棵有n个结点的完全二叉树（其深度为「log2n」+1）的结点按层序编号（从第1层到第「log2n」+1层,每层从左到右）,则对任一结点i（1≤i≤n）,有
①如果i=1,则结点i是二叉树的根,无双亲；如果i>1,则其双亲PARENT(i)是结点「i/2」
②如果2i>n,则结点n无左孩子（结点i为叶子结点）；否则其左孩子LCHILD(i)是结点2i
③如果2i+1>n,则结点i无右孩子,否则其右孩子RCHILD(i)是结点2i+1
★先序遍历二叉树的操作定义
若二叉树为空,则空操作,否则
(1)访问根结点
(2)先序遍历左子树
(3)先序遍历右子树
★中序遍历二叉树的操作定义
若二叉树为空,则空操作,否则
(1)中序遍历左子树
(2)访问根结点
(3)中序遍历右子树
★后序遍历二叉树的操作定义
若二叉树为空,则空操作,否则
(1)后序遍历左子树
(2)后序遍历右子树
(3)访问根结点

log2（66+1）=7
深度为7

根据二叉树的性质:对于一棵非空的二叉树,如果叶子节点数为n0,度为2的结点数为n2,则no=n2+1.
根据完全二叉树的定义可得:在完全二叉树中度为1的结点n1只能取两种情况,要么为0,要么为1.所以:n0+n1+n2=100 又n0=n2+1; 2n2=99-n1; 因为结点数为整数,所以n1=1,n2=49,n0=50
所以度为1的结点有一个,叶子结点有50个,度为2的结点为49个

首先注意完全二叉树数的特点：
完全二叉树的特点是：（1）深度为k的完全二叉树的叶子结点都出现在第k层或k－1层.（2）对任一结点,如果其右子树的最大层次为L,则其左子树的最大层次为L或L＋1.
这样意味着,度为1的结点只能为0个或1个!
设度为0的结点（叶子结点）有n0个,设度为1的结点有n1个,设度为2的结点有n2个
则总的结点数n=n0+n1+n2,另一方面,度为结点有两个分支,度为1的结点有一条分支
每个结点都有一条分支和其相连,除了根结点,所以有n=2*n2+n1+1;
这样就有：
n2=n0-1;
从而可推出：
n=2n0-1+n1;
现在回到问题,共有700结点：
701=2n0+n1
而n1只能取0或1,从该题看,只能取1；
所以可得：
n0=700/2=350;
所以共有350个叶子结点

1,根据完全二叉树规律即可判断2*3

完全二叉树的节点数是奇数,说明此完全二叉树也是满二叉树,也就是说每个内部节点正好都有2个叶结点.
设内部节点数为a,叶节点数为b,结点总数为m,明显有a+b=m (1)
非空满二叉树中所有节点的出度正好等于入度,每个内部节点出度为2,叶节点出度为0,所有节点的出度和为2a；根节点入度为0,其他节点的入度为1,所有节点的入度和为a+b-1;因此有2a=a+b-1 (2)
由(1),(2)得 b=(m+1)/2,a=(m-1)/2,b=a+1
也就是说,非空满二叉树的叶节点数正好比内部节点数多1
此完全二叉树的结点总数为2n-1,因此其叶结点数为n.

因完全二叉树： 某一层的结点数据为2^n, n 代表从树根开始的层次编号, 树根层次为0.
2^5 = 32;
2^6 = 64;
40 > 32 && 40 < 64;
所以编号为40的结点一定在第6层次上, 又因其有右子结点.
至少要再增加一层, 这棵树至少有7层.
所以这棵的所有结点 = 2^0 + 2^1 +... + 2^7　= 2^8 - 1 =128 -1 = 127;

设根节点的深度为1.从上到下的个数依次为1/2/4/8……,每层最多有叶子节点的个数为2的（i-1）次方,i 为深度.这里的n=64,因此,64=2的（i-1）方,所以i=7. 但是,由于是完全二叉树,因此可以在第八层里有1个叶子节点（最多只能有一个）,第八层的那个叶子节点将第七层的覆盖.故可能达到的最大深度为8.

解法一：
根据二叉树的性质3可知：叶子结点数n0＝n2+1,
根据完全二叉树的概念可知,度为1的结点数要么为1,要么为0,
二叉树总结点数N＝n0+n1+n2＝2n0+n1－1,
得出n0＝（N+1－n1）/2＝N/2向上取整,
所以本题答案是350个叶子结点.
解法二：
易求出总层数和末层叶子数.总层数k=log2N向上取整 =10;
且前9层总结点数为2^9-1=511 (完全二叉树的前k-1层肯定是满的)
所以末层叶子数为700-511=189个.
请注意叶子结点总数≠末层叶子数!
还应当加上第k-1层（靠右边）的0度结点个数.
末层的189个叶子只占据了上层的95个结点（189/2 ),上层（k=9)右边的0度结点数还有2^(9-1)-95=161个.
所以,全部叶子数＝189(末层)＋161(k-1层)=350个.

假设该完全二叉树的深度为 k,则根据完全二叉树的定义和性质 2有：
2 ^(k-1)－1＜ n ≤2^k－1 或 2^(k-1)≤ n ＜2^k
所以有：k－1≤ log2n＜k
又因为 k是整数,所以,k＝ log2n向下取整 ＋1

O.O!莫非是我算错了o.o?~~~~~为什么我算得结果是344呢~~~~~~~~~~这道题貌似没有直接公式,就算是有不好意思啊我不是太会记公式的人,但是题目的思路很简单,首先通过节点数求出完全二叉树的高度h,这个公式你知道的吧,计算出来结果应该是9,然后你再用节点总数减去前八层的节点数之和就是你所求的结果~~~~
嗯嗯,我又看了看,选b,这个题目没有现成的公式,考验的是你对二叉树的理解能力与数学的思想,首先求出树的高度h,h应该是10不是9,上面我算错了T.T,然后求出一到九层的节点总数,应该是2的9次方减去1,是511,再用节点总数减去255就是最后一层叶子节点的个数699-511=188,而最后一层有188个节点就说明上一层有94个非叶节点,你在用该层的节点总数减去这些非叶子节点就是这一层的叶子节点数,及256-94=162,最后两层的叶子节点数之和就是188+162=350个,所以选B~

A

如果这课完全二叉树是具有最小深度.那么它肯定是满二叉树少一个叶子结点.因此 是log2(N+1)

2^6 < 80 < 2^7 => 这是一棵深度为7的完全二叉树
也就是一棵深度为6的满二叉树,再加上第7层的14个叶子结点
简单画一下图,第6层有32个结点：左边的7个结点都有子节点,度为2；右边的25个结点都是叶子结点
总共有39个叶子结点

你算的是可能是多少,它问的是最多.
节点总数N:2^4≤N≤2^5 - 1 即 16≤N≤31……①
叶子节点数M:8≤M≤16……②
度为2的节点数:①-②:8≤N-M≤15
(N-M)max=15

可用数学归纳法.
当n=1=2^1-1时显然.
假设当n<=2^k-1时具有n个结点的完全二叉树的深度为「log2n」+1,则
当n=2^k（以及2^k+1,...,2^(k+1)-1）时,由归纳假设知前2^k-1个结点构成深度为「log2n」+1的树,再由完全二叉树的定义知剩余的1（或2,...,2^k)个结点均填在第「log2n」+2层上（作为“叶子”）,故深度刚好增加了1.
故n<=2^(k+1)-1时命题成立.证毕.
（首先最好能先从直观上理完全二叉树中：
第1层有1个结点；
第2层有2个结点；
第3层有4个结点；……第k层有2^(k-1)个结点；（前k层共有(2^k)-1个结点,故前面深度刚好是「log2（2^k-1)」+1=k-1+1=k）
）

完全二叉树中第一层有1个结点,第二层有2个结点,以此类推,第 i 层就有2的 i-1 次方个结点,所以列出方程得层数为,以2为底699的对数,再加1,如果结果不为整数的话,向下取整就行了,最后的答案是11层

由于是完全二叉树,因此直接用顺序存储即可.
给定结点i（i >= 0）,可知
非根结点i （i > 0）的父亲结点为P = (i - 1) / 2 按整型规则计算（向下取整）
i的左右孩子结点为L和R为L = 2 * (i + 1) - 1和R = 2 * (i + 1)

完全二叉树定义：除最后一层外,每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点.
深度为5说明二叉树有5层：
第一层——1个根结点（度为2）
第二层——2个子结点（度都为2）
第三层——4个子结点（度都为2）
第四层——要注意由于第五层一定不会全满,所以度一定是8-1个结点,最右边的结点只有一个度,不然就是满二叉树了.
所以度为2的结点数为1+2+4+（8-1）=14
■
/
■ ■
/ /
■ ■ ■ ■
/ / / /
■ ■ ■ ■ ■ ■ ■ 口
/ / / / / / / /
口口口口口口口口口口口口口口口
如图~能看得懂吗?

答案肯定有问题,含有249个节点的完全二叉树是有125个叶子节点的.
你的想法没问题 相信自己

根据完全二叉树的性质,最后一个结点（编号为n）的双亲结点的编号是en
/2?,这是最后一个分支结点,在它之后是第一个终端（叶子）结点,故序号最小的
叶子结点的下标是en/2u+1

K = 7层,完全二叉树就是满二叉去掉或者不去掉右边底层的一些东西.所以你能确定的就是这棵树高度7并且前6层是满二叉树.前6层结点个数应该是2的（K）次方-1 即63个结点.剩余结点个数为 38个结点.也就是说这38个结点处在第七层.当前这叶子结点包含这38个.对于第七层应该具有的结点数目为 2的（k-1）也即是 2的6次方64个结点.那么剩余64-38 = 26个结点就是空结点（假想）.这26个结点对应第六层的13个结点.那么 13+38 = 51个结点.就是所求的叶子结点.不知道这么算有道理不.

只要了解完全二叉树的结构的话,很好算的呀.我算了下度为2的点节点是511个,剩下的1000-511=489都是叶子节点啦,呵呵,希望对你有帮助,

答案是B 49*2+1=99

2的(h-1)次方 小于n
2的h次方 大于等于n
所以 h=log 2为低 n的对数

已发送您的邮箱

完全二叉树除了最后一层,是一棵满二叉树,其节点数为2^k-1,k是层数
根据题目,除了最后一层,上面还有4层,所以节点数为2^4-1,就是15
加上最后一层的7个节点,共22个节点

满二叉树:除了叶节点,每个父亲节点都有两个子树的,满满的二叉树
完全二叉树:所有节点集中在树左边的二叉树,就是说除了叶节点,每个节点都只有左节点或者有两个节点,而没有只有右节点情况

简便算法：(int)((节点数+1)/2),即(int)(739+1)/2 = 370
标准步骤：
512