前序实现完全二叉树，层序遍历，二叉树,import java.

前序实现完全二叉树，层序遍历，二叉树,import java.

import java.util.*;public class main {    public static void main(String[] args){        //确保输入的是整数        Scanner read=new Scanner(System.in);        int depth=0;        boolean b=false;        do{            b=false;            try{                System.out.print("请输入该二叉树的深度(大于等于0，小于等于20)：");                depth=Integer.parseInt(read.next());            }            catch(Exception e){                b=true;                System.out.println("请输入数值！");            }        }while(b||depth<0||depth>20);        //前序建立        int i=0;        int Sn=0;        if(depth==0)Sn=1;        else Sn=(int)((1-Math.pow(2, depth+1))/(1-2));        String[] data=new String[Sn];        System.out.println("请按前序的顺序输入该满二叉树的数据：");        int count=Sn;        while (i<Sn){            System.out.print("尚余"+count+"个：");            data[i]=read.next();            i++;            count--;        }        tree newtree=new tree(data,depth,Sn);        search(newtree,depth);    }        public static void search(tree tr,int depth){            System.out.println("层序遍历的数据顺序是：");            LinkedList stack=new LinkedList();            stack.add(tr);            while(!stack.isEmpty()){                tree temp=(tree)stack.getFirst();                if(temp.getLeft()!=null){                    stack.add(temp.getLeft());                    stack.add(temp.getRight());                }                System.out.print(temp.getData()+"  ");                try{                    stack.removeFirst();                }                catch(Exception e){}            }    }}public class tree {    private tree root;    private tree left;    private tree right;    private tree head;    private String data;    private int depth=0,count=1;    public tree(String a){        data=a;        this.left=null;        this.right=null;    }    public tree (String a[],int dep,int sn){        this.data=a[0];        root=this;        if(dep==0)return;        do{            if(root.left!=null&&root.right!=null){                    root=root.head;                    depth--;            }            else{                //未到倒数第二的深度时左右子树的建立                if(depth!=dep-1){                        tree temp=new tree(a[count]);                        //建立左子树                        if(root.left==null){                            root.left=temp;                            temp.head=root;                            root=root.left;                        }//建立右子树                        else {                            root.right=temp;                            temp.head=root;                            root=root.right;                        }                        depth++;                        count++;                }                //到达倒数第二的深度时左右子树的建立                else {                    root.left=new tree(a[count]);                    count++;                    root.right=new tree(a[count]);                    count++;                }            }        }while(count<sn);    }    public String getData() {        return data;    }    public int getDepth() {        return depth;    }    public tree getHead() {        return head;    }    public tree getLeft() {        return left;    }    public tree getRight() {        return right;    }}//该片段来自于http://byrx.net