「算法」树和图的遍历

树

class TreeNode {    int val;    // 左子树    TreeNode left;    // 右子树    TreeNode right;    // 构造方法    TreeNode(int x) {        val = x;    }}

先序遍历

递归先序遍历：

// 递归先序遍历void recursionPreOrderTraversal(TreeNode root) {    if (root != null) {        // 先序        System.out.print(root.val + " ");        recursionPreOrderTraversal(root.left);        recursionPreOrderTraversal(root.right);    }}

在遍历完节点的左子树后接着遍历节点的右子树，为了能找到该节点，须要应用栈来进行暂存。

非递归先序遍历：

// 非递归先序遍历void preOrderTraversal(TreeNode root) {    // 该栈用于暂存节点    Stack<TreeNode> treeNodeStack = new Stack<TreeNode>();    // 游标    TreeNode node = root;    // 最初一个节点时，左右子树为空，并且栈也为空    while (node != null || !treeNodeStack.isEmpty()) {        while (node != null) {            // 先序拜访            System.out.print(node.val + " ");            treeNodeStack.push(node);            node = node.left;        }        // 此时左子树为空，思考右子树        // 如果栈已空，无需思考        if (!treeNodeStack.isEmpty()) {            // 弹出栈顶元素            node = treeNodeStack.pop();            node = node.right;        }    }}

中序遍历

递归中序遍历：

// 递归中序遍历void recursionInOrderTraversal(TreeNode root) {    if (root != null) {        recursionInOrderTraversal(root.left);        // 中序        System.out.print(root.val + " ");        recursionInOrderTraversal(root.right);    }}

在遍历完节点的左子树后接着遍历节点的右子树，为了能找到该节点，须要应用栈来进行暂存。

非递归中序遍历：

// 非递归中序遍历void inOrderTraversal(TreeNode root) {    // 该栈用于暂存节点    Stack<TreeNode> treeNodeStack = new Stack<TreeNode>();    // 游标    TreeNode node = root;    // 最初一个节点时，左右子树为空，并且栈也为空    while (node != null || !treeNodeStack.isEmpty()) {        while (node != null) {            treeNodeStack.push(node);            node = node.left;        }        // 此时左子树为空，思考右子树        // 如果栈已空，无需思考        if (!treeNodeStack.isEmpty()) {            // 弹出栈顶元素            node = treeNodeStack.pop();            // 中序拜访            System.out.print(node.val + " ");            node = node.right;        }    }}

后序遍历

递归后序遍历

// 递归后序遍历void recursionPostOrderTraversal(TreeNode root) {    if (root != null) {        recursionPostOrderTraversal(root.left);        recursionPostOrderTraversal(root.right);        // 后序        System.out.print(root.val + " ");    }}

非递归后序遍历：

// 非递归后序遍历void postOrderTraversal(TreeNode root) {    // 该栈用于暂存节点    Stack<TreeNode> treeNodeStack = new Stack<TreeNode>();    // 游标    TreeNode node = root;    // 保留最初拜访节点    TreeNode lastVisit = root;    // 最初一个节点时，左右子树为空，并且栈也为空    while (node != null || !treeNodeStack.isEmpty()) {        while (node != null) {            treeNodeStack.push(node);            node = node.left;        }        // 查看以后栈顶元素        node = treeNodeStack.peek();        // 如果其右子树也为空，或者右子树曾经拜访        // 则能够间接输入以后节点的值        if (node.right == null || node.right == lastVisit) {            // 后序拜访            System.out.print(node.val + " ");            treeNodeStack.pop();            lastVisit = node;            node = null;        } else {            //否则，持续遍历右子树            node = node.right;        }    }}

图

参考

https://www.jianshu.com/p/456...
https://zhuanlan.zhihu.com/p/...
https://segmentfault.com/a/11...