二级C语言中"告诉了完全二叉树的总结点数,怎么求它的叶子结点数"?

论坛 期权论坛 期权     
婥媈踺—小来   2018-4-26 13:54   8562   4
分享到 :
0 人收藏

4 个回复

倒序浏览
2#
vast的天语  1级新秀 | 2018-4-30 01:58:29 发帖IP地址来自
typedef char DataType;//定义DataType类型  typedef struct node{  DataType data;  struct node *lchild, *rchild;//左右孩子子树  }BinTNode; //结点类型  typedef BinTNode *BinTree;//二叉树类型  int Node(BinTree T)  { //算结点数  if(T)  return Node(T->lchild ) + Node ( T->rchild )+1;  else  return 0;  } int Leaf(BinTree T)  {  if(T)  { if ((T->lchild==NULL )&&( T->rchild==NULL ) ) return 1;  else return Leaf(T->lchild ) +Leaf ( T->rchild );  } else return 0;  }
3#
leon51771116  2级吧友 | 2018-4-30 01:58:30 发帖IP地址来自
完全二叉树总结点数加一再除以二就是叶子节点数
4#
kingfeng588  1级新秀 | 2018-4-30 01:58:31 发帖IP地址来自
设一棵完全二叉树共有699个结点.

首先需要求出这棵树的深度。。。。也就是说这棵树有多少层。。。

完全二叉树有一个性质: 具有n个结点的完全二叉树的深度为log2n(2是下标)+1。

根据这个性质,就可以求得完全二叉树的深度为10

10层满二叉树的总结点数为1023,最后一层的结点数应该是2的9次方为512,所以肯定699个结点肯定不是满二叉树。。。叶子节点出现在最后两层上。。。

最后一层叶子结点个数为:699-(1023-512)=188

倒数第二层的叶子节点数为: (512-188)/2=162

叶子总数应该是:188+162 = 250

不确定有没有算对.大概思路应该是这样的.希望对你有帮助
5#
tattackor  4级常客 | 2018-4-30 01:58:32 发帖IP地址来自
1、首先需要求出这棵树的深度.也就是说这棵树有多少层.
2、完全二叉树有一个性质: 具有n个结点的完全二叉树的深度为log2n(2是下标)+1.
根据这个性质,就可以求得完全二叉树的深度为10
10层满二叉树的总结点数为1023,最后一层的结点数应该是2的9次方为512,所以肯定699个结点肯定不是满二叉树.叶子节点出现在最后两层上.
最后一层叶子结点个数为:699-(1023-512)=188
倒数第二层的叶子节点数为: (512-188)/2=162
叶子总数应该是:188+162 = 250
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

积分:
帖子:
精华:
期权论坛 期权论坛
发布
内容

下载期权论坛手机APP