由于先序、中序和后序序列中的任一个都不能唯一确定一棵二叉树,所以对二叉树做如下处理,将二叉树的空结点用·补齐,如图所示。我们把这样处理后的二叉树称为原二叉树的扩展二叉树,扩展二叉树的先序和后序序列能唯一确定其二叉树。 现给出扩展二叉树的先序序列,要求输出其中序和后序序列。
时间: 2023-11-14 19:54:42 浏览: 71
由前序(后序)和中序确定一棵二叉树
我们可以根据扩展二叉树的先序序列来还原二叉树,并且在还原的过程中得到其中序和后序序列。具体步骤如下:
1. 将扩展二叉树的先序序列存储为一个字符数组pre,其中pre[i]表示第i个结点的值(如果是空结点则为'·')。
2. 定义一个指针idx,初始值为0,表示当前要还原的结点在pre中的下标。
3. 定义一个递归函数buildTree,该函数的参数为当前要还原的子树的根结点在pre中的下标范围[low, high],返回值为还原出来的子树的根结点。
4. 在buildTree函数中,如果low > high,则返回空指针,表示当前子树为空。
5. 否则,取出pre[idx]的值,创建一个新的结点,并将idx加1。
6. 如果pre[idx]的值为'·',则表示当前结点的左子树为空,否则递归调用buildTree函数构建左子树,其范围为[low+1, mid],其中mid为当前结点的下标。
7. 同理,如果pre[idx]的值为'·',则表示当前结点的右子树为空,否则递归调用buildTree函数构建右子树,其范围为[mid+1, high]。
8. 在buildTree函数的末尾,返回当前创建的结点,表示已经还原出了这个子树的根结点。
9. 最终,调用buildTree(0, n-1)来还原整棵二叉树,并得到其中序和后序序列。
下面是实现该算法的Python代码:
阅读全文