前、中、后序遍历随意两种是否能确定一个二叉树?理由? && 栈和队列的特点和区别

前序和后序不能确定二叉树
理由:
前序和后序在本质上都是将父节点与子结点进行分离,但并没有指明左子树和右子树的能力,因此得到这两个序列只能明确父子关系,
而不能确定一个二叉树。

由二叉树的中序和前序遍历序列可以唯一确定一棵二叉树
理由:
1.前序遍历数组中的第一个元素就是二叉树的根节点。

2.根节点将中序遍历数组从中间划分为左子树部分和右子树部分。

3.前序遍历数组中的左子树与右子树的长度与中序遍历相同,于是也一分为二。

4.递归。

由二叉树的中序和后序遍历序列可以唯一确定一棵二叉树
理由:
中序是 访问顺序是
左子树 根 右子树

后序是

左子树 右子树 根

所以一棵二叉树如果给了后序的信息 可以把树根确定下来

带入中序的信息中 找出左右子树 再带回后续的信息找这样反复,也就是递归下去,可以把树给确定下来。

栈和队列数据结构的特点是:

栈特点就是一个先进后出的结构。

队列特点就是一个先进先出的结构。

栈和队列的区别是:

数据结构不同队列先进先出,栈先进后出。

对插入和删除操作的"限定"。 栈是限定只能在表的一端进行插入和删除操作的线性表。
队列是限定只能在表的一端进行插入和在另一端进行删除操作的线性表。

遍历数据速度不同。栈只能从头部取数据 也就最先放入的需要遍历整个栈最后才能取出来内,
而且在遍历数据的时候还得为数据开辟临时空间,保持数据在遍历前的一致性队列怎不同,
他基于地址指针进行遍历,而且可以从头或尾部开始遍历,但不能同时遍历,无容需开辟临时空间。

举例说明如何用两个栈实现队列的入队列操作和出队列 操作:
入队:将元素进栈A

出队:判断栈B是否为空,如果为空,则将栈A中所有元素pop,并push进栈B,栈B出栈;

如果不为空,栈B直接出栈。

原文地址:https://www.cnblogs.com/kongbursi-2292702937/p/13029546.html