由于先序、中序和后序序列中的任一个都不能唯一确定一棵二叉树,所以对二叉树做如下处理,将二叉树的空结点用·补齐,如图所示。我们把这样处理后的二叉树称为原二叉树的扩展二叉树,扩展二叉树的先序和后序序列能唯一确定其二叉树。 现给出扩展二叉树的先序序列,要求输出其中序和后序序列。
时间: 2023-11-14 15:43:12 浏览: 62
由前序(后序)和中序确定一棵二叉树
我们可以根据扩展二叉树的先序序列构造出原二叉树,然后再根据原二叉树求出中序和后序序列。
具体构造原二叉树的过程如下:
1. 从扩展二叉树的先序序列中取出第一个元素作为根节点。
2. 如果根节点是空结点(即·),则返回空树。
3. 否则,根据先序序列的顺序,接下来的两个元素分别是左子树的根节点和右子树的根节点。如果左子树的根节点是空结点,则左子树为空树;如果右子树的根节点是空结点,则右子树为空树。
4. 递归构造左子树和右子树。
构造出原二叉树后,我们可以根据其求出中序和后序序列。具体过程如下:
1. 对于一棵二叉树,它的中序序列是将其所有节点按照中序遍历的顺序输出的序列。
2. 对于一棵二叉树,它的后序序列是将其所有节点按照后序遍历的顺序输出的序列。
3. 对于一棵二叉树,它的中序序列和后序序列可以通过递归的方式求得。具体过程是,先递归求出左子树的中序序列和后序序列,再递归求出右子树的中序序列和后序序列,最后将根节点插入到后序序列的最后面,即可得到该二叉树的后序序列。
下面是具体的代码实现:
阅读全文