【树】二叉树的构建

一、完全二叉树的构建

　　明白了层次遍历算法后，我们可以利用层次遍历算法来构建一棵完全二叉树。为什么是完全二叉树而不是二叉树呢？因为层次遍历不能确定唯一的一棵二叉树，但是可以确定一棵完全二叉树，这是由完全二叉树的特性所决定的。

　　如果对一颗有n个结点的完全二叉树（其深度为[log₂n]+1）的结点按层序编号（从第1层到第[log₂n]+1，每层从左到右），对任一结点i（1≤i≤n）有：

1.如果i=1，则结点i是二叉树的根，无双亲；如果i>1，则其双亲是节点[i/2]（向下取整）

2.如果2i>n，则结点i无左孩子（结点i为叶子结点）；否则其左孩子是节点2i

3.如果2i+1>n，则结点i无右孩子；否则其右孩子是结点2i+1

　　因此很容易知道第1个结点就是完全二叉树，而左孩子结点序号为2i，否则没有左孩子；右结点序号为2i+1，否则没有右孩子，这样的编号恰好符合层次遍历的访问顺序。因此层次遍历确实可以确定一棵完全二叉树。

/**
 * Created by zejian on 2016/12/17.
 * Blog : http://blog.csdn.net/javazejian [原文地址,请尊重原创]
 * 利用层次遍历原理构造完全二叉树
 */
public class CompleteBinaryTree<T extends Comparable> extends BinarySearchTree <T>  {
	//构建空完全二叉树
    public CompleteBinaryTree(){
        super();
    }
    //以层序遍历构造完全二叉树
    public CompleteBinaryTree(T[] levelOrderArray){
        this.root = create(levelOrderArray, 1);
    }
    //层次遍历构造完全二叉树
    public BinaryNode<T> create(T[] levelOrderArray ,int i){
        if(levelOrderArray ==null){
            throw new RuntimeException("the param 'array' of create method can\'t be null !");
        }
        BinaryNode<T> p = null;

        if (i < levelOrderArray.length){//递归结束条件
            p=new BinaryNode<>(levelOrderArray[i],null,null);
            p.left=create(levelOrderArray,2*i);  //根据完全二叉树的性质 2*i为左孩子结点
            p.right=create(levelOrderArray,2*i+1); //2*i+1为右孩子结点
        }
        return p;
    }
    /**
     * 搜索二叉树的包含操作和移除操作不适合层次遍历构造的完全二叉树
     * 根据层次遍历构建的二叉树必须用层次遍历来判断(仅适用层次遍历构建的完全二叉树)
     */
    @Override
    public boolean contains(T data) {
    	//存放需要遍历的结点,左结点一定优先右节点遍历
        Queue<BinaryNode<T>> queue=new LinkedList<>();
        BinaryNode<T> p=this.root;

        while (p!=null){
            //判断是否存在data
            if(data.compareTo(p.data)==0){
                return true;
            }
            //先按层次遍历结点,左结点一定在右结点之前访问
            if(p.left!=null){
                queue.add(p.left);//孩子结点入队
            }
            if (p.right!=null){
                queue.add(p.right);
            }
            //访问下一个结点
            p=queue.poll();
        }
        return false;
    }
}

二、二叉树的构建

　　了解了完全二叉树的构造，现在我们回过头来看看二叉树又该如何构造呢？显然从完全二叉树的分析中发现，无论是前序遍历或者是中序遍历还是后序遍历，都无法唯一确定一棵树。都将面临之前的问题，遍历顺序为AB的树都可能有两种情况。因此已知二叉树的一种遍历顺序，不能唯一确定一棵二叉树。这是因为后序和前序次序反映的都是父母与孩子结点间的关系而没有反映兄弟间的关系，而中序次序反映的则是兄弟结点间的关系。既然这样，我们能不能考虑结合两种遍历顺序来构造一个二叉树呢？答案是肯定的。确实可以通过前序遍历和中序遍历次序或者后序和中序遍历次序唯一确定一棵二叉树，而先序和后序遍历反应的都是父母与孩子结点的关系，自然也就无法确定一棵唯一二叉树了。如给出先序顺序AB和后序顺序BA，可以确定A是根结点，但B呢，是左孩子还是右孩子呢？无法确定。

1.前序与中序构建二叉树及其代码实现

　　已知先根序列preList=ABDGCEFH和中根序列inList=DGBAECHF，确定二叉树的过程如下：

从图中我们可以发现整个构建过程都是在不断递归，即将复杂树简化为子树进行求解。上述过程我们可以这样描述，设数组preList和inList分别表示一个二叉树的先根和中根遍历次序，两个序列的长度都为n，则二叉树构建过程分如下步骤：

①由先根遍历次序可知，二叉树的根结点为preList[0],该根结点也肯定在中根序列中，设中根序列inList中根结点的位置为root(0≤root≤n-1),则有preList[0]=inList[root]

②根据中根遍历次序可知，inList[root]之前的结点都为根结点的左子树，inList[root]之后的结点都为根结点的右子树，因此根结点的左子树由root个结点组成，子序列如下：

左子树的先根序列：preList[1] , … , preList[root]
左子树的中根序列：inList[0] , … , inList[root-1]

根结点的右子树有n-root-1个结点组成，子序列如下：

右子树的先根序列：preList[root+1] , … , preList[n-1]
右子树的中根序列：inList[root+1] , … , inList[n-1]

③ 循环递归步骤①②，即可确定二叉树

以上3个步骤便是通过先根次序和中根次序确定一棵二叉树的过程，大家可结合图理解这过程，这里顺带给出实现代码如下：

/**
  * 根据先根和中根遍历算法构造二叉树
  * @param preList 	先根遍历次序数组
  * @param inList 	中根遍历次序数组
  * @param preStart 	先根数组中，左/右子树开始下标
  * @param preEnd	先根数组中，左/右子树结束下标
  * @param inStart	中根数组中，左/右子树开始下标
  * @param inEnd		中根数组中，左/右子树结束下标
  * return root 最终返回的根结点
  */
public  BinaryNode<T>  buildBSTreeByPreIn(T[] preList,T[] inList,int preStart,int preEnd,int inStart,int inEnd){
    //preList[preStart]必须根结点数据,创建根结点root
    BinaryNode<T> p=new BinaryNode<>(preList[preStart]);
    //如果没有其他元素,就说明结点已构建完成
    if (preStart == preEnd && inStart == inEnd) {
        return p;
    }
    int root=0;//找出中根次序中，根结点的下标
    for (root = inStart; root < inEnd; root++) {
        //如果中根次序中的元素值与先根次序中根结点的值相等,则该下标index即为inList中的根结点下标
        if (preList[preStart].compareTo(inList[root])==0)
            break;
    }

    //获取左子树的长度
    int leftLength=root-inStart;
    //获取右子树的长度
    int rightLength=inEnd-root;

    //递归构建左子树
    if(leftLength>0){
        //左子树的先根序列：preList[1] , ... , preList[i]
        //左子树的中根序列：inList[0] , ... , inList[i-1]
        //A:root=3	preStart=0	leftLength=3
        //B:root=2	preStart=1	leftLength=2
        //所以preStart+leftLength不能换成root
        p.left=buildBSTreeByPreIn(preList,inList,preStart+1,preStart+leftLength,inStart,root-1);
    }
    //递归构建右子树
    if (rightLength>0){
        //右子树的先根序列：preList[i+1] , ... , preList[n-1]
        //右子树的中根序列：inList[i+1] , ... , inList[n-1]
        p.right=buildBSTreeByPreIn(preList,inList,preStart+leftLength+1,preEnd,root+1,inEnd);
    }
    return p;
}

2.后根与中根次序构建二叉树及其代码实现

　　同样的情况，根据中根次序和后根次序，我们也可以确定唯一一棵二叉树，后根次序为GDBEHFCA，中根次序为DGBAECHF，其确定二叉树执行过程如下：

　　上述过程我们也可以这样描述，设数组postList和inList分别表示一个二叉树的后根和中根遍历次序，两个序列的长度都为n，则二叉树构建过程分如下步骤：

①由后根遍历次序可知，二叉树的根结点为postList[n-1]，该根结点也肯定在中根序列中，设中根序列inList中根结点的位置为root(0≤root≤n-1),则有postList[n-1]=inList[root]

②根据中根遍历次序可知，inList[root]之前的结点都为根结点的左子树，inList[root]之后的结点都为根结点的右子树，因此根结点的左子树由i个结点组成，子序列如下：

左子树的后根序列：postList[0] , … , preList[root-1]
左子树的中根序列：inList[0] , … , inList[root-1]

根结点的右子树有n-root-1个结点组成，子序列如下：

右子树的后根序列：postList[root] , … , postList[n-2]
右子树的中根序列：inList[root+1] , … , inList[n-1]

③ 循环递归步骤①②，即可确定二叉树

到此利用后根、中根遍历算法构建二叉树的过程就已全部描述完成了，实现代码如下：

/**
  * 后根/中根遍历构建二叉树
  * @param postList 	后根遍历数组
  * @param inList 	中根遍历数组
  * @param postStart	后根数组中，左/右子树开始下标
  * @param postEnd	后根数组中，左/右子树结束下标
  * @param inStart	中根数组中，左/右子树开始下标
  * @param inEnd		中根数组中，左/右子树结束下标
  * @return 根结点
  */
public BinaryNode<T> buildBSTreeByPostIn(T[] postList,T[] inList,int postStart,int postEnd,int inStart,int inEnd){
    //构建根结点
    BinaryNode<T> p=new BinaryNode<>(postList[postEnd]);

    if(postStart==postEnd && inStart==inEnd){
        return p;
    }

    //查找中根序列的根结点下标root
    int root=0;
    for (root=inStart;root<inEnd;root++){
        if (postList[postEnd].compareTo(inList[root])==0)
            break;
    }

    //左子树的长度
    int leftLenght=root-inStart;
    //右子树的长度
    int rightLenght=inEnd-root;

    //递归构建左子树
    if(leftLenght>0){
        //左子树的后根序列：postList[0] , … , preList[root-1] 
        //左子树的中根序列：inList[0] , … , inList[root-1]
        //postStart+leftLenght-1:后根左子树的结束下标
        p.left=buildBSTreeByPostIn(postList,inList,postStart,postStart+leftLenght-1,inStart,root-1);
    }
    //递归构建右子树
    if(rightLenght>0){
        //右子树的后根序列：postList[root] , … , postList[n-2] 
        //右子树的中根序列：inList[root+1] , … , inList[n-1]
        p.right=buildBSTreeByPostIn(postList,inList,postStart+leftLenght,postEnd-1,root+1,inEnd);
    }
    return p;
}

测试代码

public static void main(String args[]){
    String[] preList={"A","B","D","G","C","E","F","H"};
    String[] inList={"D","G","B","A","E","C","H","F"};
    String[] postList={"G","D","B","E","H","F","C","A"};

    //先根/中根
    BinarySearchTree<String> cbtree = new BinarySearchTree<>(preList,inList,true);
    //后根/中根
	BinarySearchTree<String> cbtree = new BinarySearchTree<>(postList,inList,false);
   
    System.out.println("先根遍历:"+cbtree.preOrder());
    //System.out.println("非递归先根遍历:"+cbtree.preOrderTraverse());
    System.out.println("中根遍历:"+cbtree.inOrder());
    //System.out.println("非递归中根遍历:"+cbtree.inOrderTraverse());
    System.out.println("后根遍历:"+cbtree.postOrder());
    //System.out.println("非递归后根遍历:"+cbtree.postOrderTraverse());

    System.out.println("树的结构如下:");
    cbtree.print();
}
/**
  * 根据先根和中根遍历算法构造二叉树
  * @param pList 先根/后根遍历次序数组
  * @param inList 中根遍历次序数组
  * @param isPreOrder 是否为先根遍历次序数组,true:先根,false:后根
  * Blog : http://blog.csdn.net/javazejian [原文地址,请尊重原创]
  */
public BinarySearchTree(T[] pList,T[] inList,boolean isPreOrder ){
    if(pList==null||inList==null){
        throw new RuntimeException("preList or inList can not be null");
    }
    if(isPreOrder) {
        //先根/中根次序构建二叉树
        this.root = buildBSTreeByPreIn(pList,inList,0,pList.length-1,0,inList.length-1);
    }else {
        //后根/中根次序构建二叉树
        this.root = buildBSTreeByPostIn(pList,inList,0,pList.length-1,0,inList.length-1);
    }
}

来源：java数据结构与算法之树基本概念及二叉树（BinaryTree）的设计与实现

（完）