交换二叉树左右子树图示：(其中橙色表示根节点，蓝色表示普通节点)

image.png

public interface BTreeOperationInterface<TreeNode> {

    /**
     * 创建二叉树
     * @param arr
     */
    TreeNode createBTree(int[] arr);

    /**
     * 判断二叉树是否为空
     * @param treeNode
     * @return
     */
    boolean BTreeEmpty(TreeNode treeNode);

    /**
     * 先序遍历二叉树
     * @param treeNode
     */
    void preOrderTraverseBTree(TreeNode treeNode);

    /**
     * 中序遍历二叉树
     * @param treeNode
     */
    void inOrderTraverseBTree(TreeNode treeNode);

    /**
     * 后序遍历二叉树
     * @param treeNode
     */
    void postOrderTraverseBTree(TreeNode treeNode);

    /**
     * 层次遍历二叉树
     */
    void levelTraverseBTree(TreeNode treeNode);

    /**
     * 求二叉树深度
     * @param treeNode
     * @return
     */
    int BTreeDepth(TreeNode treeNode);

    /**
     * 清空二叉树
     * @param treeNode
     */
    void clearBTree(TreeNode treeNode);

    /**
     * 统计叶子节点个数
     * @param root
     * @return
     */
    int countLeaf(TreeNode root);

    /**
     * 交换左右子树
     */
    TreeNode swapSubLeftTreeAndRightTree(TreeNode root);
}

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;

public class BinaryTreeTest {
    public static void main(String[] args){
        int[] arr={0,1,2,3,4,5,6};
        BTreeOpration bTreeOpration=new BTreeOpration();
        //创建二叉树
        TreeNode root=bTreeOpration.createBTree(arr);

        //层次遍历二叉树
        System.out.print("层次遍历：");
        bTreeOpration.levelTraverseBTree(root);

        //递归先序遍历
        System.out.print("先序遍历(递归)：");
        bTreeOpration.preOrderTraverseBTree(root);
        System.out.println();

        System.out.print("根 右 左：");
        bTreeOpration.traverseBTree(root);
        System.out.println();

        //迭代先序遍历
        System.out.print("先序遍历(迭代)：");
        bTreeOpration.preOrderTraverseBTreeIterator(root);

        //递归中序遍历
        System.out.print("中序遍历(递归)：");
        bTreeOpration.inOrderTraverseBTree(root);
        System.out.println();

        //迭代中序遍历
        System.out.print("中序遍历(迭代)：");
        bTreeOpration.inOrderTraverseBTreeIterator(root);

        //递归后序遍历
        System.out.print("后序遍历(递归)：");
        bTreeOpration.postOrderTraverseBTree(root);
        System.out.println();

        //迭代后序遍历
        System.out.print("后序遍历(迭代)：");
        bTreeOpration.postOrderTraverseBTreeIterator(root);

        System.out.println("树的深度："+bTreeOpration.BTreeDepth(root));

        System.out.println("叶子节点个数："+bTreeOpration.countLeaf(root));

        //交换左右子树
        root=bTreeOpration.swapSubLeftTreeAndRightTree(root);
        System.out.print("交换后的层次遍历：");
        bTreeOpration.levelTraverseBTree(root);
    }

    static class BTreeOpration implements BTreeOperationInterface<TreeNode>{
        /**
         * 根结点
         */
        private TreeNode root;


        /**
         * 给定一组整数，请按照从上到下，从左到右的顺序构造一棵二叉树(其实就是完全二叉树)
         * eg: arr=[2,4,5,1,3];
         * return=2(4(1,3),5)
         * @param arr
         * @return TreeNode
         */
        @Override
        public TreeNode createBTree(int[] arr) {
            List<TreeNode> nodeList = new LinkedList<TreeNode>();
            //将数组的值转化为TreeNode
            for(int index=0;index < arr.length;index++){
                nodeList.add(new TreeNode(arr[index]));
            }

            //按照数组中父节点与孩子节点下标的关系建立二叉树
            //从上往下构建
            //右端点：2*i+2≤n => i≤(n/2)-1
            for(int i=0;i<(arr.length >> 1);i++){
                //左孩子：2*i+1
                nodeList.get(i).setLeft(nodeList.get((i<<1)+1));
                //右孩子：2*i+2
                //右孩子存在，才建立右孩子
                if((i<<1)+2 < arr.length){
                    nodeList.get(i).setRight(nodeList.get((i<<1)+2));
                }
            }
            root=nodeList.get(0);
            return root;
        }

        @Override
        public boolean BTreeEmpty(TreeNode treeNode) {
            return treeNode==null;
        }


        /**
         * 先序遍历递归实现
         * @param node
         */
        @Override
        public void preOrderTraverseBTree(TreeNode node) {
            //用的是if，若用while，会卡在左子树最左边的地方出不去
            if (node != null){
                System.out.print(node.data+" ");
                preOrderTraverseBTree(node.left);
                preOrderTraverseBTree(node.right);
            }

        }

        /**
         * 根 右 左
         * @param node
         */
        public void traverseBTree(TreeNode node) {
            //用的是if，若用while，会卡在左子树最左边的地方出不去
            if (node != null){
                System.out.print(node.data+" ");
                traverseBTree(node.right);
                traverseBTree(node.left);
            }

        }
        /**
         * 先序遍历迭代实现
         * @param node
         */
        public void preOrderTraverseBTreeIterator(TreeNode node) {
            StringBuilder sb=new StringBuilder();
            if(node==null)
                return;
            Stack<TreeNode> stack=new Stack<>();
            TreeNode currentNode=node;

            while (currentNode != null || !stack.isEmpty()){
                while (currentNode != null){
                    sb.append(currentNode.data);
                    sb.append(" ");
                    stack.push(currentNode);
                    currentNode=currentNode.left;
                }
                //该位置已经到最左边
                //注意，叶子节点的左右节点（为null）同样需要判断
                if(!stack.isEmpty()){
                    currentNode=stack.pop();
                    currentNode=currentNode.right;
                }
            }
            System.out.println(sb.toString().trim());

        }
        @Override
        public void inOrderTraverseBTree(TreeNode node) {
            if (node != null){
                inOrderTraverseBTree(node.left);
                System.out.print(node.data+" ");
                inOrderTraverseBTree(node.right);
            }
        }

        /**
         * 中序遍历迭代实现
         * @param node
         */
        public void inOrderTraverseBTreeIterator(TreeNode node) {
            StringBuilder sb=new StringBuilder();
            TreeNode currentNode = node;
            if (currentNode == null)
                return;
            Stack<TreeNode> stack = new Stack<>();
            while (currentNode!=null || !stack.isEmpty()){
                while (currentNode!=null){
                    stack.push(currentNode);
                    currentNode=currentNode.left;
                }
                //此时，currentNode已经为null（最左边的叶子节点的左节点）
                if(!stack.isEmpty()){
                    //最左边的叶子节点，弹栈
                    currentNode=stack.pop();
                    sb.append(currentNode.data);
                    sb.append(" ");
                    currentNode=currentNode.right;
                }
            }
            System.out.println(sb.toString().trim());
        }
        @Override
        public void postOrderTraverseBTree(TreeNode node) {
            if (node != null){
                postOrderTraverseBTree(node.left);
                postOrderTraverseBTree(node.right);
                System.out.print(node.data+" ");
            }
        }

        /**
         * 后序遍历迭代实现（可用双栈实现）
         * （类似前序遍历）：首先按： 根 右 左次序遍历，然后反转，得左 右 根
         * @param node
         */
        public void postOrderTraverseBTreeIterator(TreeNode node) {
            StringBuilder sb=new StringBuilder();
            TreeNode currentNode = node;
            if (currentNode == null)
                return;
            Stack<TreeNode> stack=new Stack<>();
            while (currentNode !=null || !stack.isEmpty()){
                while (currentNode!=null){
                    stack.push(currentNode);
                    sb.append(currentNode.data);
                    sb.append(" ");
                    currentNode=currentNode.right;
                }
                if(!stack.isEmpty()){
                    currentNode=stack.pop();
                    currentNode=currentNode.left;
                }
            }
            System.out.println(sb.reverse().toString().trim());
        }

        /**
         * 层次遍历二叉树
         * @param treeNode
         */
        @Override
        public void levelTraverseBTree(TreeNode treeNode){
            StringBuilder sb=new StringBuilder();
            Queue<TreeNode> queue=new LinkedList<>();
            queue.offer(treeNode);
            while (!queue.isEmpty()){
                TreeNode root=queue.poll();
                sb.append(root.data);
                sb.append(" ");
                if(root.left!=null)
                    queue.offer(root.left);
                if(root.right!=null)
                    queue.offer(root.right);
            }
            System.out.println(sb.toString().trim());
        }

        @Override
        public int BTreeDepth(TreeNode treeNode) {
            if(treeNode==null)
                return 0;
            int depLeft=BTreeDepth(treeNode.left);
            int depRight=BTreeDepth(treeNode.right);
            return depLeft > depRight ? depLeft+1 : depRight+1;
        }

       //不一定正确
        @Override
        public void clearBTree(TreeNode treeNode) {
            treeNode=null;
        }

//####################################################################
    /**
     * 叶子节点个数
     */
    private int count=0;

    /**
     * 统计叶子节点个数
     */
    @Override
    public int countLeaf(TreeNode root){
        if(root==null)
            return 0;
        if(root.getLeft()==null && root.getRight()==null){
            count++;
        }
        countLeaf(root.getLeft());
        countLeaf(root.getRight());
        return count;
    }

    /**
     * 交换左右子树
     */
    @Override
    public TreeNode swapSubLeftTreeAndRightTree(TreeNode root){
        if(root==null)
            return null;
        //交换左右子树
        TreeNode leftTree=root.getLeft();
        root.setLeft(root.getRight());
        root.setRight(leftTree);

        swapSubLeftTreeAndRightTree(root.getLeft());
        swapSubLeftTreeAndRightTree(root.getRight());
        return root;
    }
    }

    /**
     * 二叉树结点
     */
    static class TreeNode {
        private TreeNode left;
        private TreeNode right;
        private int data;
        /**
         * 构造节点
         * @param data
         */
        public TreeNode(int data) {
            this.data = data;
            this.left=null;
            this.right=null;
        }
        public TreeNode(){}

        public void setLeft(TreeNode left) {
            this.left = left;
        }

        public void setRight(TreeNode right) {
            this.right = right;
        }

        public Integer getData() {
            return data;
        }

        @Override
        public String toString() {
            return "TreeNode{" +
                    "left=" + left +
                    ", right=" + right +
                    ", data=" + data +
                    '}';
        }
    }
}

结果：

image.png