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

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

---

目录

一. 非递归前序遍历

二. 非递归中序遍历

三. 非递归后序遍历

四. 数据结构专栏

---

一. 非递归前序遍历

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

如图所示:

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

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

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

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

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

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

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

代码如下：

//前序遍历的非递归实现
 
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）是 二叉树遍历的一种，也叫做 中根遍历、中序周游。在二叉树中，先左后根再右。巧记：左根右。
中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树
若 二叉树为空则结束返回，
否则：
（1）中序遍历左子树
（2）访问根结点
（3）中序遍历右子树

如图所示：

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

如图所示

后序遍历结果：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.5482https://blog.csdn.net/weixin_53919192/category_11908333.html?spm=1001.2014.3001.5482