二叉树的建立与遍历

忘是亡心i 2021-09-26 07:36 366阅读 0赞

**二叉树的建立与遍历**  
1.所谓树的遍历，就是按某种次序访问树中的结点，要求每个结点访问一次且仅访问一次。

2.广度优先遍历（层序遍历）  
从最高层（或最底层）开始，向下（或向上）逐层访问，每层从左到右（或从右到左）访问每个结点

3.深度优先遍历（先深遍历）：沿深度方向一路到底，再回溯其它路径（也是一路到底）。  
则可能的遍历次序有：  
前序 VLR 父节点-左子女-右子女  
中序 LVR 左子女-父节点-右子女  
后序 LRV 左子女-右子女-父节点

*  前序遍历  
    前序遍历二叉树算法的框架是  
    
    
     *  若二叉树为空，则空操作；
     *  否则  
        
        
         *  访问根结点 (V)；
         *  前序遍历左子树 (L)；
         *  前序遍历右子树 (R)。
 *  中序遍历  
    中序遍历二叉树算法的框架是：  
    
    
     *  若二叉树为空，则空操作；
     *  否则  
        
        
         *  中序遍历左子树 (L)；
         *  访问根结点 (V)；
         *  中序遍历右子树 (R)。
 *  后序遍历  
    后序遍历二叉树算法的框架是  
    
    
     *  若二叉树为空，则空操作；
     *  否则  
        
        
         *  后序遍历左子树 (L)；
         *  后序遍历右子树 (R)；
         *  访问根结点 (V)。

二叉树的构建与遍历代码如下：

import java.util.LinkedList;
    import java.util.Queue;
    import java.util.Stack;
    
    public class BinaryTree { 
    
        public 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 BinaryTree(){
            this.root =null;
        }
        /* * 递归创建树 */
        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 void preOrder(Node node) {
            if(node!=null){
                System.out.print(node.data+" ");
                preOrder(node.left);
                preOrder(node.right);
            }
        }
        /* * 中序遍历 */
        public void midOrder(Node node) {
            if(node!=null){
                midOrder(node.left);
                System.out.print(node.data+" ");
                midOrder(node.right);
            }
        }
        /* * 后序遍历 */
        public void postOrder(Node node) {
            if(node!=null){
                postOrder(node.left);
                postOrder(node.right);
                System.out.print(node.data+" ");
            }
        }
        /******************* 非递归遍历 **************************/
        /* * 前序遍历 */
        public void n_preOrder(Node node) {
            Stack<Node> S=new Stack<>();
            Node p =node;//p为遍历指针
            while(p!=null){
       //若p为非空 ，访问节点
                System.out.print(p.data+" ");
                //仅当同时存在左右子女时才令右子女入栈
                if(p.left!=null&& p.right!=null){
                    S.push(p.right);
                    p=p.left;
                }else if(p.left!=null){
       //仅存在左子女
                    p=p.left;
                }else if(p.right!=null){
       //仅存在右子女
                    p=p.right;
                }else{
       //若为叶子节点则弹出祖先节点的右子女
                    if(S.isEmpty())
                        break;
                    p=S.pop();
                }           
            }
        }
        /* * 中序遍历 */
        public void n_midOrder(Node node) {
            Stack<Node> S=new Stack<>();
            Node p =node;//p为遍历指针
            while(true){
                while(p!=null){
                    //仅当存在左子树时才入栈
                    if(p.left!=null){
                        S.push(p);
                        p=p.left;
                    }else{
                        //否则直接访问并指向右节点
                        System.out.print(p.data+" ");
                        p=p.right;
                    }
                }
                if(S.isEmpty())//栈空则跳出
                    break;
                p=S.pop();//出栈并访问
                System.out.print(p.data+" ");
                p=p.right;
            }
        }
        /* * 后序遍历 * 1.当前结点指向根结点 * 2.沿当前结点左子树一路到底，把沿途结点和左子树标志分别送入结点栈和标识栈 * 3.弹出标识栈： * 若是从左子树退回，指针指向栈顶结点的右子树，在标识栈送入右子树标识，跳出循环（转向2）； * 若是从右子树退回，则弹出结点并访问之。继续直至栈空或跳出。 * 4.重复2 - 3直至栈空 */
        public void n_postOrder(Node node) {
            Stack<Node> S=new Stack<>();
            Stack<Boolean> Tag=new Stack<>();//true为两次标识 false为单次标识
            Node p= node;
            Boolean tag;
            do{
                while(p!=null){
       //子树智能化处理
                    if(p.left==null&&p.right==null){
       //若无子女
                        System.out.print(p.data+" ");
                        break;
                    }else{
                        //若存在节点,此节点必须入栈
                        S.push(p);
                        //若存在左子女
                        if(p.left!=null){
                            //存在右子女则设置true标识 否则设置false 
                            if(p.right!=null){
                                Tag.push(true);
                            }else{
                                Tag.push(false);
                            }
                            //指针指向左子女 
                            p=p.left;
                        }else{
                        //若仅存在右子女
                            p=p.right;
                            Tag.push(false);//设置单次入栈标识
                        }
                    }
                }
                //若结点栈为非空
                while(!S.isEmpty()){
                    tag=Tag.pop();
                    if(tag){
                        Tag.push(false);
                        p= S.peek().right;//转向右子树
                        break;
                    }else{
                        //单次入栈标识
                        p=S.pop();
                        System.out.print(p.data+" ");
                    }
                }
            }while(!S.isEmpty());
        }
    
        /******************* 层次遍历（借助队列） ******************/
        public void levelOrder(Node node) {
            if(node==null)
                return;
            Node p = node;
            Queue<Node> que=new LinkedList<>();
            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);//右子女入队
            }
        }
    }

测试代码：

import java.util.Scanner;
    
    public class Test {
    
        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();
            BinaryTree binaryTree=new BinaryTree();
            for(int i=0;i<N;i++){ 
                binaryTree.buildTree(binaryTree.root, a[i]);
            }
            System.out.println("*********递归遍历************");
            System.out.println("前序");
            binaryTree.preOrder(binaryTree.root);
            System.out.println("\n中序");
            binaryTree.midOrder(binaryTree.root);
            System.out.println("\n后序");
            binaryTree.postOrder(binaryTree.root);
            System.out.println("\n*********非递归遍历************");
            System.out.println("前序");
            binaryTree.n_preOrder(binaryTree.root);
            System.out.println("\n中序");
            binaryTree.n_midOrder(binaryTree.root);
            System.out.println("\n后序");
            binaryTree.n_postOrder(binaryTree.root);
            System.out.println("\n*********层次遍历************");
            binaryTree.levelOrder(binaryTree.root);
        }
    
    }