使用Java函数实现二叉树的深度优先遍历
二叉树是一种常见的数据结构，常用于组织和管理数据，例如计算机科学中的树形结构和关系型数据库中的数据结构。在二叉树中，每个节点最多有两个子节点，左侧子节点的值总是小于父节点的值，右侧子节点的值总是大于父节点的值。深度优先遍历是一种遍历二叉树节点的方法，它会先遍历左子树，再遍历右子树，最后遍历根节点。本文将介绍如何使用Java函数实现二叉树的深度优先遍历。
一、实现方法
1.1 定义节点类
首先需要创建二叉树的节点类，它包括三个属性：左子节点、右子节点和节点值。
public class TreeNode {
public TreeNode left;
public TreeNode right;
public int val;
public TreeNode(int val) {
this.val = val;
}
}
1.2 递归方式遍历
深度优先遍历可通过递归方式进行遍历。遍历过程如下：
- 如果当前节点不为空，则输出它的值；
- 如果当前节点有左子节点，则递归遍历左子节点；
- 如果当前节点有右子节点，则递归遍历右子节点。
public static void dfs(TreeNode root) {
if (root == null) {
return;
}
System.out.print(root.val + " ");
dfs(root.left);
dfs(root.right);
}
1.3 栈方式遍历
深度优先遍历可通过栈方式进行遍历。遍历过程如下：
- 创建一个栈，并将根节点压入栈中；
- 当栈不为空时，弹出栈顶节点，输出其值；
- 如果当前节点有右子节点，则将右子节点压入栈中；
- 如果当前节点有左子节点，则将左子节点压入栈中；
- 继续遍历栈中的下一个节点。
public static void dfs(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.val + " ");
if (node.right != null) {
stack.push(node.right);
}
if (node.left != null) {
stack.push(node.left);
}
}
}
1.4 递归方式遍历并打印层数
如果需要输出每个节点所在的层数，可以对递归方式进行改进，增加一个参数表示当前节点所在的层数。
public static void dfs(TreeNode root, int level) {
if (root == null) {
return;
}
for (int i = 0; i < level; i++) {
System.out.print("--");
}
System.out.print(root.val + " (" + level + ")");
System.out.println();
dfs(root.left, level + 1);
dfs(root.right, level + 1);
}
1.5 栈方式遍历并打印层数
栈方式也可以增加一个参数表示当前节点所在的层数。遍历过程如下：
- 创建一个栈，并将根节点和根节点层数压入栈中；
- 当栈不为空时，弹出栈顶元素，输出其值和层数；
- 如果当前元素有右子节点，则将右子节点和右子节点层数压入栈中；
- 如果当前元素有左子节点，则将左子节点和左子节点层数压入栈中；
- 继续遍历栈中的下一个元素。
public static void dfs(TreeNode root) {
if (root == null) {
return;
}
Stack<Pair<TreeNode, Integer>> stack = new Stack<>();
stack.push(new Pair<>(root, 0));
while (!stack.isEmpty()) {
Pair<TreeNode, Integer> pair = stack.pop();
TreeNode node = pair.getKey();
int level = pair.getValue();
for (int i = 0; i < level; i++) {
System.out.print("--");
}
System.out.print(node.val + " (" + level + ")");
System.out.println();
if (node.right != null) {
stack.push(new Pair<>(node.right, level + 1));
}
if (node.left != null) {
stack.push(new Pair<>(node.left, level + 1));
}
}
}
二、使用示例
以下为使用示例：
public static void main(String[] args) {
/**
* 输入：
* 1
* / \
* 2 3
* / \ \
* 4 5 6
* 输出：1 2 4 5 3 6
*/
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.right = new TreeNode(6);
dfs(root);
// 输出：1 2 4 (2)--5 (2)--3 6 (2)
dfs(root, 0);
}
输出为：
1 2 4 5 3 6 1 (0) --2 (1) ----4 (2) ----5 (2) --3 (1) ----6 (2)
三、总结
本文介绍了如何使用Java函数实现二叉树的深度优先遍历，包括递归方式和栈方式，以及如何输出每个节点所在的层数。深度优先遍历是一种基本的遍历二叉树的方法，熟练掌握该方法可以帮助我们更好的理解二叉树的基本性质和特点。