亲宝软件园·资讯

展开

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

lillcol 人气:0
本文实现了二叉树的深度遍历算法,分为递归与非递归 递归的实现非常简单,基本上没啥难度 非递归的实现需要根据遍历的顺序,将递归转换成循环 代码中的二叉树如下 ![遍历.png](https://upload-images.jianshu.io/upload_images/6264117-62ec04e77355d882.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240) --- ### 递归 递归的实现很简单,此处不做过多赘述 ``` 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. 此处的先序遍历不是从左到右的先序遍历,是从右到做的先序遍历,具体如下图 ![原理.png](https://upload-images.jianshu.io/upload_images/6264117-618d6b9f001663e7.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240) 下面对比观察一下结果: ![对比.png](https://upload-images.jianshu.io/upload_images/6264117-0321f2b7b4d52958.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240) ``` 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

加载全部内容

相关教程
猜你喜欢
用户评论