二叉树遍历（附Java实现代码）

向右看齐 2022-12-12 01:56 160阅读 0赞

## 二叉树遍历（附Java实现代码） ##

二叉树遍历可以有两种方法：递归遍历的方式与非递归遍历的方式。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoaG1vbmtleQ_size_16_color_FFFFFF_t_70_pic_center]

**先序遍历**就是先遍历**根**节点再**左**再**右**；

**中序遍历**就是先**左**再**根**再**右**；

**后序遍历**就是先**左**再**右**再**根**；

先构建这棵树，然后分别调用相应的方法实现，代码如下：

package binarytree;
    
    import java.util.ArrayList;
    import java.util.LinkedList;
    import java.util.List;
    import java.util.Queue;
    import java.util.Stack;
    
    public class Test { 
        //递归遍历的方式与非递归遍历的方式:
        //一、递归的方式：
    	//1、先序遍历：
    	private static void preOrder1(Node root){ 
    		if(root == null) return;
    		System.out.print(root.value);
    		preOrder1(root.left);
    		preOrder1(root.right);
    	}
    	//2、中序遍历：
    	private static void midOrder1(Node root){ 
    		if(root == null) return;
    		midOrder1(root.left);
    		System.out.print(root.value);
    		midOrder1(root.right);
    	}
    	//3、后序遍历：
    	private static void postOrder1(Node root){ 
    		if(root == null) return;
    		postOrder1(root.left);
    		postOrder1(root.right);
    		System.out.print(root.value);
    	}
        
        //二、非递归的方式：
    	//1、先序遍历：
    	private static void preOrder2(Node root){ 
    		if(root == null) return;
    		Stack<Node> stack = new Stack<>();//用栈来存储（先进后出）
    		stack.push(root);
    		while(!stack.isEmpty()){ 
    			Node node = stack.pop();
    			System.out.print(node.value);
    			if(node.right != null) stack.push(node.right);
    			if(node.left != null) stack.push(node.left);
    		}
    	}
    	//2、中序遍历
    	private static void midOrder2(Node root){ 
    		if(root == null) return;
    		Stack<Node> stack = new Stack<>();
    		Node cur = root;
    		while(!stack.isEmpty() || cur != null){ 
    			while(cur != null){ 
    				stack.push(cur);
    				cur = cur.left;
    			}
    			Node node = stack.pop();
    			System.out.print(node.value);
    			if(node.right != null) cur= node.right;
    		}
    	}
    	//3、后序遍历：
    	private static void postOrder2(Node root){ 
    		if(root == null) return;
    		Stack<Node> stack = new Stack<>();
    		Stack<Node> stack2 = new Stack<>();
    		stack.push(root);
    		while(!stack.isEmpty()){ 
    			Node node = stack.pop();
    			stack2.push(node);
    			if(node.left != null) stack.push(node.left);
    			if(node.right != null) stack.push(node.right);
    		}
    		while(!stack2.isEmpty()){ 
    			System.out.print(stack2.pop().value);
    		}
    	}
    	
        //三、层序遍历
    	private static void bfs(Node root){ 
    		if(root == null) return;
    		Queue<Node> queue = new LinkedList<>();//用队列来存储（先进先出）
    		queue.add(root);
    		while(!queue.isEmpty()){ 
    			Node node = queue.poll();
    			System.out.print(node.value);
    			if(node.left != null) queue.add(node.left);
    			if(node.right != null) queue.add(node.right);
    		}
    	}
    	private static List<List<String>> bfs2(Node root){ 
    		List<List<String>> res = new ArrayList<>();//存储节点（List里面套List）
    		
    		Queue<Node> queue = new LinkedList<>();//用队列来存储（先进先出）
    		queue.add(root);
    		
    		List<String> list;
    		while(!queue.isEmpty()){ 
    			int size = queue.size();
    			list = new ArrayList<>();
    			while(size-- > 0){ 
    				Node node = queue.poll();
    				list.add(node.value);
    				if(node.left != null) queue.add(node.left);
    				if(node.right != null) queue.add(node.right);
    			}
    			res.add(list);
    		}
    		return res;
    	}
        
    	public static void main(String[] args) { 
    		Node nodeA = new Node("A");
    		Node nodeB = new Node("B");
    		Node nodeC = new Node("C");
    		Node nodeD = new Node("D");
    		Node nodeE = new Node("E");
    		Node nodeF = new Node("F");
    		Node nodeG = new Node("G");
    		
    		//构建二叉树
    		nodeA.left = nodeB;
    		nodeA.right = nodeC;
    		nodeB.left = nodeD;
    		nodeB.right = nodeE;
    		nodeC.right = nodeF;
    		nodeE.left = nodeG;
    		
    		preOrder1(nodeA);
    		System.out.println();
    		midOrder1(nodeA);
    		System.out.println();
    		postOrder1(nodeA);
    		System.out.println();
    		preOrder2(nodeA);
    		System.out.println();
    		midOrder2(nodeA);
    		System.out.println();
    		postOrder2(nodeA);
    		System.out.println();
    		bfs(nodeA);
            
            bfs2(nodeA);
    	}
    	
    	public static class Node{  //节点
    		public String value;
    		public Node left;
    		public Node right;
    		
    		public Node(String value){ 
    			this.value = value;
    		}
    	}
    
    }

运行结果如下图所示：

![在这里插入图片描述][20201004195530626.PNG_pic_center]

其中，层序遍历这里多写了一个方法，将每层的节点存储起来：

private static List<List<String>> bfs2(Node root){ 
    		List<List<String>> res = new ArrayList<>();//存储节点（List里面套List）
    		
    		Queue<Node> queue = new LinkedList<>();//用队列来存储（先进先出）
    		queue.add(root);
    		
    		List<String> list;
    		while(!queue.isEmpty()){ 
    			int size = queue.size();
    			list = new ArrayList<>();
    			while(size-- > 0){ 
    				Node node = queue.poll();
    				list.add(node.value);
    				if(node.left != null) queue.add(node.left);
    				if(node.right != null) queue.add(node.right);
    			}
    			res.add(list);
    		}
    		return res;
    	}

在debug中查看res的结果：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoaG1vbmtleQ_size_16_color_FFFFFF_t_70_pic_center 1]  
【参考Queue部分】[http://blog.sina.com.cn/s/blog\_14ffae8a60102x2x6.html][http_blog.sina.com.cn_s_blog_14ffae8a60102x2x6.html]  
【视频参考】[https://www.bilibili.com/video/BV1oV411d7U5?spm\_id\_from=333.999.0.0][https_www.bilibili.com_video_BV1oV411d7U5_spm_id_from_333.999.0.0]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoaG1vbmtleQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/5501e5993f4e493ebca7e1038637cc3f.png
[20201004195530626.PNG_pic_center]: /images/20221123/43963c6ee78d4d3698a5a10296e06808.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hoaG1vbmtleQ_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/5bbd2d2206664357bb72f185f779bc0e.png
[http_blog.sina.com.cn_s_blog_14ffae8a60102x2x6.html]: http://blog.sina.com.cn/s/blog_14ffae8a60102x2x6.html
[https_www.bilibili.com_video_BV1oV411d7U5_spm_id_from_333.999.0.0]: https://www.bilibili.com/video/BV1oV411d7U5?spm_id_from=333.999.0.0