树的遍历

Author Avatar
ahscuml 11月 21, 2018
  • 在其它设备中阅读本文章

树的前序遍历，中序遍历，后序遍历以及层序遍历的java代码实现，每种都有递归和循环两种方法。
对于树结构的定义如下所示：

/**
* 树结构的定义
*/
public static class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

前序遍历

  1. 访问根结点。
  2. 前序遍历左子树。
  3. 前序遍历右子树

递归方法：

/**
* 前序遍历，递归方法
*/
public static void preorderRec(TreeNode root) {
    if (root != null) {
        System.out.print(root.val);
        preorderRec(root.left);
        preorderRec(root.right);
    }
}

迭代方法：

/**
* 前序遍历迭代方法
*/
public static void preorderIte(TreeNode root) {
    if (root != null) {
        // 用于存储遍历过的结点
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        // 当前节点与栈都不为空
        while (cur != null || !stack.isEmpty()) {
            // 如果当前节点不为空，输出值，压入栈，移动到左子树
            if (cur != null) {
                // 前序遍历根节点首先输出，所以输出在最前
                System.out.print(cur.val);
                // 将cur入栈是为了后面遍历右子树
                stack.push(cur);
                cur = cur.left;
            } else {
                // 如果当前元素为空，回退到父节点，再遍历右子树，然后父节点就可以出栈了，因为他的左右子树都遍历完成了
                cur = stack.pop();
                cur = cur.right;
            }
        }
    }
}

中序遍历

  1. 中序遍历左子树。
  2. 访问根结点。
  3. 中序遍历右子树

递归方法：

/**
* 中序遍历，循环
*/
private static void inOrderRec(TreeNode root) {
    if (root == null) {
        return;
    }
    inOrderRec(root.left);
    System.out.print(root.val);
    inOrderRec(root.right);
}

迭代方法：

/**
* 中序遍历，循环
*/
private static void inOrderIte(TreeNode root) {
    if (root == null) {
        return;
    }

    Stack<TreeNode> stack = new Stack<>();
    TreeNode cur = root;
    while (cur != null || !stack.isEmpty()) {
        if (cur != null) {
            stack.push(cur);
            // 先是左子树
            cur = cur.left;
        } else {
            // 到达叶子节点，弹出栈，输出，在遍历右子树
            cur = stack.pop();
            // 跟前序遍历相反，这个是出栈输出
            System.out.print(cur.val);
            cur = cur.right;
        }
    }
}

后序遍历

  1. 后序遍历左子树。
  2. 后序遍历右子树
  3. 访问根结点。

递归方法：

/**
* 后序遍历，递归
*/
private static void postOrderRec(TreeNode root) {
    if (root == null) {
        return;
    }
    postOrderRec(root.left);
    postOrderRec(root.right);
    System.out.print(root.val);
}

循环方法

/**
* 后序遍历，迭代
* 后序遍历的方法与前序遍历与中序遍历的方法不太相同
*/
private static void postOrderIte(TreeNode root) {
    if (root == null) {
        return;
    }
    Stack<TreeNode> stack = new Stack<>();
    // 新增加一个栈,利用栈先进后出的原则，先放入根节点，然后放入右节点，最后放入左节点
    Stack<TreeNode> output = new Stack<>();

    TreeNode cur = root;
    while (cur != null || !stack.isEmpty()) {
        if (cur != null) {
            output.push(cur);
            stack.push(cur);
            // 先进后出，所以先是右边
            cur = cur.right;
        } else {
            // output不出栈，stack只是为了帮助找到左子树
            cur = stack.pop();
            cur = cur.left;
        }
    }

    while (!output.isEmpty()) {
        System.out.print(output.pop().val);
    }
}

层序遍历

按照层的顺序来遍历

递归方法：

/**
* 层序遍历， 递归方法
* 首先层序遍历需要按照层来划分，也就是深度，
* 然后围绕深度输出
*/
public static void levelOrderRec(TreeNode root) {
    if (root == null) {
        return;
    }
    // 分层遍历
    for (int i = 1; i <= depthIte(root); i++) {
        levleOrder(root, i);
    }
}


/**
* 层序遍历辅助函数，每遍历一层level减1，直到level为1，输出这一层的元素值
*/
private static void levleOrder(TreeNode root, int level) {
    if (root == null || level < 1) {
        return;
    }
    // 这里的level不是指树的层，指还剩的层数
    if (level == 1) {
        System.out.print(root.val);
    }
    // 每向下遍历一层，层数就减1，直到层数为1，遍历的就是这一层，输出节点的值
    levleOrder(root.left, level - 1);
    levleOrder(root.right, level - 1);
}

/**
* 递归方法计算树深度
*/
private static int depthRec(TreeNode root) {
    if (root == null) {
        return 0;
    }

    int l = depthRec(root.left);
    int r = depthRec(root.right);

    if (l > r) {
        return l + 1;
    } else {
        return r + 1;
    }
}

循环方法

/**
* 层序遍历，非递归方法
* 利用队列这个先进先出的数据结构
* 入队的时候就是按照层的顺序入队，出队也 非常方便
* LinkedList类实现了Queue接口，因此我们可以把LinkedList当成Queue来用
*/
public static void levelOrderIte(TreeNode root) {
    if (root == null) {
        return;
    }

    TreeNode cur;
    // LinkedList类实现了Queue接口，因此我们可以把LinkedList当成Queue来用
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);

    // 每次都是当前节点出队，然后存入当前节点的左右子节点
    while (queue.size() != 0) {
        cur = queue.poll();
        System.out.print(cur.val);
        if (cur.left != null) {
            queue.offer(cur.left);
        }
        if (cur.right != null) {
            queue.offer(cur.right);
        }
    }
}

This blog is under a CC BY-NC-SA 4.0 Unported License
本文链接：https://ahscuml.github.io/树的遍历/

Powered by Hexo
Theme - Material