Question

已知一棵完全二叉树中共有768个结点，则改树中共有多少叶子结点？

Answer 1

已知一棵完全二叉树中共有768个结点，则改树中共有1个叶子节点。

令二叉树中叶子个数为L，只有一个孩子的结点数为S， 有两个孩子的结点数为D，所有结点数位n，则有1） n=L+S+D。n-1=2D+S，原因是除根结点外每个叶子结点都由一条入边， 且该入边是由其父节点引出的，根据完全二叉树的性质可知S=0或S=1， 从n=768可知 s=1。

扩展资料：

完全二叉树——若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第h层有叶子结点，并且叶子结点都是从左到右依次排布，这就是完全二叉树。

叉树是一个连通的无环图，并且每一个顶点的度不大于3。有根二叉树还要满足根结点的度不大于2。有了根结点之后，每个顶点定义了唯一的父结点，和最多2个子结点。然而，没有足够的信息来区分左结点和右结点。如果不考虑连通性，允许图中有多个连通分量，这样的结构叫做森林。

参考资料来源：百度百科-二叉树

Answer 2

令二叉树中叶子个数为L, 只有一个孩子的结点数为S， 有两个孩子的结点数为D，所有结点数位n；
则有1） n=L+S+D
2） n-1=2D+S, 原因是除根结点外每个叶子结点都由一条入边， 且该入边是由其父节点引出的；
根据完全二叉树的性质可知S=0或S=1， 从n=768可知 s=1
所以得到方程：
L+D+1=768
2D+1=768-1
解方程有L=384， 即有384个叶子结点。