关于二叉树，下面说法正确的是()_

Circle&Z

基本概念

二叉树是递归定义的，其结点有左右子树之分，逻辑上二叉树有五种基本形态：

(1)空二叉树——如图(a)；

(2)只有一个根结点的二叉树——如图(b)；

(3)只有左子树——如图(c)；

(4)只有右子树——如图(d)；

(5)完全二叉树——如图(e)。

注意：尽管二叉树与树有许多相似之处，但二叉树不是树的特殊情形

二叉树性质

(1) 在非空二叉树中，第i层的结点总数不超过

, i>=1；

(2) 深度为h的二叉树最多有

个结点(h>=1)，最少有h个结点；

(3) 对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1；

(4) 具有n个结点的完全二叉树的深度为

(5)有N个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系：

若I为结点编号则如果I>1，则其父结点的编号为I/2；

如果2*I<=N，则其左儿子（即左子树的根结点）的编号为2*I；若2*I>N，则无左儿子；

如果2*I+1<=N，则其右儿子的结点编号为2*I+1；若2*I+1>N，则无右儿子。

(6)给定N个节点，能构成h(N)种不同的二叉树。

h(N)为卡特兰数的第N项。h(n)=C(2*n，n)/(n+1)。

(7)设有i个枝点，I为所有枝点的道路长度总和，J为叶的道路长度总和J=I+2i

题目分析

对于A选项，由二叉树的基本概念可知，二叉树中节点的最大度数不超过2，而并一定非要有度为2的节点，如上述（a）（b）（c）（d）所示

对于B选项，数的高度最大为1025，即每一层都只有一个节点，最小是当每一层的节点数最大时，

=1025，h=10,又显然2的10次方减一等于1023，所以最小层数为11，正确

对于C选项， 具有n个结点的 完全二叉树 的深度为

，而选项未标明二叉树种类，显然不对；

对于D选项，由先序遍历可知，根节点是E,所以由中序遍历可知JKG是E的右子树，再观察先序遍历顺序，为GJK，所以显然G是右子树的根节点，再观察中序遍历，可以知JK是G的左子树，正确

综上所述，答案选BD

我的Github ^_^ (欢迎follow): https://github.com/CircleZ3791117

编辑于 2018-02-09 15:46:09 回复(1)

推荐

SunburstRun

答案是BD

B： 10层最多节点为：2^10-1=1023，所以1025个节点最小为11层，最大是单只树1025层

D：只有一种结构：

E

/ \

F G

/

/ \ J

H I \

k

编辑于 2015-09-10 22:46:08 回复(7)

刘-琛

二叉树的先序遍历是EFHIGJK,中序遍历为HFIEJKG,该二叉树的右子树的根为G

D选项可以这样看：

先看先序的第一个确定根为E,再拿E去看中序，确定E的右子树节点有JKG,在拿着JKG在先序中比较顺序，第一个就是该二叉树的右子树的根（G）。

发表于 2022-05-04 21:01:24 回复(1)

nnnn

二叉树的先序遍历是EFHIGJK，说明二叉树的根是E；中序遍历为HFIEJKG，E之前的应该为左子树，HFI为左子树，再看先序遍历，EFHI后应该是右子树的根了，所以G是右子树的根。

发表于 2016-03-09 20:25:46 回复(2)

allensimon

二叉树可以是空树，所以可以没有节点的度为2

发表于 2017-05-07 19:18:36 回复(0)

智者不惑

二叉树的高度不是应该从0开始算吗？

发表于 2018-04-27 16:58:40 回复(0)

顛~⑤瘋——断念

D是的错的吧，既然中序遍历为HFIEJKG，那么G怎么可能为右子树节点？求解答

发表于 2015-09-15 16:05:53 回复(3)

duanhua

二叉树高度最高的情况是每一个层只有一个结点，此时高度为N；最小的情况是完全二叉树，高度是[log2N]+1，以2为底的对数取整后+1。所以高度是[log2N]+1 到 N

发表于 2015-09-12 14:33:11 回复(0)

aaronyoung

二叉树高度范围：ceil(log(N+1))~N

发表于 2015-09-11 10:29:02 回复(0)

lanker

d项提一下我的看法，preorder推根节点是e，inorder推hfi这3个节点是左子树的直接不看，那么右子树只有GJK3个，前序（NLR）是GJK，中序（LNR）是JKG，如果它们三个满足这种字母一一对应，也就是N-G，L-J，R-K，无疑是说右子树他们3个是平衡树（也就是说右子树的深度为2，注意是右子树），直接按前序排序即可，但是题示显然不对应，那么绝对的，右子树的深度大于2，前序去排列，必然出现的是右子树的N节点，也就是右子树的根节点是G，后面JK的顺序在前序和中序没有影响，（但是在中序是在G）直接推出他们是G的左子，J的右子为K。所以d选正确，如图

个人感觉左子树是很容易的，一个是FHI，一个是HFI，这不很明显和（NLR）（LNR）一一对应吗，所以直接F为左子树根N，H为F的L，I为F的R

个人理解，愿听指正