java 从上至下打印二叉树

从上往下打印二叉树
题目描述：

从上往下打印出二叉树的每个节点，同层节点从左至右打印。

输入：

输入可能包含多个测试样例。

对于每个测试案例，输入的第一行一个整数n(1<=n<=1000, ：n代表将要输入的二叉树元素的个数（节点从1开始编号）。接下来一行有n个数字,代表第i个二叉树节点的元素的值。接下来有n行，每行有一个字母Ci。

Ci=’d’表示第i个节点有两子孩子，紧接着是左孩子编号和右孩子编号。

Ci=’l’表示第i个节点有一个左孩子，紧接着是左孩子的编号。

Ci=’r’表示第i个节点有一个右孩子，紧接着是右孩子的编号。

Ci=’z’表示第i个节点没有子孩子。

输出：

对应每个测试案例，

按照从上之下，从左至右打印出二叉树节点的值。

样例输入：

8 6 5 7 10 9 11

d 2 5

d 3 4

d 6 7

样例输出：

8 6 10 5 7 9 11

二叉树的实现记得一般都是用指针，左儿子，右儿子，什么的。

但是自己觉得可以用数组来实现一发。、

下面就是用数组实现的代码，主要是存储二叉树，和一层一层的打印。

 import java.util.Scanner;

 public class Main {

     public static void main(String[] args) {

         // TODO Auto-generated method stub

         Scanner in = new Scanner(System.in) ;

         int node[][] = new int [1005][4] ; ///0为节点的值，1左孩子，2父节点，3右孩子

         while(in.hasNextInt()){

             int n = in.nextInt() ;

             for(int i=1;i<=n;i++){

                 node[i][0] = in.nextInt() ;

             }

             for(int i=1;i<=n;i++){ ///节点的初始化

                 node[i][2] = i ;

                 node[i][1]=node[i][3]=0 ;

             }

             for(int i=1;i<=n;i++){

                 String str = in.next() ;

                 if(str.equals("d")){

                     int x = in.nextInt() ;

                     int y = in.nextInt() ;

                     node[i][1] = x ;

                     node[i][3] = y ;

                     node[x][2] = i ;

                     node[y][2] = i ;

                 }else if(str.equals("l")){

                     int x = in.nextInt() ;

                     node[i][1] = x ;

                     node[i][3] = 0 ;

                     node[x][2] = i ;

                 }else if(str.equals("r")){

                     int x = in.nextInt() ;

                     node[i][1] = 0 ;

                     node[i][3] = x ;

                     node[x][2] = i ;

                 }

             }

             int root = 1 ;  ///寻找根节点

             while(root != node[root][2] ){

                 root = node[root][2] ;

             }

             //System.out.println(root);

             int arry1[] = new int[1005];

             int arry2[] = new int[1005];

             arry1[1] = root ;

             int cnt = 2 ;

             //System.out.println("yes");

             ///开始打印二叉树

             System.out.print(node[root][0]);

             while(true){

                 if(arry1[1]!=root){ ///不再打印根节点

                     for(int i=1;i<cnt;i++){

                         System.out.print(" "+node[arry1[i]][0]);

                     }

                 }

                 int c = 1 ;

                 for(int i=1;i<cnt;i++){

                     if(node[arry1[i]][1]!=0){  ///如果有左孩子

                         arry2[c]=node[arry1[i]][1] ;

                         c++ ;

                     }

                     if(node[arry1[i]][3]!=0){  ///如果有右孩子

                         arry2[c]=node[arry1[i]][3] ;

                         c++ ;

                     }

                 }

                 cnt=c ;

                 for(int i=1;i<cnt;i++){

                     arry1[i] = arry2[i] ;

                 }

                 if(c==1)break ;

             }

         }

     }

 }

巴特西

java 从上至下打印二叉树

最新文章

热门文章