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

2019/04/10 10:10
阅读数 30

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

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

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

代码中的二叉树如下
遍历.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;
    }
}

本文为原创文章,转载请注明出处!!!

原文出处:https://www.cnblogs.com/lillcol/p/12447478.html

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部