本文共 2801 字，大约阅读时间需要 9 分钟。

根据二叉树的中序遍历和后序遍历构造出二叉树

给出二叉树的中序遍历数组和后序遍历数组构造出该二叉树

二叉树的中序遍历和后序遍历分别为下面的数组：

int[] inorder = {12,15,35,46,57,62,65,68,79};

算法设计如下：

package com.bean.constructbinarytreedemo;import java.util.ArrayList;import java.util.Stack;public class BuildBinaryTreeDemo2 {    /*     * 二叉树的前序遍历     * */    public static ArrayList
   
     preOrder(TreeNode root){        Stack
    
      stack = new Stack
     
      ();        ArrayList
      
        list = new ArrayList
       
        ();        if(root == null){            return list;        }        stack.push(root);        while(!stack.empty()){            TreeNode node = stack.pop();            list.add(node.data);            if(node.rightChild!=null){                stack.push(node.rightChild);            }            if(node.leftChild != null){                stack.push(node.leftChild);            }        }        System.out.println(list);        return list;    }    /*     * 二叉树的中序遍历     * */    public static ArrayList
        
          inOrder(TreeNode root){ ArrayList
         
           list = new ArrayList
          
           (); Stack
           
             stack = new Stack
            
             (); TreeNode current = root; while(current != null|| !stack.empty()){ while(current != null){ stack.add(current); current = current.leftChild; } current = stack.peek(); stack.pop(); list.add(current.data); current = current.rightChild; } System.out.println(list); return list; } /* * 二叉树的后续遍历 * */ public static ArrayList
             
               postOrder(TreeNode root){ ArrayList
              
                list = new ArrayList
               
                (); if(root == null){ return list; } list.addAll(postOrder(root.leftChild)); list.addAll(postOrder(root.rightChild)); list.add(root.data); System.out.println(list); return list; } /* * 构造二叉树 * */ public TreeNode buildTree(int[] inorder, int[] postorder) { return buildBinaryTreeProcess(inorder, postorder, postorder.length - 1, 0, inorder.length - 1); } /* * 根据二叉树中序遍历和后序遍历的结果构造二叉树 * */ public TreeNode buildBinaryTreeProcess(int[] inorder, int[] postorder, int ppos, int is, int ie){ if(ppos >= postorder.length || is > ie) return null; TreeNode node = new TreeNode(postorder[ppos]); int pii = 0; for(int i = 0; i < inorder.length; i++){ if(inorder[i] == postorder[ppos]) pii = i; } node.leftChild = buildBinaryTreeProcess(inorder, postorder, ppos - 1 - ie + pii, is, pii - 1); node.rightChild = buildBinaryTreeProcess(inorder, postorder, ppos - 1 , pii + 1, ie); return node; } public static void main(String[] args) { // TODO Auto-generated method stub //int[] preorder = {62,15,12,46,35,57,68,65,79}; int[] inorder = { 12,15,35,46,57,62,65,68,79}; int[] postorder= { 12,35,57,46,15,65,79,68,62}; BuildBinaryTreeDemo2 buildBT=new BuildBinaryTreeDemo2(); TreeNode tree = buildBT.buildTree(inorder, postorder); buildBT.preOrder(tree); buildBT.inOrder(tree); buildBT.postOrder(tree); }}
               
              
             
            
           
          
         
        
       
      
     
    
   

（完）