为什么完全二叉树中度为1的结点只能是1或0?

 我来答
didato
2011-08-18 · TA获得超过189个赞
知道答主
回答量:120
采纳率:100%
帮助的人:23.7万
展开全部
看起来,你对二叉树的概念还不是很清楚:
完全二叉树定义
  完全二叉树(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,有如下特点:
  (1)若i为奇数且i>1,那么tree的左兄弟为tree[i-1];
  (2)若i为偶数且i<n,那么tree的右兄弟为tree[i+1];
  (3)若i>1,tree的双亲为tree[i div 2];
  (4)若2*i<=n,那么tree的左孩子为tree[2*i];若2*i+1<=n,那么tree的右孩子为tree[2*i+1];
  (5)若i>n div 2,那么tree为叶子结点(对应于(3));
  (6)若i<(n-1) div 2.那么tree必有两个孩子(对应于(4))。
  (7)满二叉树一定是完全二叉树,完全二叉树不一定是满二叉树
  完全二叉树第i层至多有2^(i-1)个节点,共i层的完全二叉树最多有2^i-1个节点。
编辑本段
完全二叉树叶子结点的算法

  如果一棵具有n个结点的深度为k的二叉树,它的每一个结点都与深度为k的满二叉树中编号为1~n的结点一一对应,这棵二叉树称为完全二叉树。
  可以根据公式进行推导,假设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 ,就可根据完全二叉树的结点总数计算出叶子结点数。
以上摘自【百度】百科。
已赞过 已踩过<
你对这个回答的评价是?
评论 收起
axizn
2011-08-18
知道答主
回答量:53
采纳率:0%
帮助的人:29万
展开全部
这是根据完全二叉树的定义得出的,完全二叉树左右子树的深度之差不大于1,所以要么只有一个度为1的结点,要么没有,你可以随便画一个完全二叉树就看出来了
本回答被提问者采纳
已赞过 已踩过<
你对这个回答的评价是?
评论 收起
推荐律师服务: 若未解决您的问题,请您详细描述您的问题,通过百度律临进行免费专业咨询

为你推荐:

下载百度知道APP,抢鲜体验
使用百度知道APP,立即抢鲜体验。你的手机镜头里或许有别人想知道的答案。
扫描二维码下载
×

类别

我们会通过消息、邮箱等方式尽快将举报结果通知您。

说明

0/200

提交
取消

辅 助

模 式