一棵非空二叉树,若后序遍历与中序遍历的序列相同,则该二叉树所有结点均无左孩子。
时间: 2023-07-24 17:33:50 浏览: 450
这个说法是错误的。后序遍历与中序遍历序列相同并不意味着二叉树所有结点均无左孩子。举个例子,考虑以下二叉树:
```
A
/ \
B C
/ \
D E
```
它的中序遍历为 `B A D C E`,后序遍历也为 `B D E C A`。可以发现,节点 C 就有左孩子 D。因此,原命题不成立。
相关问题
一棵非空二叉树,若先序遍历与后序遍历的序列相反,则该二叉树所有结点均无左孩子。
这个说法是正确的。如果一棵二叉树的先序遍历和后序遍历序列恰好相反,那么可以推断出该二叉树所有结点均无左孩子。因为先序遍历是先遍历根结点,再遍历左子树和右子树,而后序遍历是先遍历左子树和右子树,再遍历根结点。如果一个结点有左孩子,那么在先序遍历序列中,它的左孩子会被先遍历,而在后序遍历序列中,它的左孩子会被后遍历,这两个序列不可能相反。因此,如果先序遍历和后序遍历序列相反,那么所有结点都没有左孩子。
一棵非空二叉树,若先序遍历与后序遍历的序列相反,则该二叉树所有结点均无右孩子。
这个说法是错误的。如果一棵二叉树的先序遍历和后序遍历序列恰好相反,不能推断出该二叉树所有结点均无右孩子。举个例子,下面这棵二叉树的先序遍历和后序遍历序列都是{1, 3, 2}和{3, 1, 2},但是它的根结点2有右孩子3。
```
2
\
3
/
1
```
因此,先序遍历和后序遍历序列相反并不能说明所有结点均无右孩子。
阅读全文