- 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://www.codesnippet.cn/detail/091020136318.html
来源: http://www.codesnippet.cn/detail/091020136318.html