（递归方法）不建立二叉树模型求解“根据前序序列、中序序列写出后序序列”的问题

思路算法实现本博客其他文章推荐

思路

通过前序序列顺序次序在中序序列中查找，利用中序序列的特性，向两边分治，先向左分治再向右分治，最后输出根节点； 这种思路会有很多重复解，所以我们还需借用visited数组去除不必要的重复解，即可得到后序序列输出而不建立二叉树。

算法实现

#include<iostream> using namespace std; #define N 100 // 1 // 2 3 //# 4 5 6 // 前序 1 2 4 3 5 6 // 中序 2 4 1 5 3 6 // 后序 4 2 5 6 3 1 /** 辅助方法 在序列中查找 @param int[] 序列 @param int 查询开始位置 @param int 查询结束位置 @param int 待查询元素 @return int 查找到的元素的下标 */ int search(int[],int,int,int); /** 根据前序和中序序列输出后序序列的递归方法 @param int 前序序列的长度 @param int[] 前序序列 @param int 遍历前序序列的开始位置 @param int[] 中序序列 @param int 中序序列递归开始位置 @param int 中序序列递归结束位置 */ void postOrderSeq(int,int[],int,int[],int,int); int visited[N]={0}; //防止重复访问 int main(){ int preOrderSeq[N] = {1,2,4,3,5,6},inOrderSeq[N] = {2,4,1,5,3,6}; int len = 6; postOrderSeq(len,preOrderSeq,0,inOrderSeq,0,len); } int search(int inOrderSeq[],int inStart,int inEnd,int x){ for(int i = inStart;i < inEnd;i++) if(inOrderSeq[i] == x)return i; return -1; } void postOrderSeq(int len,int preOrderSeq[],int preStart,int inOrderSeq[],int inStart,int inEnd){ for(int i = preStart;i < len;i++){ int index = search(inOrderSeq,inStart,inEnd,preOrderSeq[i]); if(index != -1&&visited[index]!=1) { visited[index] = 1; postOrderSeq(len,preOrderSeq,i,inOrderSeq,0,index); postOrderSeq(len,preOrderSeq,i,inOrderSeq,index+1,inEnd); cout<<preOrderSeq[i]<<" "; } } }

本博客其他文章推荐

算法设计与分析之半数集问题

关于C++整型数组自动初始化为零的情况记录

算法设计与分析之线性时间选择

算法设计与分析之分治策略练习（下）

算法设计与分析之分治策略练习（上）

算法设计与分析之分治策略