「算法」树和图的遍历

树

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…