交换左右子树的两种实现（递归和非递归）

淩亂°似流年 2021-09-26 13:08 435阅读 0赞

递归实现：  
基本思想：  
\- 交换左右子树  
\- 对左子树进行递归交换  
\- 符右子树进行递归交换

非递归实现：  
\- 借助栈来实现  
\- 首先交换左右子树  
\- 右子树不为空时将右子树入栈  
\- 左子树不为空时指针指向左子树  
\- 否则出栈

实验过程如下：

import java.util.LinkedList;
    import java.util.Queue;
    import java.util.Scanner;
    import java.util.Stack;
    
    public class TransLeftRight { 
    
        public static Node root;//根节点
        ///
        ///内部类 表示节点
        ///
        private class Node { 
            private Node left;
            private Node right;
            private int data;
    
            public Node(int data) {
                this.left = null;
                this.right = null;
                this.data = data;
            }       
        }
        public TransLeftRight(){
            this.root =null;
        }
        /** * @param args */
        public static void main(String[] args) {
            // TODO Auto-generated method stub
            Scanner scanner=new Scanner(System.in);
            int N =scanner.nextInt();//数组大小
            int[] a=new int[N];
            for(int i=0;i<N;i++)
                a[i]=scanner.nextInt();
            TransLeftRight binaryTree=new TransLeftRight();
            for(int i=0;i<N;i++){
                binaryTree.buildTree(binaryTree.root, a[i]);
            }
            System.out.println("********交换顺序前*********");
            levelOrder(root);
            ExchangeLeftRight(root);
            System.out.println();
            System.out.println("********交换顺序后*********");
            levelOrder(root);
            System.out.println();
            ExchangeLeftRight2(root);
            System.out.println("********再次交换顺序后*********");
            levelOrder(root);
        }
        /* * 递归创建树 创建的是二叉排序树 即左边节点小于父节点 右边节点大于父节点 */
        public void buildTree(Node node,int data) {
            if(root==null){
                root = new Node(data);
            }else{
                if(data<node.data){
                    if(node.left==null){
                        node.left = new Node(data);
                    }else{
                        buildTree(node.left, data);
                    }
                }else{
                    if(node.right==null){
                        node.right = new Node(data);
                    }else{
                        buildTree(node.right, data);
                    }
                }
            }
        }
        /**************递归交换********************/
        public static void ExchangeLeftRight(Node node) {
            if(node == null)//节点为空 则返回
                return ;
            if(node.left==null&&node.right==null){
       //节点无左右孩子，返回
                return ;
            }
            else{
       //交换左右孩子
                Node temp = node.left;
                node.left = node.right;
                node.right = temp;
            }
            ExchangeLeftRight(node.left);//对左子树进行交换操作
            ExchangeLeftRight(node.right);//对右子树进行交换操作
        }
        /**************非递归交换（用栈实现）********************/
        public static void ExchangeLeftRight2(Node node) {
            if(node == null)
                return ;
            Node p = node;//指针
            Stack<Node> stack = new Stack<Node>();
            p = node;
            /** * 首先交换左右子树 * 如果右子树不为空则入栈 * 如果左子树不为空则将指针指向左子树，对左子树进行同样的操作 * 否则，出栈 */
            while(true){
                Node temp = p.left;
                p.left = p.right;
                p.right = temp;
                if(p.right !=null){
       //将右节点入栈
                    stack.push(p.right);
                }
                if(p.left !=null){
       //指向左节点
                    p = p.left;
                }else{
                    if(stack.isEmpty()){
       //栈为空时结束
                        break;
                    }else{
                        p = stack.pop();    
                    }
                }
    
            }
        }
        /***************层次遍历打印*******************/
        public static void levelOrder(Node node) {
            if(node==null)
                return;
            Node p = node;
            Queue<Node> que=new LinkedList<Node>();
            que.add(p);
            while(!que.isEmpty()){
                //队首元素出栈
                p = que.remove();
                System.out.print(p.data+" ");
                if(p.left!=null)
                    que.add(p.left);//左子女入队
                if(p.right!=null)
                    que.add(p.right);//右子女入队
            }
        }
    }

实验结果：  
![这里写图片描述][Image 1]

[Image 1]: