本文实现了二叉树的深度遍历算法, 分为递归与非递归
递归的实现非常简单, 基本上没啥难度
非递归的实现需要根据遍历的顺序, 将递归转换成循环
代码中的二叉树如下
递归
递归的实现很简单, 此处不做过多赘述
- 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;
- }
- }
来源: https://www.cnblogs.com/lillcol/p/12447478.html