在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; }