层序遍历非队列方法

朱雀 2022-11-27 07:19 123阅读 0赞

不使用队列，实现层序遍历

import static java.lang.Integer.max;
    
    public class LayerOrderLearn {
    
        public static void main(String[] args) {
            int arr[]={1,2,3,4,5,6,7,8,9,10};
            BiTNode root = createTree1(arr, 0, arr.length - 1);
            //inOrder(root);
            //printThisLevel(root,4);
            LayerOrder(root);
        }
    
        //1、建树
        static BiTNode createTree1(int arr[],int start,int end){
            if(end-start<0) return null;
    
            int mid=(start+end+1)/2;
            BiTNode root = new BiTNode();
            root.data=arr[mid];
            root.left=createTree1(arr,start,mid-1);
            root.right=createTree1(arr,mid+1,end);
    
            return root;
        }
    
        //建树【方法二】
        static BiTNode createTree(int arr[],int start,int end){
            BiTNode root=null;
            if (start<=end){
                int mid=(start+end+1)/2;
                root=new BiTNode();
                root.data=arr[mid];
                root.left=createTree(arr,start,mid-1);
                root.right=createTree(arr,mid+1,end);
            }
            return root;
        }
    
        /*
        static int Height(BiTNode root){
    
            BiTNode temp=root;
            int height=0;
            while(temp!=null){
                height++;
                temp=temp.right;
            }
            return height;
        }*/
    
        //2、求树的高度
        static int TreeHeight(BiTNode root){
            if (root==null)return 0;
            return max(TreeHeight(root.left),TreeHeight(root.right))+1;
        }
    
        //3、打印树的指定层的结点
        static void printThisLevel(BiTNode root,int level){  //root出口，level出口
    
            if(root==null) return;
    
            if(level==1) System.out.print(root.data+" ");  //有可能是空节点了，但是level=1，这时打印就会出错了
            if(level<=0) return;
            //if(root==null) return;
    
            printThisLevel(root.left,level-1);
            printThisLevel(root.right,level-1);
        }
    
        //4、层序遍历
        static void LayerOrder(BiTNode root){
            int h=TreeHeight(root);
            for (int i = 1; i <=h ; i++) {
                printThisLevel(root,i);
            }
            /*while(h>=1){
                printThisLevel(root,h);
                h--;
            }*/
        }
    
        //[测试] 中序遍历
        public static void inOrder(BiTNode root){
            if (root==null)return;
            inOrder(root.left);
            System.out.print(root.data+" ");
            inOrder(root.right);
        }
    
        //*** 树的结点 ***
        static class  BiTNode{
            int data;
            BiTNode left,right;
        }
    
    }