时间戳

首页 > 技术文章 > 二叉树的遍历实现递归与非递归

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

lillcol 2020-03-09 11:24 原文

本文实现了二叉树的深度遍历算法，分为递归与非递归

递归的实现非常简单，基本上没啥难度

非递归的实现需要根据遍历的顺序，将递归转换成循环

代码中的二叉树如下
遍历.png

递归

递归的实现很简单，此处不做过多赘述

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

下面对比观察一下结果：
对比.png

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;
    }
}

本文为原创文章，转载请注明出处！！！

推荐阅读