若一棵二叉树的前序遍历序列是{ 4, 2, 1, 3, 6, 5, 7 },中序遍历序列是{ 1, 2, 3, 4, 5, 6, 7 },则下列哪句是错的? A. 这是一棵完全二叉树 B. 所有的奇数都在叶子结点上 C. 6是3的父结点 D. 这是一棵二叉搜索树
时间: 2023-10-11 19:13:24 浏览: 29
根据前序遍历和中序遍历建立二叉树的过程如下:
1. 前序遍历的第一个元素 4 是整棵树的根节点。
2. 在中序遍历中找到根节点 4,根据根节点将中序遍历分成左右两部分,左边部分 {1, 2, 3} 是根节点的左子树的中序遍历,右边部分 {5, 6, 7} 是根节点的右子树的中序遍历。
3. 根据左子树的中序遍历 {1, 2, 3} 和左子树的前序遍历 {2, 1, 3} 递归构建左子树,左子树的根节点是 2。
4. 根据右子树的中序遍历 {5, 6, 7} 和右子树的前序遍历 {6, 5, 7} 递归构建右子树,右子树的根节点是 6。
根据前序遍历和中序遍历建立出的二叉树如下图所示:
```
4
/ \
2 6
/ \ / \
1 3 5 7
```
根据上述二叉树,可以得出以下结论:
A. 这不是一棵完全二叉树,因为右子树不满足完全二叉树的定义。
B. 不是所有的奇数都在叶子结点上,2 是奇数且不是叶子结点。
C. 6 不是 3 的父节点,6 是 3 的兄弟节点。
D. 这不是一棵二叉搜索树,因为在二叉搜索树中,左子树的所有节点都比根节点小,右子树的所有节点都比根节点大,而这棵二叉树中,节点 2 比节点 4 小,节点 6 比节点 4 大,不符合二叉搜索树的定义。
因此,选项 A、B、D 都是错的,选项 C 才是正确的。
相关问题
已知二叉树的前序遍历序列是AEFBGCDHIKJ,中序遍历序列是EFAGBCHKIJD,画出此 二叉树
我们可以根据前序遍历和中序遍历的规律来构造这棵二叉树:
1. 前序遍历的第一个元素是根节点,即A。
2. 在中序遍历中,根节点A左侧的所有元素都属于左子树,右侧的所有元素都属于右子树。
3. 由于前序遍历的第二个元素是左子树的根节点,所以我们可以得到左子树的前序遍历序列为EFBG,中序遍历序列为EFGABC.
4. 由于前序遍历的第六个元素是右子树的根节点,所以我们可以得到右子树的前序遍历序列为CDHIKJ,中序遍历序列为CHKIGDJB。
根据上述规律,我们可以递归构造出这棵二叉树,如下图所示:
```
A
/ \
/ \
E C
/ \ / \
F B H K
/ \
G J
\
D
```
其中,蓝色节点表示前序遍历序列中的节点,红色节点表示中序遍历序列中的节点。
若一颗二叉树的前序遍历序列和后序遍历序列分别为1,2,4,5,6,3,7和4,6,5,2.7,3.1,则该二叉树的中序遍历序列不会是() A 1,2,3,4.5,6.7 B 1,2,4.5,6,3,7 C1.2.4,6,5,3,7 D 1.2.4,5.6.7,3
根据提供的引用内容,我们可以使用前序遍历序列和后序遍历序列来确定二叉树的中序遍历序列。根据引用中的逻辑,我们可以按照以下步骤来解决这个问题:
1. 前序遍历序列的第一个节点是根节点,后序遍历序列的最后一个节点也是根节点。所以,根据提供的前序遍历序列和后序遍历序列,我们可以确定根节点为1。
2. 根据前序遍历序列,我们可以确定根节点1的左子树的前序遍历序列为2,4,5,6,右子树的前序遍历序列为3,7。
3. 根据后序遍历序列,我们可以确定根节点1的左子树的后序遍历序列为4,6,5,2,右子树的后序遍历序列为7,3。
4. 根据前序遍历序列和后序遍历序列的左子树和右子树的长度,我们可以确定左子树的后序遍历序列为4,6,5,右子树的后序遍历序列为7。
5. 重复步骤1-4,我们可以递归地确定整个二叉树的中序遍历序列为2,4,5,6,1,7,3。
所以,该二叉树的中序遍历序列不会是A. 1,2,3,4,5,6,7。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)