根据中序和先序(后序)构建二叉树_数据结构,给前序和中序 画二叉树

1、根据先序和中序构建二叉树

例：

前序遍历: GDAFEMHZ

中序遍历: ADEFGHMZ

画树求法：
第一步，根据前序遍历的特点，我们知道根结点为G

第二步，观察中序遍历ADEFGHMZ。其中root节点G左侧的ADEF必然是root的左子树，G右侧的HMZ必然是root的右子树。

第三步，观察左子树ADEF，左子树的中的根节点必然是大树的root的leftchild。在前序遍历中，大树的root的leftchild位于root之后，所以左子树的根节点为D。

第四步，同样的道理，root的右子树节点HMZ中的根节点也可以通过前序遍历求得。在前序遍历中，一定是先把root和root的所有左子树节点遍历完之后才会遍历右子树，并且遍历的左子树的第一个节点就是左子树的根节点。同理，遍历的右子树的第一个节点就是右子树的根节点。

第五步，观察发现，上面的过程是递归的。先找到当前树的根节点，然后划分为左子树，右子树，然后进入左子树重复上面的过程，然后进入右子树重复上面的过程。最后就可以还原一棵树了。该步递归的过程可以简洁表达如下：

1 确定根,确定左子树，确定右子树。

2 在左子树中递归。

3 在右子树中递归。

4 打印当前根。

代码如下：

/**
      * 根据先序和中序 构建二叉树
      * @param pre
      * @param in
      * @return
      */
     public TreeNode reConstructBinaryTree(int[] pre ,int[] in){
         TreeNode root = reConstructBinaryTree(pre,0,pre.length-1,in,0,in.length-1);
         return root;
     }
     public TreeNode reConstructBinaryTree(int[] pre,int preStart,int preEnd,int[] in,int inStart,int inEnd){
         if(preStart>preEnd || inStart > inEnd){ //到达边界条件时返回null
             return null;
         }
         TreeNode  treeNode =new TreeNode(pre[preStart]);   //新建一个TreeNode

         for(int i=inStart;i<=inEnd;i++){   
             if(in[i] == pre[preStart]){    //在中序中找到根节点的位置，【依次】将先序序列和中序序列分成左右字树，分别构建左右子树。
                 // 重构左子树，注意边界条件
                 treeNode.left = reConstructBinaryTree( pre, preStart+1,           preStart+i-inStart, in, inStart, i-1);
                 // 重构右子树，注意边界条件
                 treeNode.right = reConstructBinaryTree(pre, preStart+i-inStart+1, preEnd,             in, i+1,     inEnd);
             }
         }
         return treeNode;
     }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

2、根据中序和后序构建二叉树

依然是上面的题，这次我们只给出中序和后序遍历：

中序遍历: ADEFGHMZ

后序遍历: AEFDHZMG

画树求法：
第一步，根据后序遍历的特点，我们知道后序遍历最后一个结点即为根结点，即根结点为G。

第二步，观察中序遍历ADEFGHMZ。其中root节点G左侧的ADEF必然是root的左子树，G右侧的HMZ必然是root的右子树。

第三步，观察左子树ADEF，左子树的中的根节点必然是大树的root的leftchild。在前序遍历中，大树的root的leftchild位于root之后，所以左子树的根节点为D。

第四步，同样的道理，root的右子树节点HMZ中的根节点也可以通过前序遍历求得。在前后序遍历中，一定是先把root和root的所有左子树节点遍历完之后才会遍历右子树，并且遍历的左子树的第一个节点就是左子树的根节点。同理，遍历的右子树的第一个节点就是右子树的根节点。

第五步，观察发现，上面的过程是递归的。先找到当前树的根节点，然后划分为左子树，右子树，然后进入左子树重复上面的过程，然后进入右子树重复上面的过程。最后就可以还原一棵树了。该步递归的过程可以简洁表达如下：

1 确定根,确定左子树，确定右子树。

2 在左子树中递归。

3 在右子树中递归。

4 打印当前根。

这样，我们就可以画出二叉树的形状，如上图所示，这里就不再赘述。

那么，前序遍历: GDAFEMHZ

/**
      * 根据中序和后序 构建二叉树
      * @param in
      * @param last
      * @return
      */
     public TreeNode reConstructBinaryTree2(int[] in,int[] last){
         TreeNode root = reConstructBinaryTree2(in,0,in.length-1,last,0,last.length-1);
         return root;
     }

     public TreeNode reConstructBinaryTree2(int[] in,int inStart,int inEnd,int[] last,int lastStart,int lastEnd){
         if(inStart > inEnd || lastStart > lastEnd)
             return null;
         TreeNode treeNode = new TreeNode(last[lastEnd]);
         for(int i=inStart;i<=inEnd;i++){
             if(in[i] == last[lastEnd]){
                 treeNode.left = reConstructBinaryTree2(in, inStart,    i-1,    last,   lastStart,              lastStart+i-inStart-1);
                 treeNode.right = reConstructBinaryTree2(in,    i+1,    inEnd,  last,   lastStart+i-inStart,    lastEnd-1);
             }
         }
         return treeNode;
     }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23