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

vast的天语 · 2018-4-30 01:58:29

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; }

leon51771116 · 2018-4-30 01:58:30

完全二叉树总结点数加一再除以二就是叶子节点数

kingfeng588 · 2018-4-30 01:58:31

设一棵完全二叉树共有699个结点.

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

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

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

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

最后一层叶子结点个数为：699-（1023-512）=188

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

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

不确定有没有算对.大概思路应该是这样的.希望对你有帮助

tattackor · 2018-4-30 01:58:32

1、首先需要求出这棵树的深度.也就是说这棵树有多少层.
2、完全二叉树有一个性质：具有n个结点的完全二叉树的深度为log2n(2是下标)+1.
根据这个性质,就可以求得完全二叉树的深度为10
10层满二叉树的总结点数为1023,最后一层的结点数应该是2的9次方为512,所以肯定699个结点肯定不是满二叉树.叶子节点出现在最后两层上.
最后一层叶子结点个数为：699-（1023-512）=188
倒数第二层的叶子节点数为：（512-188)/2=162
叶子总数应该是：188+162 = 250

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

4 个回复