Java树形结构查询用法介绍

我会带着你远行 2024-02-26 05:40 39阅读 0赞

在Java中，树形结构查询主要是通过特定的数据结构和相关算法来实现对特定的树形结构数据的查询操作，从而获取树中的某个或者某些节点的信息。

### 一、常用的树形数据结构 ###

在Java中，常用的树形结构包括二叉树、平衡二叉树、红黑树、B树、B+树等。

这里以二叉树为例，定义一个简单的二叉树节点。

public class TreeNode {
            int val;
            TreeNode left;
            TreeNode right;
            TreeNode(int x) { val = x; }
        }

### 二、树形查询算法 ###

常用的树形结构查询算法包括深度优先搜索（DFS）和广度优先搜索（BFS）。

以下是一个底层使用递归实现的深度优先搜索的Java代码实例：

public boolean DFS(TreeNode root, int target) {
            if (root == null) return false;
            if (root.val == target) return true;
            return DFS(root.left, target) || DFS(root.right, target);
        }

以下是一个底层使用队列实现的广度优先搜索的Java代码实例：

public boolean BFS(TreeNode root, int target) {
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            while (!queue.isEmpty()) {
                TreeNode node = queue.poll();
                if (node.val == target) return true;
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            return false;
        }

### 三、构造查询树 ###

在实际开发中，我们通常需要构造查询树来实现特定的查询需求。

下面是一个基于ArrayList实现的二叉树的构造方法：

public TreeNode constructTree(ArrayList<Integer> nums) {
            if (nums == null || nums.size() == 0) return null;
            TreeNode root = new TreeNode(nums.get(0));
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            for (int i = 1; i < nums.size(); i += 2) {
                TreeNode node = queue.poll();
                node.left = nums.get(i) != null ? new TreeNode(nums.get(i)) : null;
                if (i + 1 < nums.size()) {
                    node.right = nums.get(i + 1) != null ? new TreeNode(nums.get(i + 1)) : null;
                }
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            return root;
        }