前序中序求后序的java算法是怎样的

共计 1913 个字符，预计需要花费 5 分钟才能阅读完成。

前序中序求后序的 java 算法是怎样的，相信很多没有经验的人对此束手无策，为此本文总结了问题出现的原因和解决方法，通过这篇文章希望你能解决这个问题。

 二叉树的前序、中序、后序遍历的定义：前序遍历：对任一子树，先访问跟，然后遍历其左子树，最后遍历其右子树；中序遍历：对任一子树，先遍历其左子树，然后访问根，最后遍历其右子树；后序遍历：对任一子树，先遍历其左子树，然后遍历其右子树，最后访问根。给定一棵二叉树的前序遍历和中序遍历，求其后序遍历（提示：给定前序遍历与中序遍历能够唯一确定后序遍历）。变量条件：二叉树中的结点名称以大写字母表示：A，B，C.... 最多 26 个结点。运行时限：1 秒 / 测试数据。输入格式：两行，第一行为前序遍历，第二行为中序遍历。输出格式：若不能根据前序和中序遍历求出后序遍历，输出 NO ANSWER；否则输出一行，为后序遍历。

/**
 *  前序遍历:GDAFEMHZ
 *  中序遍历:ADEFGHMZ
 *
 *
 *  两个步骤:
   根据前序中序, 构造二叉树
   后序遍历二叉树
 *  根据前序遍历的特点得知, 根结点为 G
 *  根结点将中序遍历结果 ADEFGHMZ 分成 ADEF 和 HMZ 两个左子树、右子树。 *  递归确定中序遍历序列 ADEF 和前序遍历序列 DAFE 的子树结构;
 *  递归确定中序遍历序列 HMZ 和前序遍历序列 MHZ 的子树结构;
 */
public class PostOrder{ public static void main(String[] args) throws Exception{// Scanner in = new Scanner(System.in);
// String pre,mid;
// while(in.hasNext()){// pre = in.next();
// mid = in.next();
// System.out.println(postOrder(pre,mid));
// }
 String pre =  ABDGCEFH 
 String mid =  DGBAECHF 
 System.out.println(postOrder(pre,mid));
 }
 private static String postOrder(String pre, String mid) throws Exception{ if(pre.length() == 1)
 return pre;
 else if(pre.length() == 0)
 return  
 int m = mid.indexOf(pre.charAt(0));
 return postOrder(pre.substring(1,m+1 ),mid.substring(0, m)) 
+ postOrder(pre.substring(m+1),mid.substring(m+1)) 
+ pre.charAt(0);
 }
}

/**
 *  中序遍历:ADEFGHMZ
 *  后序遍历:AEFDHZMG
 *
 *
 *  后序遍历最后一个结点即为根结点, 即   根结点为 G
 */
public class PreOrder { public static void main(String[] args) throws Exception{
 String post =  AEFDHZMG 
 String mid =  ADEFGHMZ 
 System.out.println(preOrder(post,mid));
 }
 private static String preOrder(String post, String mid) throws Exception{ if(post.length() == 1)
 return post;
 else if(post.length() == 0)
 return  
 int m = mid.indexOf(post.charAt(post.length() - 1));
 return post.charAt(post.length() - 1) 
+ preOrder(post.substring(post.length() - mid.length(),m),mid.substring(0,m)) 
+ preOrder(post.substring(m,post.length() - 1),mid.substring(m+1));
 }
}

看完上述内容，你们掌握前序中序求后序的 java 算法是怎样的的方法了吗？如果还想学到更多技能或想了解更多相关内容，欢迎关注丸趣 TV 行业资讯频道，感谢各位的阅读！