二叉树的遍历实现递归与非递归
- 2020 年 3 月 9 日
- 筆記
本文实现了二叉树的深度遍历算法，分为递归与非递归
递归的实现非常简单，基本上没啥难度
非递归的实现需要根据遍历的顺序，将递归转换成循环
代码中的二叉树如下
递归
递归的实现很简单，此处不做过多赘述
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 + "->"); } } 非递归
非递归的实现比起递归相对复杂些。
核心是利用栈的特性，记录访问过的结点或输出的结点
非递归的实现中，先序遍历、中序遍历是比较简单的，只要按照便利的顺序结合代码的注释基本就可以理解了。
比较难的后续遍历，在实现的过程中发现，如果要按照访问顺序来进行实现，很复杂。
有些实现方式是通过增加一个标志位标记该借点是否访问过，但是却有问题：比如需要考虑很多子树的情况，判断情况特别多，只要少一个情况就会出错。
后面查看资料还有一个实现的方式相对简单很多，实现如下：
后序遍历可以看作逆先序遍历，此处有两个关键：
- 结果是先序遍历的逆序
- 此处的先序遍历不是从左到右的先序遍历，是从右到做的先序遍历，具体如下图
下面对比观察一下结果：
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<Node> stack = new Stack<>(); // 此处出了t不为空，还需要栈也不为空，否则会停在第一次遍历到右节点的位置 while (t != null || !stack.empty()) { // 遍历到树的最左边节点 while (t != null) { stack.push(t);//记录遍历过的节点 System.out.print(t.data + "->");//先序遍历，首先输出父节点，所以此处需要输出 t = t.leftChild;//遍历父节点后，下一个遍历的节点为左节点 } if (!stack.empty()) { // 当遍历完左节点，需要遍历右节点 t = stack.pop().rightChild; } } } /** * 中序遍历 非递归版本 * * @param t */ public void inOrderTraverse(Node t) { if (t == null) return; Stack<Node> stack = new Stack<>(); //当前节点不为空，或栈中有元素 while (t != null || !stack.empty()) { //一直遍历左子树，直到某结点的左子树为null，说明到了最下边的左子树 while (t != null) { //将每一个便利的左子树入栈 stack.push(t); t = t.leftChild; } //当遍历到最下边的左子树，就需要开始出栈了 if (!stack.empty()) { //栈顶元素出栈 Node top = stack.pop(); System.out.print(top.toString() + "->"); //遍历因为是中序遍历，在输出一个结点后，接下来判断该结点的右子树，这和之前一样相当于是一新的树，重复之前的操作即可 t = top.rightChild; } } } /** * 后续遍历 非递归版本 * 核心：后续遍历就是 逆先序遍历 （先序遍历的顺序为父->右结点->左结点：和一般的刚好相反） * 所以代码实现需要两个栈，一个进行节点的先序遍历，另一个记录输出内容（因为是逆序，所以根据栈的特性，最后在遍历stack2即是最终的后续遍历结果） * * @param t */ public void postOrderTraverse(Node t) { if (t == null) return; Stack<Node> stack = new Stack<>(); Stack<Node> stack2 = new Stack<>(); while (t != null || !stack.empty()) { while (t != null) { stack.push(t);//记录已经访问结点 // System.out.print(t.data + "->");正常先序遍历该在此处输出 stack2.push(t);//记录本该输出的部分 t = t.rightChild; } if (!stack.empty()) { t = stack.pop().leftChild; } } // 输出stack2中的记录即为后续遍历结果 while (!stack2.empty()) { System.out.print(stack2.pop().data + "->"); } } /** * 生成一棵树 * * @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; } } 本文为原创文章，转载请注明出处！！！
