使用Java函数实现二叉树的遍历和查找操作。
发布时间:2023-06-09 02:22:59
1. 二叉树的遍历
前序遍历:
前序遍历的顺序是先访问根结点,再遍历左子树,最后遍历右子树。具体实现代码如下:
public void preOrder(TreeNode node) {
if (root != null) {
System.out.print(node.val + " "); //先输出根结点
preOrder(node.left); //遍历左子树
preOrder(node.right); //遍历右子树
}
}
中序遍历:
中序遍历的顺序是先遍历左子树,再访问根结点,最后遍历右子树。具体实现代码如下:
public void inOrder(TreeNode node) {
if (node != null) {
inOrder(node.left); //遍历左子树
System.out.print(node.val + " "); //输出根结点
inOrder(node.right); //遍历右子树
}
}
后序遍历:
后序遍历的顺序是先遍历左子树,再遍历右子树,最后访问根结点。具体实现代码如下:
public void postOrder(TreeNode node) {
if (node != null) {
postOrder(node.left); //遍历左子树
postOrder(node.right); //遍历右子树
System.out.print(node.val + " "); //输出根结点
}
}
2. 二叉树的查找
查找操作常用的有深度优先查找和广度优先查找。
深度优先查找:
深度优先查找一般使用递归实现,它的思路是先查找根结点,然后再依次往下查找左子树和右子树。具体实现代码如下:
public TreeNode dfs(TreeNode node, int val) {
if (node == null) {
return null;
}
if (node.val == val) {
return node;
}
TreeNode leftNode = dfs(node.left, val); //查找左子树
if (leftNode != null) {
return leftNode;
}
TreeNode rightNode = dfs(node.right, val); //查找右子树
if (rightNode != null) {
return rightNode;
}
return null;
}
广度优先查找:
广度优先查找是一层一层的进行查找,常使用队列来实现。具体实现代码如下:
public TreeNode bfs(TreeNode node, int val) {
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(node);
while (!queue.isEmpty()) {
TreeNode curr = queue.poll(); //取出队头结点
if (curr.val == val) {
return curr;
}
if (curr.left != null) {
queue.offer(curr.left); //将左结点加入队列
}
if (curr.right != null) {
queue.offer(curr.right); //将右结点加入队列
}
}
return null; //未找到
}
综上所述,对于二叉树的遍历和查找操作,在Java中都可以使用递归和队列实现。其中,前序遍历、中序遍历、后序遍历的实现可参考本文,而深度优先查找和广度优先查找的实现可以根据具体情况选择。
