二叉树的非递归三种写法和层序遍历

偏执的太偏执、 2024-04-19 00:12 1阅读 0赞

package com.hnist.lzn.Resulbe;
    
    import java.util.LinkedList;
    import java.util.Queue;
    import java.util.Stack;
    
    /*
       二叉树的 前中后序三种非递归的遍历方式
     */
    public class TreeTravel {
    
        public static class TreeNode{
            int val;
            TreeNode left;
            TreeNode right;
            public TreeNode(int val){
    
                this.val = val;
            }
        }
    
    
        // 前序
        public static void preTravel(TreeNode head){
    
            if(head == null)
                return;
            System.out.println("前序遍历:");
            Stack<TreeNode> stack = new Stack<>();
            stack.add(head);
            while(!stack.isEmpty()){
    
                TreeNode node = stack.pop();
                System.out.print(node.val);
                System.out.print(" ");
                if(node.right!=null)
                    stack.add(node.right);
                if(node.left!=null)
                    stack.add(node.left);
            }
        }
    
        // 中序
        public static void midTravel(TreeNode node){
    
            if(node == null)
                return;
            System.out.println("中序遍历：");
            Stack<TreeNode> stack = new Stack<>();
    
            while(!stack.isEmpty() || node!=null)
            {
                if(node !=null)
                {
                    stack.add(node);
                    node = node.left;
    
                }else{
    
                    TreeNode nodes = stack.pop();
                    System.out.print(nodes.val);
                    System.out.print(" ");
                    node = nodes.right;
                    //node = node.right;
                }
    
            }
    
        }
    
        // 后序 非递归
        public static void lasTravel(TreeNode node){
    
    
            if(node == null)
                return;
            System.out.println("后序遍历：");
            Stack<TreeNode> node1 = new Stack<>();
            Stack<TreeNode> node2 = new Stack<>();
            node1.push(node);
            while(!node1.isEmpty()){
                TreeNode head= node1.pop();
                node2.push(head);
    
                if(head.left!=null)
                    node1.push(head.left);
    
                if(head.right!=null)
                    node1.push(head.right);
            }
    
            while(!node2.isEmpty()){
    
                System.out.print(node2.pop().val);
                System.out.print(" ");
            }
    
        }
    
        // 层序遍历
        public static void levelTravel(TreeNode node){
    
            if(node == null)
                return;
            System.out.println("层序遍历:");
            Queue<TreeNode> queue = new LinkedList<>();
            queue.add(node);
            while(!queue.isEmpty()){
    
                TreeNode nodes = queue.poll();
                System.out.print(nodes.val);
                System.out.print(" ");
                if(nodes.left!=null)
                    queue.add(nodes.left);
                if(nodes.right!=null)
                    queue.add(nodes.right);
    
            }
        }
    
    
        public static void main(String[] args) {
    
            TreeNode node= new TreeNode(2);
            TreeNode node1= new TreeNode(1);
            TreeNode node2= new TreeNode(3);
            TreeNode node3= new TreeNode(4);
            TreeNode node4= new TreeNode(5);
            TreeNode node5= new TreeNode(8);
            node.left= node1;
            node.right = node2;
            node1.left = node3;
            node1.right = node4;
            node2.left = node5;
            //preTravel(node);
            //midTravel(node);
            //lasTravel(node);
            levelTravel(node);
        }
    
    }