二叉树的各种遍历方式实现（Java）

素颜马尾好姑娘i 2023-03-03 11:05 12阅读 0赞

**目录**

二叉树定义如下：

一、前中后序遍历

1.递归实现

2.非递归实现

二、广度优先遍历（BFS）

1.递归实现

2.非递归实现

三、深度优先遍历（DFS）

1.递归实现

2.非递归实现

四、参考链接

--------------------

# 二叉树定义如下： #

class TreeNode{  
        public int val;  
        public TreeNode left;  
        public TreeNode right;  
        TreeNode(int x) { val = x; }  
    }

# 一、前中后序遍历 #

## 1.递归实现 ##

/**
    * 前序遍历
    * 从根节点开始，先遍历左子树，后遍历右子树
    */
    public static void preOrderTraveral(TreeNode root){
        if(root!=null){
           System.out.println(root.val);
           preOrderTraveral(root.left);
           preOrderTraveral(root.right);
        
        }
    }
    
    
    /**
    * 中序遍历
    * 先遍历左子树，再遍历根节点，后遍历右子树
    */
    public static void inOrderTraveral(TreeNode root){
        if(root!=null){
           inOrderTraveral(root.left);
           System.out.println(root.val);
           inOrderTraveral(root.right);
        
        }
    }
    
    
    /**
    * 后序遍历
    * 先遍历左子树，再遍历右子树，后遍历根节点
    */
    public static void postOrderTraveral(TreeNode root){
        if(root!=null){
           postOrderTraveral(root.left);
           postOrderTraveral(root.right);
           System.out.println(root.val);
        
        }
    }

## 2.非递归实现 ##

//前序遍历的非递归实现，用栈
        public static void preOrderfun(TreeNode root){
    		Stack<TreeNode> stack =new Stack<TreeNode>();
    		TreeNode tmp=null;
    		if(root!=null){
    			stack.push(root);
    			while(!stack.isEmpty()){
    				tmp=stack.pop();
    				System.out.println(tmp.val);
    				if(tmp.right!=null){stack.push(tmp.right);}
    				if(tmp.left!=null){stack.push(tmp.left);}
    			}
    		}
    		
    	}
    
    
    //中序遍历的非递归实现，用栈
    public static void inOrderfun(TreeNode root){
    		Stack<TreeNode> stack =new Stack<TreeNode>();
    		TreeNode tmp=null;
    		if(root!=null){
    			tmp=root;
    			while(!stack.isEmpty() || tmp!=null){
    				while(tmp!=null){//处理所有左结点，进栈
    					stack.push(tmp);
    					tmp=tmp.left;
    				}
    				if(!stack.isEmpty()){//执行到这里，栈顶元素没有左孩子或者左子树都被访问过
    					tmp=stack.pop();
    					System.out.print(tmp.val);
    					tmp=tmp.right;
    				}
    		}
    		
    	}
    }
    
    
    //后序遍历的非递归实现，双栈,临时存储tmp，结果存储res
    public void postOrder(TreeNode root) {
    		Stack<TreeNode> tmp = new Stack<TreeNode>();
    		Stack<TreeNode> res = new Stack<TreeNode>();
    		tmp.push(root);
    		while(!tmp.isEmpty()){
    			TreeNode cur = tmp.pop();
    			res.push(cur);
    			if(cur.left != null){
    				tmp.push(cur.left);
    			}
    			if(cur.right != null){
    				tmp.push(cur.right);
    			}
    		}
    		//输出最终后序遍历的结果
    		while(!res.isEmpty()){
    			System.out.print(res.pop().val + " ");
    		}	
    	}

# 二、广度优先遍历（BFS） #

## 1.递归实现 ##

## 2.非递归实现 ##

public void BFS(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>(); // 核心数据结构队列
    
        queue.offer(root);
    
        while (!queue.isEmpty()) { // 一层走到下一层
            int sz = queue.size();
            // 取当前节点，往下走
            for (int i = 0; i < sz; i++) {
                TreeNode cur = queue.poll();
                if (cur.left != null)
                    queue.offer(cur.left);
                if (cur.right != null)
                    queue.offer(cur.right);
            }
        }
    }

# 三、深度优先遍历（DFS） #

## 1.递归实现 ##

//DFS递归实现
    public void dfs(TreeNode root) {
        if (root == null)
            return;
        ……
    
        if (root.left != null)
            dfs(root.left);
        if (root.right != null)
            dfs(root.right);
    }

## 2.非递归实现 ##

//DFS的迭代实现版本（Stack）
    public void dfs(TreeNode root) {
         if (root != null)
             return;
         Stack<TreeNode> stack = new Stack<>();
         stack.push(root);
     
         while (!stack.isEmpty()) {
             TreeNode tmp = stack.pop();
                
             ……
    
             if (tmp.right != null)
                 stack.push(tmp.right);
             if (tmp.left != null)
                 stack.push(tmp.left);
         }
    }

# 四、参考链接 #

[https://blog.csdn.net/a784586/article/details/61920892][https_blog.csdn.net_a784586_article_details_61920892]

[https://blog.csdn.net/qq\_39445165/article/details/90749343][https_blog.csdn.net_qq_39445165_article_details_90749343]

[https://blog.csdn.net/hongxue8888/article/details/102935259][https_blog.csdn.net_hongxue8888_article_details_102935259]

[https_blog.csdn.net_a784586_article_details_61920892]: https://blog.csdn.net/a784586/article/details/61920892
[https_blog.csdn.net_qq_39445165_article_details_90749343]: https://blog.csdn.net/qq_39445165/article/details/90749343
[https_blog.csdn.net_hongxue8888_article_details_102935259]: https://blog.csdn.net/hongxue8888/article/details/102935259