博客

1.二叉树的节点结构

//二叉树节点结构
public class TreeNode<T> {
    T data;
    TreeNode left;
    TreeNode right;
    public TreeNode(T data){
        this.data = data;
        this.left = null;
        this.right = null;
    }

    @Override
    public String toString() {
        return (String) data;
    }
}

2.打印输出

public class Traverse {

    /**
     * 按层输出二叉树，例如：
     *         A
     *       /  \
     *      B    C
     *    /  \  / \
     *   D   E F   G
     *  / \ / \
     * H  IJ  K
     * 输出结果：
     * Level 1 : A
     * Level 2 : B C
     * Level 3 : D E F G
     * Level 4 : H I J K
     * @param root
     */
    public static void printByLevel(TreeNode root){
        if(root == null){
            return ;
        }

        Queue<TreeNode> queue = new ArrayDeque<>();
        int level = 0;
        queue.offer(root);

        while (!queue.isEmpty()){
            level++;
            System.out.print("Level " + level + " : ");
            int levelNum = queue.size();
            for(int i = 0; i < levelNum; i++){
                TreeNode node = queue.poll();
                System.out.print(node + " ");
                if(node.left != null){
                    queue.offer(node.left);
                }

                if(node.right != null){
                    queue.offer(node.right);
                }
            }
            System.out.println();
        }
    }

    /**
     * 锯齿状输出二叉树，例如：
     *         A
     *       /  \
     *      B    C
     *    /  \  / \
     *   D   E F   G
     *  / \ / \
     * H  IJ  K
     * 输出结果：
     * Level 1 : A
     * Level 2 : C B
     * Level 3 : D E F G
     * Level 4 : K J I H
     * @param root
     */
    public static void printByZigZag(TreeNode root){
        if(root == null){
            return;
        }
        //使用双端队列
        ArrayDeque<TreeNode> dq = new ArrayDeque<>();
        int level = 1;
        //记录每一层中最后打印的节点
        TreeNode lastNode = root;
        TreeNode tempNode = null;

        boolean l2r = true;
        dq.offerFirst(root);

        System.out.print("Level " + level + " : ");
        while(!dq.isEmpty()){
            if(l2r){
                //由左向由的过程:
                //一律从队列头部弹出节点，然后先让其左孩子从尾部进入队列，再让其右孩子从尾部进入队列
                tempNode = dq.pollFirst();
                if(tempNode.left != null){
                    dq.offerLast(tempNode.left);
                }
                if(tempNode.right != null){
                    dq.offerLast(tempNode.right);
                }
            } else {
                //由右向左的过程：
                //一律从队列尾部弹出节点，然后让其右孩子从头部进入队列，在让其左孩子从头部进入队列
                tempNode = dq.pollLast();
                if(tempNode.right != null){
                    dq.offerFirst(tempNode.right);
                }
                if(tempNode.left != null){
                    dq.offerFirst(tempNode.left);
                }
            }
            System.out.print(tempNode + " ");
            if(tempNode == lastNode && !dq.isEmpty()){
                lastNode = l2r ? dq.peekFirst() : dq.peekLast();
                l2r = !l2r;
                level++;
                System.out.println();
                System.out.print("Level " + level + " : ");
            }
        }

    }
    public static void main(String[] args) {
        TreeNode A = new TreeNode("A");
        TreeNode B = new TreeNode("B");
        TreeNode C = new TreeNode("C");
        TreeNode D = new TreeNode("D");
        TreeNode E = new TreeNode("E");
        TreeNode F = new TreeNode("F");
        TreeNode G = new TreeNode("G");
        TreeNode H = new TreeNode("H");
        TreeNode I = new TreeNode("I");
        TreeNode J = new TreeNode("J");
        TreeNode K = new TreeNode("K");

        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;
        D.left = H;
        D.right = I;
        E.left = J;
        E.right = K;


        System.out.println("按层输出二叉树");
        printByLevel(A);

        System.out.println("锯齿状输出二叉树");
        printByZigZag(A);
    }
}