数据结构学习——树形结构之非递归遍历二叉树

妖狐艹你老母 2023-09-28 14:33 18阅读 0赞

> 前文有介绍二叉树以及递归遍历二叉树的内容，有兴趣的朋友可以去看看：[树形结构之递归遍历二叉树][Link 1]

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

**目录**

一. 非递归前序遍历

二. 非递归中序遍历

三. 非递归后序遍历

四. 数据结构专栏

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

## 一. 非递归前序遍历 ##

> 前序遍历（DLR，lchild,data,rchild），是二叉树遍历的一种，也叫做先根遍历、先序遍历、前序周游，可记做根左右。前序遍历首先访问根结点然后遍历左子树，最后遍历右子树。  
> 前序遍历首先访问根结点然后遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问 [根结点][Link 2]，然后遍历左子树，最后遍历右子树。  
> 若 [二叉树][Link 3]为空则结束返回，否则：  
> （1）访问根结点。  
> （2）前序遍历左子树 。  
> （3）前序遍历右子树 。  
> 需要注意的是：遍历左右子树时仍然采用前序遍历方法。

如图所示:

![f236a4c547720b133f7da2d4ea92f8a5.png][]

>   
> 除使用递归以外，二叉树的遍历也可以用非递归的方式来实现。绝大多数可以用递归解决的问题，其实都可以用另一种数据结构来解决，这种数据结构就是栈。因为递归和栈都有回溯的特性。  
> 如何借助栈来实现二叉树的非递归遍历呢？下面以二叉树的前序遍历为例，看一看具体过程：  
> 1. 首先遍历二叉树的根节点A，放入栈中。

![73f0aabb6f9fc4cacb4f492e43e124c0.png][]

> 2. 遍历根节点1的左孩子节点2，放入栈中。

![1d4fa418bf3a778595faaecc1625b506.png][]

> 3. 遍历节点2的左孩子节点4，放入栈中。

![92ef5684fa738ded08b536aaf7c298df.png][]

> 4. 节点4既没有左孩子，也没有右孩子，我们需要回溯到上一个节点2。可是现在并不是做递归操作，怎么回溯呢？别担心，栈已经存储了刚才遍历的路径。让旧的栈顶元素4出栈，就可以重新访问节点2，得到节点2的右孩子节点5。此时节点2已经没有利用价值（已经访问过左孩子和右孩子），节点2出栈，节点5入栈。

![3a9773627189c702b29f9cc39ab7e763.png][]

> 5. 节点5既没有左孩子，也没有右孩子，我们需要再次回溯，一直回溯到节点1。所以让节点5出栈。  
> 根节点1的右孩子是节点3，节点1出栈，节点3入栈。

![da5cf4a1285f0ef86bd0398294ab6101.png][]

> 6. 节点3的右孩子是节点6，节点3出栈，节点6入栈。

![92866c3d469737aaed5d3d4d25b82f8f.png][]

> 7. 节点6既没有左孩子，也没有右孩子，所以节点6出栈。此时栈为空，遍历结束。

![29e6ac554fe0f4e2f394a09431e0bc8f.png][]

代码如下：

//前序遍历的非递归实现
    
    import java.util.Stack;
    
    public class Test {
    	public static void main(String[] args) {
    		TreeNode[] node = new TreeNode[10];
    		for (int i = 0; i < 10; i++) {
    			node[i] = new TreeNode(i);
    		}
    		for (int i = 0; i < 10; i++) {
    			if (i * 2 + 1 < 10)
    				node[i].left = node[i * 2 + 1];
    			if (i * 2 + 2 < 10)
    				node[i].right = node[i * 2 + 2];
    		}
    		// 非递归实现
    		preOrderRe(node[0]);
    	}
    
    	public static void preOrderRe(TreeNode biTree) {
    		Stack<TreeNode> stack = new Stack<TreeNode>();
    		//循环体中的biTree会被设置为指向左或右节点，因此可能为空。但只要栈不为空就循环
    		while (biTree != null || !stack.isEmpty()) {
    			//一直遍历到最左边的左子节点之后结束
    			while (biTree != null) {
    				System.out.print(biTree.value+" ");
    				stack.push(biTree);
    				biTree = biTree.left;
    			}
    			//只要栈不为空，就出栈上面的左子节点，就能回溯到当前根节点，接着遍历右子节点
    			if (!stack.isEmpty()) {
    				biTree = stack.pop();
    				biTree = biTree.right;
    			}
    		}
    	}
    }
    
    //节点结构
    class TreeNode {
    	int value;
    	TreeNode left;
    	TreeNode right;
    
    	TreeNode(int value) {
    		this.value = value;
    	}
    }

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

## 二. 非递归中序遍历 ##

> 中序遍历（LDR）是 [二叉树遍历][Link 4]的一种，也叫做 [中根遍历][Link 5]、中序周游。在二叉树中，先左后根再右。巧记：左根右。  
> 中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树  
> 若 [二叉树][Link 3]为空则结束返回，  
> 否则：  
> （1）中序遍历左子树  
> （2）访问根结点  
> （3）中序遍历右子树

如图所示：

![d9b0355d1063ac78bd70b0b672c2248c.png][]

> 中序遍历结果：DBEAFC

实现代码:

import java.util.Stack;
    
    public class Test {
    	public static void main(String[] args) {
    		TreeNode[] node = new TreeNode[10];
    		for (int i = 0; i < 10; i++) {
    			node[i] = new TreeNode(i);
    		}
    		for (int i = 0; i < 10; i++) {
    			if (i * 2 + 1 < 10)
    				node[i].left = node[i * 2 + 1];
    			if (i * 2 + 2 < 10)
    				node[i].right = node[i * 2 + 2];
    		}
            //中序遍历
    		midOrderRe(node[0]);
    	}
    
    	public static void midOrderRe(TreeNode biTree) {
    		Stack<TreeNode> stack = new Stack<TreeNode>();
    		while (biTree != null || !stack.isEmpty()) {
    			while (biTree != null) {
    				stack.push(biTree);
    				biTree = biTree.left;
    			}
    			if (!stack.isEmpty()) {
    				biTree = stack.pop();
    				System.out.print(biTree.value+" ");
    				biTree = biTree.right;
    			}
    		}
    	}
    }
    
    //节点结构
    class TreeNode{
    	int value;
    	TreeNode left;
    	TreeNode right;
    	
    	TreeNode(int value){
    		this.value = value;
    	}
    }

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

## 三. 非递归后序遍历 ##

> 后序遍历（LRD）是 [二叉树遍历][Link 4]的一种，也叫做 [后根遍历][Link 6]、后序周游，可记做左右根。后序遍历有 [递归算法][Link 7]和非递归算法两种。在二叉树中，先左后右再根。巧记：左右根。  
> 后序遍历首先遍历左子树，然后遍历右子树，最后访问根结点，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后遍历根结点。即：  
> 若 [二叉树][Link 3]为空则结束返回，否则：  
> （1）后序遍历左子树  
> （2）后序遍历右子树  
> （3）访问根结点

如图所示

![ab51fc2080c821caafbe87e917a632eb.png][]

> 后序遍历结果：DEBFCA

**算法核心思想：**

> 首先要搞清楚先序、中序、后序的非递归算法共同之处：用栈来保存先前走过的路径，以便可以在访问完子树后,可以利用栈中的信息,回退到当前节点的双亲节点,进行下一步操作。
> 
> 后序遍历的非递归算法是三种顺序中最复杂的，原因在于，后序遍历是先访问左、右子树,再访问根节点，而在非递归算法中，利用栈回退到时，并不知道是从左子树回退到根节点，还是从右子树回退到根节点，如果从左子树回退到根节点，此时就应该去访问右子树，而如果从右子树回退到根节点，此时就应该访问根节点。所以相比前序和后序，必须得在压栈时添加信息，以便在退栈时可以知道是从左子树返回，还是从右子树返回进而决定下一步的操作。

实现代码:

import java.util.Stack;
    
    public class Test {
    	public static void main(String[] args) {
    		TreeNode[] node = new TreeNode[10];// 以数组形式生成一棵完全二叉树
    		for (int i = 0; i < 10; i++) {
    			node[i] = new TreeNode(i);
    		}
    		for (int i = 0; i < 10; i++) {
    			if (i * 2 + 1 < 10)
    				node[i].left = node[i * 2 + 1];
    			if (i * 2 + 2 < 10)
    				node[i].right = node[i * 2 + 2];
    		}
    		// 后序遍历非递归实现
    		postOrderRe(node[0]);
    	}
    
    	public static void postOrderRe(TreeNode biTree) {
    		int leftFlag = 1;// 在辅助栈里表示左节点
    		int rightFlag = 2;// 在辅助栈里表示右节点
    		Stack<TreeNode> stack = new Stack<TreeNode>();
    		// 辅助栈，用来判断子节点返回父节点时处于左节点还是右节点。
    		Stack<Integer> stackHelp = new Stack<Integer>();
    		while (biTree != null || !stack.empty()) {
    			while (biTree != null) {
    				// 将节点压入栈1，并在栈2将节点标记为左节点
    				stack.push(biTree);
    				stackHelp.push(leftFlag);
    				biTree = biTree.left;
    			}
    			while (!stack.empty() && stackHelp.peek() == rightFlag) {
    				// 如果是从右子节点返回父节点，则任务完成，将两个栈的栈顶弹出
    				stackHelp.pop();
    				System.out.print(stack.pop().value + " ");
    			}
    			if (!stack.empty() && stackHelp.peek() == leftFlag) {
    				// 如果是从左子节点返回父节点，则将标记改为右子节点
    				stackHelp.pop();
    				stackHelp.push(rightFlag);
    				biTree = stack.peek().right;
    			}
    		}
    	}
    }
    
    //节点结构
    class TreeNode {
    	int value;
    	TreeNode left;
    	TreeNode right;
    
    	TreeNode(int value) {
    		this.value = value;
    	}
    }

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

## 四. 数据结构专栏 ##

[https://blog.csdn.net/weixin\_53919192/category\_11908333.html?spm=1001.2014.3001.5482![icon-default.png?t=M666][icon-default.png_t_M666]https://blog.csdn.net/weixin\_53919192/category\_11908333.html?spm=1001.2014.3001.5482][https_blog.csdn.net_weixin_53919192_category_11908333.html_spm_1001.2014.3001.5482_icon-default.png_t_M666_icon-default.png_t_M666_https_blog.csdn.net_weixin_53919192_category_11908333.html_spm_1001.2014.3001.5482]

[Link 1]: https://blog.csdn.net/weixin_53919192/article/details/125712373?csdn_share_tail=%7B%22type%22%3A%22blog%22%2C%22rType%22%3A%22article%22%2C%22rId%22%3A%22125712373%22%2C%22source%22%3A%22weixin_53919192%22%7D&ctrtid=U91BW
[Link 2]: https://baike.baidu.com/item/%E6%A0%B9%E7%BB%93%E7%82%B9
[Link 3]: https://baike.baidu.com/item/%E4%BA%8C%E5%8F%89%E6%A0%91
[f236a4c547720b133f7da2d4ea92f8a5.png]: https://img-blog.csdnimg.cn/img_convert/f236a4c547720b133f7da2d4ea92f8a5.png
[73f0aabb6f9fc4cacb4f492e43e124c0.png]: https://img-blog.csdnimg.cn/img_convert/73f0aabb6f9fc4cacb4f492e43e124c0.png
[1d4fa418bf3a778595faaecc1625b506.png]: https://img-blog.csdnimg.cn/img_convert/1d4fa418bf3a778595faaecc1625b506.png
[92ef5684fa738ded08b536aaf7c298df.png]: https://img-blog.csdnimg.cn/img_convert/92ef5684fa738ded08b536aaf7c298df.png
[3a9773627189c702b29f9cc39ab7e763.png]: https://img-blog.csdnimg.cn/img_convert/3a9773627189c702b29f9cc39ab7e763.png
[da5cf4a1285f0ef86bd0398294ab6101.png]: https://img-blog.csdnimg.cn/img_convert/da5cf4a1285f0ef86bd0398294ab6101.png
[92866c3d469737aaed5d3d4d25b82f8f.png]: https://img-blog.csdnimg.cn/img_convert/92866c3d469737aaed5d3d4d25b82f8f.png
[29e6ac554fe0f4e2f394a09431e0bc8f.png]: https://img-blog.csdnimg.cn/img_convert/29e6ac554fe0f4e2f394a09431e0bc8f.png
[Link 4]: https://baike.baidu.com/item/%E4%BA%8C%E5%8F%89%E6%A0%91%E9%81%8D%E5%8E%86
[Link 5]: https://baike.baidu.com/item/%E4%B8%AD%E6%A0%B9%E9%81%8D%E5%8E%86
[d9b0355d1063ac78bd70b0b672c2248c.png]: https://img-blog.csdnimg.cn/img_convert/d9b0355d1063ac78bd70b0b672c2248c.png
[Link 6]: https://baike.baidu.com/item/%E5%90%8E%E6%A0%B9%E9%81%8D%E5%8E%86
[Link 7]: https://baike.baidu.com/item/%E9%80%92%E5%BD%92%E7%AE%97%E6%B3%95
[ab51fc2080c821caafbe87e917a632eb.png]: https://img-blog.csdnimg.cn/img_convert/ab51fc2080c821caafbe87e917a632eb.png
[icon-default.png_t_M666]: https://csdnimg.cn/release/blog_editor_html/release2.1.7/ckeditor/plugins/CsdnLink/icons/icon-default.png?t=M666
[https_blog.csdn.net_weixin_53919192_category_11908333.html_spm_1001.2014.3001.5482_icon-default.png_t_M666_icon-default.png_t_M666_https_blog.csdn.net_weixin_53919192_category_11908333.html_spm_1001.2014.3001.5482]: https://blog.csdn.net/weixin_53919192/category_11908333.html?spm=1001.2014.3001.5482