数据结构/树：深度优先遍历与Java实现

介绍

深度优先遍历从树的根节点开始，沿着树的深度访问节点，先访问根节点，然后递归地访问根节点的第一个子节点，再递归地访问该子节点的子节点，直到到达树的最深处。然后回溯到上一层节点，继续访问其他子节点。

具体步骤如下：

• 访问当前节点。

• 递归地对当前节点的每个子节点进行深度优先遍历。

Java实现

递归

先序遍历

以下是一个使用递归实现树的深度优先遍历（先序遍历）的Java代码示例：

class TreeNode {
    int value;
    TreeNode left;
    TreeNode right;

    public TreeNode(int value) {
        this.value = value;
        left = null;
        right = null;
    }
}

public class BinaryTreeTraversal {
    public static void depthFirstTraversal(TreeNode root) {
        if (root == null) {
            return;
        }

        System.out.print(root.value + " ");
        depthFirstTraversal(root.left);
        depthFirstTraversal(root.right);
    }

    public static void main(String[] args) {
        // 构建一个二叉树
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(7);

        System.out.println("深度优先遍历结果：");
        depthFirstTraversal(root);
    }
}

在上述代码中，我们定义了一个TreeNode类表示树的节点。depthFirstTraversal方法用于进行深度优先遍历（先序遍历），它接受一个树的根节点作为参数。首先，我们检查根节点是否为空，如果为空，则直接返回。然后，我们打印当前节点的值，然后递归地对左子树和右子树进行深度优先遍历。这样，我们就可以按照先序遍历的顺序遍历整棵树。

非递归

先序遍历

以下是一个使用非递归方式实现树的深度优先遍历（先序遍历）的Java代码示例：

import java.util.Stack;

class TreeNode {
    int value;
    TreeNode left;
    TreeNode right;

    public TreeNode(int value) {
        this.value = value;
        left = null;
        right = null;
    }
}

public class BinaryTreeTraversal {
    public static void depthFirstTraversal(TreeNode root) {
        if (root == null) {
            return;
        }

        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            System.out.print(node.value + " ");

            if (node.right != null) {
                stack.push(node.right);
            }

            if (node.left != null) {
                stack.push(node.left);
            }
        }
    }

    public static void main(String[] args) {
        // 构建一个二叉树
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(7);

        System.out.println("深度优先遍历结果：");
        depthFirstTraversal(root);
    }
}

在上述代码中，我们使用了一个栈来辅助进行深度优先遍历（先序遍历）。首先，我们将根节点放入栈中。然后，进入一个循环，直到栈为空。在循环中，我们弹出栈顶的节点，并打印它的值。然后，将该节点的右子节点（如果存在）先入栈，再将左子节点（如果存在）入栈。这样，我们就可以按照先序遍历的顺序遍历整棵树。

中序遍历

以下是一个使用非递归方式实现树的深度优先遍历（中序遍历）的Java代码示例：

import java.util.Stack;

class TreeNode {
    int value;
    TreeNode left;
    TreeNode right;

    public TreeNode(int value) {
        this.value = value;
        left = null;
        right = null;
    }
}

public class BinaryTreeTraversal {
    public static void depthFirstTraversal(TreeNode root) {
        if (root == null) {
            return;
        }

        Stack<TreeNode> stack = new Stack<>();
        TreeNode curr = root;

        while (curr != null || !stack.isEmpty()) {
            while (curr != null) {
                stack.push(curr);
                curr = curr.left;
            }

            curr = stack.pop();
            System.out.print(curr.value + " ");
            curr = curr.right;
        }
    }

    public static void main(String[] args) {
        // 构建一个二叉树
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(7);

        System.out.println("深度优先遍历结果：");
        depthFirstTraversal(root);
    }
}

在上述代码中，我们使用了一个栈来辅助进行深度优先遍历（中序遍历）。首先，我们将根节点放入栈中，并将当前节点初始化为根节点。然后，进入一个循环，条件是当前节点不为空或栈不为空。在循环中，我们先将当前节点的左子节点（如果存在）依次入栈，直到当前节点为空。然后，从栈中弹出一个节点，打印它的值，并将当前节点更新为该节点的右子节点。这个过程会一直重复，直到当前节点为空且栈为空。这样，我们就可以按照中序遍历的顺序遍历整棵树。

后序遍历

以下是一个使用非递归方式实现树的深度优先遍历（后序遍历）的Java代码示例：

import java.util.Stack;

class TreeNode {
    int value;
    TreeNode left;
    TreeNode right;

    public TreeNode(int value) {
        this.value = value;
        left = null;
        right = null;
    }
}

public class BinaryTreeTraversal {
    public static void depthFirstTraversal(TreeNode root) {
        if (root == null) {
            return;
        }

        Stack<TreeNode> stack = new Stack<>();
        Stack<TreeNode> output = new Stack<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            TreeNode curr = stack.pop();
            output.push(curr);

            if (curr.left != null) {
                stack.push(curr.left);
            }

            if (curr.right != null) {
                stack.push(curr.right);
            }
        }

        while (!output.isEmpty()) {
            TreeNode node = output.pop();
            System.out.print(node.value + " ");
        }
    }

    public static void main(String[] args) {
        // 构建一个二叉树
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(7);

        System.out.println("深度优先遍历结果：");
        depthFirstTraversal(root);
    }
}

在上述代码中，我们使用了两个栈来辅助进行深度优先遍历（后序遍历）。首先，我们将根节点放入栈1中。然后，进入一个循环，直到栈1为空。在循环中，我们从栈1中弹出一个节点，并将其压入栈2中。然后，将该节点的左子节点（如果存在）和右子节点（如果存在）依次入栈1。这样，我们可以保证栈2中的节点顺序为后序遍历的逆序。最后，我们将栈2中的节点依次弹出并打印，即可得到后序遍历的结果。这样，我们就可以按照后序遍历的顺序遍历整棵树。