Question

请问二叉树的节点数怎么求的？

Answer 1

完全二叉树的叶子节点数公式为：

设叶子节点数为n0, 度为1的节点数为n1，度为2的节点数为n2，总节点为n。

1、当n为奇数时（即度为1的节点为0个），n0= (n+1)/2。

2、当n为偶数（即度为1的节点为1个）， n0= n/2。

n1，n2，都可以求。

特殊类型：

1、满二叉树：如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树。

2、完全二叉树：深度为k，有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1到n的结点一一对应时，称为完全二叉树。

3、完全二叉树的特点是叶子结点只可能出现在层序最大的两层上，并且某个结点的左分支下子孙的最大层序与右分支下子孙的最大层序相等或大1。

相关术语：

1、结点：包含一个数据元素及若干指向子树分支的信息。

2、结点的度：一个结点拥有子树的数目称为结点的度。

3、叶子结点：也称为终端结点，没有子树的结点或者度为零的结点。

4、结点的层次：从根结点开始，假设根结点为第1层，根结点的子节点为第2层，依此类推，如果某一个结点位于第L层，则其子节点位于第L+1层。

5、树的深度：也称为树的高度，树中所有结点的层次最大值称为树的深度。

以上内容参考   百度百科-二叉树