欢迎访问宙启技术站
智能推送

使用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中都可以使用递归和队列实现。其中,前序遍历、中序遍历、后序遍历的实现可参考本文,而深度优先查找和广度优先查找的实现可以根据具体情况选择。