二叉树的高度，深度和结点计算

二叉树的高度，深度和结点计算

二叉树是数据结构中常用的题目，下面简单介绍一下；

满二叉树：每层都是满的；

完全二叉树：除最后一层外，每层都是满的，并且或者最后一层是满的，或者是在右边缺少连续若干结点;

某节点的深度是指从根节点到该节点的最长简单路径边的条数

高度是指从该节点到叶子节点的最长简单路径边的条数

以图为例：

深度为n，最多有2ⁿ-1个结点【n≥1】,如图：

第i层，最多有2的（i-1）次方个结点；

具有n个结点的完全二叉树的深度为floor(log2n)+1，如图：

度：

1、结点所拥有的子树的个数

2、树中各结点度的最大值称为该树的度

叶子结点 就是度为0的结点

n0：度为0的结点数，n1:度为1的结点 n2：度为2的结点数

对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1；

如图：

例题1：

一棵树度为4，其中度为1，2，3，4的结点个数分别为4，2，1，1，则这棵树的叶子节点个数为多少？

解：因为任一棵树中，结点总数=度数*该度数对应的结点数+1，所以：

n0+4+2+1+1 = （0*n0 + 1*4 + 2*2 + 3*1 + 4*1）+1

则：n0=8

其中：n0表示叶子结点。

例题2：

一颗二叉树的叶子节点有5个，度为1的结点有3个，该二叉树的结点总个数是？

例题3：

深度为7的完全二叉树共有125个结点，则该完全二叉树的叶子结点为？