数据结构的定义:

树的顶节点定义：

public class BinaryTree
     
       extends BinaryTreeNode
      
        {    private int count;    public int getCount() {        return count;    }    public void setCount(int count) {        this.count = count;    }    public BinaryTree(T data) {        super(data);        this.count = 1;    }}
      
     

 节点定义：

package com.itmei.offer;/** * Created by qiaodan on 2017/12/8. */public class BinaryTreeNode
     
       {    private T data;    private BinaryTreeNode
      
        left;    private BinaryTreeNode
       
         right;    public BinaryTreeNode
        
          getLeft() {        return left;    }    public void setLeft(BinaryTreeNode
         
           left) {        this.left = left;    }    public BinaryTreeNode
          
            getRight() { return right; } public void setRight(BinaryTreeNode
           
             right) { this.right = right; } public T getData() { return data; } public void setData(T data) { this.data = data; } public BinaryTreeNode(T data) { this.data = data; }}
           
          
         
        
       
      
     

 

泛型对象：

package com.itmei.offer;/** * Created by qiaodan on 2017/12/8. */public class Person {    private String name;    private int age;    public String getName() {        return name;    }    public void setName(String name) {        this.name = name;    }    public int getAge() {        return age;    }    public void setAge(int age) {        this.age = age;    }    @Override    public String toString() {        return "姓名："+this.getName()+"年龄："+this.getAge();    }}

 二叉树构造主方法：

/**     * 问题8、根据根据前序遍历和中序遍历 确定 构造一个 二叉树     */    @Test    public void contructionBinaryTree(){        int[] pre = {1,2,4,7,3,5,6,8};        int[] middle = {4,7,2,1,5,3,8,6};        int root = 0;        int startL = 0;        int endL = foundNumIndexinMiddle(pre[root],middle)-1;        int startR = foundNumIndexinMiddle(pre[root],middle)+1;        int endR = middle.length-1;        Person rootPerson = new Person();        int val = pre[root];        System.out.println(val);        rootPerson.setName("node"+pre[root]);        rootPerson.setAge(pre[root]);        BinaryTree
     
       tree = new BinaryTree
      
       (rootPerson);        tree.setCount(pre.length);        root++;        tree.setLeft(constructBTCore(root,startL,endL,middle,pre));        root = startR;        if (startR==endR){            root++;        }        tree.setRight(constructBTCore(root,startR,endR,middle,pre));        System.out.println(tree.getLeft().getData().getName());        System.out.println(tree.getRight().getData().getName());    }
      
     

 添加二叉树非根节点的递归方法（核心实现）：

public BinaryTreeNode
     
       constructBTCore(int rootindex,int start,int end,int[] middle,int[] pre){        Person p = new Person();        p.setName("node"+pre[rootindex]);        p.setAge(pre[rootindex]);        BinaryTreeNode
      
        tree = new BinaryTreeNode<>(p);        tree.setLeft(null);        tree.setRight(null);        int startL = start;        int endL = foundNumIndexinMiddle(pre[rootindex],middle)-1;        int startR = foundNumIndexinMiddle(pre[rootindex],middle)+1;        int endR = end;        if (start
       
        =start) {                rootindex++;                tree.setLeft(constructBTCore(rootindex, startL, endL, middle, pre));            }            if (startR < endR && rootindex
        
         <=end) {                rootindex = startR;                tree.setRight(constructBTCore(rootindex, startR, endR, middle, pre));            } else if(startR==endR){                rootindex++;                tree.setRight(constructBTCore(rootindex, startR, endR, middle, pre));            }        }        return tree;    }
        
       
      
     

 

使用到了工具方法：

public int foundNumIndexinMiddle(int num,int[] arr){        for (int i=0;i

 构造结果：