二叉树专题[校招]

作者: 大海 分类: 校招 发布时间: 2016-03-05 20:59 ė1411 views 6二叉树专题[校招]已关闭评论

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

本文出自 纳百川,转载时请注明出处及相应链接。

本文永久链接: http://www.bicner.com/881.html

Ɣ回顶部