二叉树-二叉树的基础遍历（3）

深藏阁楼爱情的钟 2024-03-30 08:54 97阅读 0赞

## 二叉树的遍历的三种方式 ##

**1.前序遍历；**  
先访问根结点，然后再访问左子树，最后访问右子树  
**2.中序遍历；**  
先访问左子树，中间访问根节点，最后访问右子树  
**3.后序遍历；**  
先访问左子树，再访问右子树，最后访问根节点  
如果我们分别对下面的树使用三种遍历方式进行遍历，得到的结果如下：  
![在这里插入图片描述][709fb1526cc74288a2fb6b41e7c34bb6.png]

## 前序遍历 ##

> **前序遍历的API：**  
> public Queue preErgodic()：使用前序遍历，获取整个树中的所有键  
> private void preErgodic(Node x,Queue keys)：使用前序遍历，把指定树x中的所有键放入到keys队列中  
> **实现步骤：**  
> 1.把当前结点的key放入到队列中;  
> 2.找到当前结点的左子树，如果不为空，递归遍历左子树  
> 3.找到当前结点的右子树，如果不为空，递归遍历右子树

**代码实现：**

//使用前序遍历，获取整个树中的所有键
    public Queue<Key> preErgodic(){
        
    	Queue<Key> keys = new Queue<>();
    	preErgodic(root,keys);
    	return keys;
    }
    //使用前序遍历，把指定树x中的所有键放入到keys队列中
    private void preErgodic(Node x,Queue<Key> keys){
        
    	if (x==null){
        
    	return;
    }
    	//1.把当前结点的key放入到队列中;
    	keys.enqueue(x.key);
    	//2.找到当前结点的左子树，如果不为空，递归遍历左子树
    	if (x.left!=null){
        
    		preErgodic(x.left,keys);
    	}
    	//3.找到当前结点的右子树，如果不为空，递归遍历右子树
    	if (x.right!=null){
        
    		preErgodic(x.right,keys);
    	}
    }
    	//测试代码
    	public class Test {
        
    		public static void main(String[] args) throws Exception {
        
    		BinaryTree<String, String> bt = new BinaryTree<>();
    			bt.put("E", "5");
    			bt.put("B", "2");
    			bt.put("G", "7");
    			bt.put("A", "1");
    			bt.put("D", "4");
    			bt.put("F", "6");
    			bt.put("H", "8");
    			bt.put("C", "3");
    		Queue<String> queue = bt.preErgodic();
    		for (String key : queue) {
        
    			System.out.println(key+"="+bt.get(key));
    		}
    	}
    }

**运行结果：**

5=E
    2=B
    1=A
    4=D
    3=C
    7=G
    6=F
    8=H

## 中序遍历 ##

> **前序遍历的API：**  
> public Queue midErgodic()：使用中序遍历，获取整个树中的所有键  
> private void midErgodic(Node x,Queue keys)：使用中序遍历，把指定树x中的所有键放入到keys队列中  
> **实现步骤：**  
> 1.找到当前结点的左子树，如果不为空，递归遍历左子树  
> 2.把当前结点的key放入到队列中;  
> 3.找到当前结点的右子树，如果不为空，递归遍历右子树

**代码实现：**

//使用中序遍历，获取整个树中的所有键
    	public Queue<Key> midErgodic(){
        
    		Queue<Key> keys = new Queue<>();
    		midErgodic(root,keys);
    		return keys;
    	}
    	//使用中序遍历，把指定树x中的所有键放入到keys队列中
    	private void midErgodic(Node x,Queue<Key> keys){
        
    	if (x==null){
        
    		return;
    	}
    	//1.找到当前结点的左子树，如果不为空，递归遍历左子树
    	if (x.left!=null){
        
    		midErgodic(x.left,keys);
    	}
    	//2.把当前结点的key放入到队列中;
    	keys.enqueue(x.key);
    	//3.找到当前结点的右子树，如果不为空，递归遍历右子树
    	if (x.right!=null){
        
    		midErgodic(x.right,keys);
    	}
    }
    //测试代码
    public class Test {
        
    	public static void main(String[] args) throws Exception {
        
    	BinaryTree<String, String> bt = new BinaryTree<>();
    	bt.put("E", "5");
    	bt.put("B", "2");
    	bt.put("G", "7");
    	bt.put("A", "1");
    	bt.put("D", "4");
    	bt.put("F", "6");
    	bt.put("H", "8");
    	bt.put("C", "3");
    	Queue<String> queue = bt.midErgodic();
    	for (String key : queue) {
        
    		System.out.println(key+"="+bt.get(key));
    	}
    	}
    }

**运行结果：**

1=A
    2=B
    3=C
    4=D
    5=E
    6=F
    7=G
    8=H

## 后序遍历 ##

> **后序遍历的API：**  
> public Queue afterErgodic()：使用后序遍历，获取整个树中的所有键  
> private void afterErgodic(Node x,Queue keys)：使用后序遍历，把指定树x中的所有键放入到keys队列中  
> **实现步骤：**  
> 1.找到当前结点的左子树，如果不为空，递归遍历左子树  
> 2.找到当前结点的右子树，如果不为空，递归遍历右子树  
> 3.把当前结点的key放入到队列中;

**代码实现：**

//使用后序遍历，获取整个树中的所有键
    public Queue<Key> afterErgodic(){
        
    	Queue<Key> keys = new Queue<>();
    	afterErgodic(root,keys);
    	return keys;
    }
    //使用后序遍历，把指定树x中的所有键放入到keys队列中
    private void afterErgodic(Node x,Queue<Key> keys){
        
    	if (x==null){
        
    	return;
    }
    //1.找到当前结点的左子树，如果不为空，递归遍历左子树
    if (x.left!=null){
        
    	afterErgodic(x.left,keys);
    }
    //2.找到当前结点的右子树，如果不为空，递归遍历右子树
    if (x.right!=null){
        
    	afterErgodic(x.right,keys);
    }
    //3.把当前结点的key放入到队列中;
    keys.enqueue(x.key);
    }
    //测试代码
    public class Test {
        
    public static void main(String[] args) throws Exception {
        
    	BinaryTree<String, String> bt = new BinaryTree<>();
    	bt.put("E", "5");
    	bt.put("B", "2");
    	bt.put("G", "7");
    	bt.put("A", "1");
    	bt.put("D", "4");
    	bt.put("F", "6");
    	bt.put("H", "8");
    	bt.put("C", "3");
    	Queue<String> queue = bt.afterErgodic();
    	for (String key : queue) {
        
    		System.out.println(key+"="+bt.get(key));
    	}
    }
    }

**运行结果：**

1=A
    3=C
    4=D
    2=B
    6=F
    8=H
    7=G
    5=E

## 二叉树的层序遍历 ##

> 所谓的层序遍历，就是从根节点（第一层）开始，依次向下，获取每一层所有结点的值，有二叉树如下：  
> 那么层序遍历的结果是：EBGADFHC  
> **层序遍历的API：**  
> public Queue layerErgodic()：使用层序遍历，获取整个树中的所有键  
> **实现步骤：**  
> 1.创建队列，存储每一层的结点；  
> 2.使用循环从队列中弹出一个结点：  
> 2.1获取当前结点的key；  
> 2.2如果当前结点的左子结点不为空，则把左子结点放入到队列中  
> 2.3如果当前结点的右子结点不为空，则把右子结点放入到队列中  
> ![在这里插入图片描述][c762eb6893334ffeabeeffb11d64bc6f.png]  
> 代码：

//使用层序遍历得到树中所有的键
    public Queue<Key> layerErgodic(){
        
    	Queue<Key> keys = new Queue<>();
    	Queue<Node> nodes = new Queue<>();
    	nodes.enqueue(root);
    	while(!nodes.isEmpty()){
        
    		Node x = nodes.dequeue();
    		keys.enqueue(x.key);
    		if (x.left!=null){
        
    		nodes.enqueue(x.left);
    	}
    	if (x.right!=null){
        
    		nodes.enqueue(x.right);
    	}
    	}
    }
    //测试代码
    public class Test {
        
    public static void main(String[] args) throws Exception {
        
    	BinaryTree<String, String> bt = new BinaryTree<>();
    	bt.put("E", "5");
    	bt.put("B", "2");
    	bt.put("G", "7");
    	bt.put("A", "1");
    	bt.put("D", "4");
    	bt.put("F", "6");
    	bt.put("H", "8");
    	bt.put("C", "3");
    	Queue<String> queue = bt.layerErgodic();
    	for (String key : queue) {
        
    	System.out.println(key+"="+bt.get(key));
    	}
    }
    }

**结果：**

5=E
    2=B
    7=G
    1=A
    4=D
    6=F
    8=H
    3=C

**参考**：黑马程序员Java数据结构与java算法全套教程

[709fb1526cc74288a2fb6b41e7c34bb6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/a056d10daada483cb97cb32c27c68def.png
[c762eb6893334ffeabeeffb11d64bc6f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/c8067280d3534fdba9de6c3a7f858223.png