二叉树度为二和度为零的关系？
2021-11-06
二叉树度为2的结点个数始终比度为0的结点个数少1。
二叉树中，结点的度指这个结点的直接子结点个数。叶子结点的度为0，只有一个子结点的结点度数为1，左右子结点都具备的度数为2。
这里设度数为0的结点有n0个，度数为2的结点有n2个。
1、初始时，二叉树只有一个度数为0的根结点，n0=1，n2=0，n0=n2+1。
2、我们为根结点加上一个子结点，根结点的度变成了1，但是因为多了个叶子结点，所以n0仍然是1，仍然满足n0=n2+1。
3、再为根结点的子结点加上子结点，和第2步一样，n0=1，n2=0，n0=n2+1。
4、如果撤销第3步，为根结点加上另一个子结点，度为2的结点变成了1个，但度为0的就有了两个，n0=2，n2=1，仍然满足n0=n2+1。
综上，继续添加新的结点，都会与第2到4步的情况一样。所以，二叉树中，始终度为0的结点比度为2的结点多1个。
大家都在看
本站系本网编辑转载，转载目的在于传递更多信息，并不代表本网赞同其观点和对其真实性负责。如涉及作品内容、版权和其它问题，请在30日内与本网联系，我们将在第一时间删除内容！本站文章版权归原作者所有，内容为作者个人观点。本站只提供参考并不构成任何投资及应用建议。本站拥有对此声明的最终解释权。