这是一个数据结构二叉树问题

Question

对任何一颗二叉树T，如果其终端节点数为n0,度为2的节点数为n2，则n0=n2+1
这是为什么呢？求大佬们帮忙解答！另外，满二叉树和完全二叉树区别是？

Answer 1

任何一个二叉树都可以通过上面的图生成（当然，单个节点的n2=0，n0=1这个就不讨论了）
初始状态下要么左边要么右边（或者右边旋转，是一样的），那么n0=n2+1显然成立
然后无非是两个操作，把其中的一个子节点换成左边或者右边
如果换成左边n0=n0-1+2=n0+1 n2=n2+1，也就是n0 n2都+1，显然n0=n2+1还是成立
如果换成右边n0=n0-1+1=n0 n2不变，也就是n0 n2都不变，显然还是n0=n2+1成立
任何二叉树都可以通过以上2个替换得到，也就是每次要么n0 n2都+1，要么都不变，所以一直维持n0=n2+1的关系

满二叉树是完全二叉树的特例，完全二叉树是除了最后一层以外，是满二叉树，最后一层的结点都连续集中在最左边