二叉树节点数该怎么计算?有几种算法?

TheDisguiser 2020-05-28 21:51:15 java常见问答 5674

每一棵二叉树中都有左右两棵子树,子树中又有无数节点,那你们知道子树中的节点该怎么计算吗?快来跟小编了解一下吧。

二叉树算法概念

对于任何一棵二叉树来说,其叶子结点的数目为n0,且其度数为2的结点数n2,则n0=n2+1.

证明:对于此二叉树:

二叉树节点数怎么算

设其度数为1的结点数为n1. 从下往上看,每个结点都会有一个边朝上,除了根结点,则边总数为:N=n0+n1+n2-1 ①

从上往下看,度数为2的结点有两个边,度数为1的结点有1个边,度数为0的结点有0个边,则边总数为:N=0*n0+1*n1+2*n2 ②

联系① ②,得:n0=n2+1

二叉树的叶子节点数含义:没有子树的结点是叶子结点。它的结点的度就是指,该结点的子树的个数,在二叉树中,不存在度大于2的结点。

计算公式:n0=n2+1

n0 是叶子节点的个数

n2 是度为2的结点的个数

n0=n2+1=5+1=6

故二叉树有5个度zhidao为2的结点,则该二叉树中的叶子结点数为6。

二叉树节点算法

1)、程序计算法

int leaf(bitree t)
{
if(!t)
return 0; //空树,无叶子
else if(!t->lch && !t->rch)
return 1;
else
return (leaf(t->lch) + leaf(t->rch));
}

2)、手动计算公式

利用“树中所有结点的度数之和再加1等于结点数”

二叉树节点数怎么算

则叶子节点数,即为:

二叉树节点数怎么算

3)、递归算法

public int getTotal(Node node){
if(node == null){
return 0;
}
return getTotal(node.left) + getTotal(node.right) + 1;}

以上就是今天的所有内容了,二叉树是树结构中一个较复杂的结构,它有很多分支,分支又有分支,所以想要深入了解二叉树还是要一定的努力的。如果你还想要了解更多二叉树相关的java常见问答知识,就请来关注我们的网站吧。

推荐阅读:

二叉树的度是什么意思?二叉树是什么?

二叉树的序列化与反序列化(代码实现和思路)

二叉树的深度怎么算?求二叉树深度的算法(思路和代码实现)