二叉树的遍历实现递归与非递归

本文实现了二叉树的深度遍历算法，分为递归与非递归 递归的实现非常简单，基本上没啥难度 非递归的实现需要根据遍历的顺序，将递归转换成循环 代码中的二叉树如下  --- ### 递归 递归的实现很简单，此处不做过多赘述 ``` package cn.lillcol.agst.test; /** * 定义 结点数据结构 */ public class Node { // 数据域 String data = "null"; // 左孩子 Node leftChild; // 右孩子 Node rightChild; // 是否被访问 boolean isVisit = false; public void setIsVisit(boolean isVisit) { this.isVisit = isVisit; } public boolean getisVisit() { return this.isVisit; } public Node(String data) { this.data = data; } public void setData(String data) { this.data = data; } public void setLeftChild(Node leftChild) { this.leftChild = leftChild; } public void setRightChild(Node rightChild) { this.rightChild = rightChild; } @Override public String toString() { return this.data; } } ``` --- ``` package cn.lillcol.agst.test; /** * 二叉树遍历案例递归版本 * * @author lillcol * @date 2020-01-16 23：56：51 */ public class BTreeTestRecursion { public static void main(String[] args) { BTreeTestRecursion bTreeTestRecursion = new BTreeTestRecursion(); Node bTree = bTreeTestRecursion.createBTree(); System.out.print("前序遍历："); bTreeTestRecursion.preOrderTraverse(bTree); System.out.print("\n中序遍历："); bTreeTestRecursion.inOrderTraverse(bTree); System.out.print("\n后序遍历："); bTreeTestRecursion.postOrderTraverse(bTree); } /** * 生成一棵树 * * @return */ public Node createBTree() { Node A = new Node("A"); Node B = new Node("B"); Node C = new Node("C"); Node D = new Node("D"); Node E = new Node("E"); Node F = new Node("F"); Node G = new Node("G"); Node H = new Node("H"); Node I = new Node("I"); A.setLeftChild(B); A.setRightChild(C); B.setLeftChild(D); C.setLeftChild(E); C.setRightChild(F); D.setLeftChild(G); D.setRightChild(H); E.setRightChild(I); return A; } /** * 前序遍历递归版本 * * @param t */ public void preOrderTraverse(Node t) { if (t == null) return; System.out.print(t.data + "->"); preOrderTraverse(t.leftChild); preOrderTraverse(t.rightChild); } /** * 中序遍历 递归版本 * * @param t */ public void inOrderTraverse(Node t) { if (t == null) return; inOrderTraverse(t.leftChild); System.out.print(t.data + "->"); inOrderTraverse(t.rightChild); } /** * 后续遍历 递归版本 * * @param t */ public void postOrderTraverse(Node t) { if (t == null) return; postOrderTraverse(t.leftChild); postOrderTraverse(t.rightChild); System.out.print(t.data + "->"); } } ``` --- ### 非递归 非递归的实现比起递归相对复杂些。 核心是利用栈的特性，记录访问过的结点或输出的结点 非递归的实现中，先序遍历、中序遍历是比较简单的，只要按照便利的顺序结合代码的注释基本就可以理解了。 比较难的后续遍历，在实现的过程中发现，如果要按照访问顺序来进行实现，很复杂。 有些实现方式是通过增加一个标志位标记该借点是否访问过，但是却有问题：比如需要考虑很多子树的情况，判断情况特别多，只要少一个情况就会出错。 后面查看资料还有一个实现的方式相对简单很多，实现如下： 后序遍历可以看作逆先序遍历，此处有两个关键： 1. 结果是先序遍历的逆序 2. 此处的先序遍历不是从左到右的先序遍历，是从右到做的先序遍历，具体如下图  下面对比观察一下结果：  ``` package cn.lillcol.agst.test; import java.util.Stack; /*** * 二叉树层次遍历的非递归实现版本 * @author lillcol 20200308 */ public class BTreeTestNotRecursion { public static void main(String[] args) throws InterruptedException { BTreeTestNotRecursion bTreeTestNotRecursion = new BTreeTestNotRecursion(); Node bTree = bTreeTestNotRecursion.createBTree(); bTreeTestNotRecursion.inOrderTraverse(bTree); bTreeTestNotRecursion.preOrderTraverse(bTree); bTreeTestNotRecursion.postOrderTraverse(bTree); } /** * 前序遍历 非递归版本 * * @param t */ public void preOrderTraverse(Node t) { if (t == null) return; Stack