二叉树专题[校招]

1. 一个具有20个叶子节点的二叉树、它有（）个度为2的节点

A.16
B.21
C.17
D.19

N0=N2+1

可以推导出来的：

N = N0+N1+N2       （节点总数由度为0的节点数+度为1的节点数+度为2的节点数 ）

N-1= 0*N0+1*N1+2*N2    （从下往上以树枝看，一个节点对应一个树枝，除了根节点外，因此共有N-1根树枝，这个式子表示的是树枝的关系）

通过两式做差可得：

N2-N0=-1即N0=N2+1

2.

现有一个包含m个节点的三叉树，即每个节点都有三个指向孩子结点的指针，请问:在这3m个指针中有(   )个空指针。
A.    2m
B.    2m-1
C.    2m+1
D.    3m
m个节点有m-1个非空指针,其余皆为空指针,故3m-(m-1)=2m+1