二叉树的遍历-递归和非递归

前言

最近准备面试 ,复习了一下数据结构 中的二叉树,整理了二叉树的前序、中序、后序、深度和广度遍历以及递归和非递归实现方法，如有好的方案大家可以一起讨论。

前序遍历

先遍历根节点，然后再遍历左子树，最后再遍历右子树

java 示例：

/**
 * 前序遍历
 */
public void previousTraverse() {
    if (Objects.nonNull(root)) {
        doPreviousTraverse(root);
    }
}


private void doPreviousTraverse(Node root) {
    //先遍历根节点
    System.out.println(root.getData());
    if (Objects.nonNull(root.getLeft())) {
        doPreviousTraverse(root.getLeft());
    }
    if (Objects.nonNull(root.getRight())) {
        doPreviousTraverse(root.getRight());
    }
}

中序遍历

思路：先遍历左子树，然后遍历根节点，最后遍历右子树

java 示例

/**
 * 中序遍历
 */
public void middleTraverse() {
    if (Objects.nonNull(root)) {
        doMiddleTraverse(root);
    }
}

private void doMiddleTraverse(Node root) {
    //先遍历左节点
    if (Objects.nonNull(root.getLeft())) {
        doMiddleTraverse(root.getLeft());
    }
    //遍历根节点
    System.out.println(root.getData());
    //遍历右节点
    if (Objects.nonNull(root.getRight())) {
        doMiddleTraverse(root.getRight());
    }
}

后序遍历

思路：先遍历左子树，然后遍历右子树，再遍历根节点

java示例

/**
 * 后序遍历
 */
public void afterTraverse() {
    if (Objects.nonNull(root)) {
        doAfterTraverse(root);
    }
}

private void doAfterTraverse(Node root) {
    //先遍历左节点
    if (Objects.nonNull(root.getLeft())) {
        doAfterTraverse(root.getLeft());
    }
    // 遍历右节点
    if (Objects.nonNull(root.getRight())) {
        doAfterTraverse(root.getRight());
    }
    //遍历根节点
    System.out.println(root.getData());
}

广度遍历

思路：使用队列来辅助实现，首先把根节点放到队列里，然后弹出 根节点 打印根节  点的値，判断左子节点是否为空，不为空放入队列，判断右节点是否为空，不为空     放入队列，一次重复上述步骤，找到队列里没有数据结束，打印出来的序列则为该   树的广度遍历。

java 示例：

/**
 * 广度遍历
 */
public void broadCastTraverse() {
    if (Objects.nonNull(root)) {
        //定义一个存放节点的队列
        LinkedList<Node> nodes = new LinkedList<>();
        nodes.addLast(root);
        while (!nodes.isEmpty()) {
            Node node = nodes.removeFirst();
            System.out.println(node.getData());
            if (Objects.nonNull(node.getLeft())) {
                nodes.addLast(node.getLeft());
            }
            if (Objects.nonNull(node.getRight())) {
                nodes.addLast(node.getRight());
            }
        }
    }
}

深度遍历 即先序遍历 若不采用递归方式则序借助栈的后进先出

   先将根节点事先放到栈中然后执行下面的步骤:
   1.从栈顶弹出节点
   2.打印节点的値
   3.判断该节点的右子节点是否为空，若不为空则将右子节点放入栈中
   4.判断该节点的左子节点是否为空，若不为空则将左子节点放入栈中
   重复上述步骤，直到栈为空

java 示例

/**
 * 深度遍历 即先序遍历 若不采用递归方式则序借助栈的后进先出
 * 先将根节点事先放到栈中然后执行下面的步骤:
 * 1.从栈顶弹出节点
 * 2.打印节点的値
 * 3.判断该节点的右子节点是否为空，若不为空则将右子节点放入栈中
 * 4.判断该节点的左子节点是否为空，若不为空则将左子节点放入栈中
 * 重复上述步骤，直到栈为空
 */
public void deepTraverse() {
    if (Objects.nonNull(root)) {
        Stack<Node> nodes = new Stack<>();
        nodes.push(root);
        while (!nodes.isEmpty()) {
            Node node = nodes.pop();
            System.out.println(node.getData());
            if (Objects.nonNull(node.getRight())) {
                nodes.push(node.getRight());
            }
            if (Objects.nonNull(node.getLeft())) {
                nodes.push(node.getLeft());
            }
        }
    }
}

中序遍历 非递归遍历 借用栈来实现

思路：
1.首先将根节点 入栈
2.依次将左节点入栈直到左节点为空
3.弹出栈顶打印判断是否有右节点，若有则入栈  

java 示例

/**
 * Non-recursive traversal
 *
 * 中序遍历 非递归遍历 借用栈来实现
 * 思路：
 * 1.首先将根节点 入栈
 * 2.依次将左节点入栈直到左节点为空
 * 3.弹出栈顶打印判断是否有右节点，若有则入栈
 */
public void nonRecursiveTraverse() {
    if (Objects.nonNull(root)) {
        Node node = root;
        Stack<Node> nodes = new Stack<>();
        while (Objects.nonNull(node) || !nodes.isEmpty()) {
            if (Objects.nonNull(node)) {
                //将根节点入栈
                nodes.push(node);
                node = node.getLeft();
            } else {
                Node someLeft = nodes.pop();
                System.out.println(someLeft.getData());
                if (Objects.nonNull(someLeft.getRight())) {
                    node = someLeft.getRight();
                }
            }

        }
    }
}

完整源码位置
https://github.com/241600489/homeworks/tree/master/src/main/java/zym/sort/tree/binary

后记

看完之后如果觉得有用麻烦点个赞加个关注哦

参考
https://blog.csdn.net/qq_38875300/article/details/89299647