某二叉树的前序序列为 ABCDEFG ，中序序列为 DCBA

[单选题]

某二叉树的前序序列为 ABCDEFG ，中序序列为 DCBAEFG ，则该二叉树的深度（根结点在第 1 层）为（）。

```
2
```
```
3
```
```
4
```
```
5
```

查看正确选项

赞花婆

【解析】深度，定义一棵树的根节点所在的层次为 1 ，其他节点所在的层次等于它的父节点所在的层次加 1 ，树的最大层次称为树的深度。二叉树遍历可以分为 3 种：前序遍历（访问根节点再访问左子树和访问右子树之前）、中序遍历（访问根节点在访问左子树和访问右子树两者之间）、后序遍历（访问根节点在访问左子树和访问右子树之后）。二叉树的前序序列为 ABCDEFG ， A 为根节点。中序序列为 DCBAEFG ，可知 DCB 为左子树节点， EFG 为右子树节点。同理 B 为 C 父节点 ,C 为 D 父节点。同理 E 为 F 根节点， F 为 G 根节点。故二叉树深度为 4 层。 C 选项正确。

发表于 2017-05-01 10:38:49 回复(0)