Question

为什么在任意一棵二叉树中,叶结点的个数为n1,度为2的结点数为n2,则n1=n2+1

Answer 1

对一颗n高的树来说,叶节点只存在于第n层,二叉树第n层的节点数=2^(n-1),所以一颗满二叉树第n层节点数为2^(n-1),除第n层外的所有节点都是度2的节点,总数为2^n-1 - 2^(n-1)
2^(n-1) - [2^n-1 - 2^(n-1)] - = 2^n - 2^n + 1 = 1
每个叶节若增加一个子节点,则该节点变为度1节点,度2节点数不变,同时增加的子节点变为新的叶节点,所以仍有关系式n1=n2+1,若增加到2个子节点,则度2节点数增1,叶节点数也增1,关系式还是不变为n1=n2+1
所以可得