二叉树

节点

二叉树中每个元素都称为节点。

度

  • 度的定义：节点所拥有的子树的数目称为该节点的度
  • 注意： 叶子节点的度为0

二叉树的度表示节点的子树或直接继承者的数目，二叉树的度是一个子树或单子树。2度是两个孩子，或者左和右子树有两个叉树，最大度数为2。

叶子

叶是叶节的缩写。叶子或叶子指的是网络结构中的计算机，它接收来自靠近中心的计算机而不是更远的计算机的信号。叶节点是树的底部段中的节点，叶节点不具有子节点。叶节点的结构比中间节点的结构稍微复杂一些。以便在格式化的叶节点中保存多个条目。

总结

“二叉树中的度“是指树中最大的结点度，叶子结点是终端结点，是度为 0 的结点。

二叉树的度是指树中所以结点的度数的最大值。二叉树的度小于等于2，因为二叉树的定义要求二叉树中任意结点的度数（结点的分支数）小于等于2 ，并且两个子树有左右之分，顺序不可颠倒。

叶子结点就是度为0的结点，也就是没有子结点的结点叶子。如n0表示度为0的结点数，n1表示度为1的结点，n2表示度为2的结点数。在二叉树中：n0=n2+1；N=n0+n1+n2（N是总结点）。

例

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

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

n0+4+2+1+1 = （0n0 + 14 + 22 + 31 + 4*1）+1

则：n0=8

其中：n0表示叶子结点。

我们设度为0,1,2的节点分别为n0,n1,n2个，那么节点总数n=n0+n1+n2，然而边数b=n-1（除去最顶上的节点）,并且b=n1+2*n2=n-1=n0+n1+n2-1，由此我们可以推出n0=n2+1

也就是说叶子节点要比度为二的节点多一个。
b=n1+2*n2 度为2的节点有两条边，度为1的节点有1条

结点总数=度数*该度数对应的结点数+1
n=n2 *2+n1 *1+0 *n0+1

因为度为2的节点连接两个节点，度为1的节点连接一个节点，最后加1个最顶端的根节点就行