二叉树专题[校招]
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
本文出自 纳百川,转载时请注明出处及相应链接。
本文永久链接: https://www.bicner.com/881.html