题目

有一棵三叉树,度为1,2,3的节点数分别为n1,n2,n3,则该三叉数的叶子节点数n0为多少?

提问时间：2020-10-21

答案

数据结构吧,设这棵树总节点数为n,边数为B,那么存在以下关系B=n-1,同时总节点数为n=n0+ n1+n2+n3,而树有这样的性质：有一个度为1的节点就有一条边,有一个度为2的节点就有两条边,依此类推,所以,B=n1+2*n2+3*n3(星号是乘,字母后面数字是下标),所以n0+n1+n2+n3=n1+2*n2+3*n3+1,所以n0=n2+2*n3+1,以此类推这个公式对度为m仍适用,(记得我吗,百度好友,有问题可以在问我哈)