一棵非空二叉树,若先序遍历与后序遍历的序列相反,则该二叉树所有结点均无左孩子。
时间: 2024-01-23 19:35:18 浏览: 137
这个说法是正确的。如果一棵二叉树的先序遍历和后序遍历序列恰好相反,那么可以推断出该二叉树所有结点均无左孩子。因为先序遍历是先遍历根结点,再遍历左子树和右子树,而后序遍历是先遍历左子树和右子树,再遍历根结点。如果一个结点有左孩子,那么在先序遍历序列中,它的左孩子会被先遍历,而在后序遍历序列中,它的左孩子会被后遍历,这两个序列不可能相反。因此,如果先序遍历和后序遍历序列相反,那么所有结点都没有左孩子。
相关问题
一棵非空二叉树的先序遍历序列与后序遍历序列正好相反,则该二叉树一定满足()。 A 只有一个叶子结点 B 是一棵满二叉树 C 所有的结点均无右孩子 D 所有的结点均无左孩子
该二叉树一定满足选项 B,是一棵满二叉树。因为满二叉树的性质是每个节点要么有两个子节点,要么没有子节点。假设该二叉树有左子树和右子树,则先序遍历的第一个节点为根节点,后序遍历的最后一个节点也为根节点,因此必须是叶子节点,否则无法满足先序遍历和后序遍历正好相反的条件。若只有一个叶子结点,则不可能得到一棵二叉树。若所有节点均无右孩子,则左子树为空,不符合满二叉树的定义。若所有节点均无左孩子,则右子树为空,同样不符合满二叉树的定义。
一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反,则该二叉树一定满足( )。 A 所有的结点均无左孩子 B 所有的结点均无右孩子 C 只有一个叶子结点 D 是任意一棵二叉树
该二叉树一定满足选项 A 所有的结点均无左孩子。 根据二叉树的遍历方式,先序遍历的顺序为 根-左-右,后序遍历的顺序为 左-右-根。如果一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反,那么根结点在先序遍历中一定是最后一个结点,也就是说在后序遍历中根结点一定是第一个结点。如果根结点有左孩子,那么在后序遍历中左孩子会先被遍历,与根结点不符合;如果根结点有右孩子,那么在先序遍历中右孩子会先被遍历,与根结点也不符合。因此,该二叉树一定满足所有的结点均无左孩子。
阅读全文