Java树表查找

树表查找通常指的是利用树形数据结构进行查找操作，其中最著名的树表结构是二叉查找树（也称为二叉搜索树、BST）。在BST中，每个节点都包含一个键（key）和相应的值（value），并且树的每个节点都遵循以下性质：左子树上的所有键都小于或等于当前节点的键，右子树上的所有键都大于当前节点的键。

树表查找的工作原理：

1. 开始查找：从根节点开始。
2. 比较键值：将目标值与当前节点的键进行比较。
3. 选择子树：如果目标值小于当前节点的键，则在左子树中继续查找；如果目标值大于当前节点的键，则在右子树中继续查找；如果相等，则查找成功。
4. 递归或迭代：重复步骤2和3，直到找到目标值或遍历到叶节点。

树表查找的Java实现：

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

public class BinaryTreeSearch {
    public TreeNode searchBST(TreeNode root, int key) {
        if (root == null || root.val == key) return root;
        if (key < root.val) return searchBST(root.left, key);
        return searchBST(root.right, key);
    }

    public static void main(String[] args) {
        BinaryTreeSearch bst = new BinaryTreeSearch();
        TreeNode root = new TreeNode(8);
        root.left = new TreeNode(3);
        root.right = new TreeNode(10);
        root.left.left = new TreeNode(1);
        root.left.right = new TreeNode(6);
        root.right.right = new TreeNode(14);

        int keyToSearch = 10;
        TreeNode result = bst.searchBST(root, keyToSearch);
        if (result != null) {
            System.out.println("Key " + keyToSearch + " found in the BST.");
        } else {
            System.out.println("Key " + keyToSearch + " not found in the BST.");
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

面试大厂题示例：

1. 实现BST的查找功能：
   描述：给定一个BST的根节点，实现一个方法来查找任意一个键是否存在于BST中。

2. BST的插入操作：
   描述：给定一个BST的根节点和一个要插入的键，实现一个方法来将这个键插入BST，并保持BST的性质。

3. 找到BST中的第k小的元素：
   描述：给定一个BST的根节点和一个整数k，实现一个方法来找出BST中的第k小的元素。

4. 检查平衡性：
   描述：给定一个BST的根节点，判断该BST是否是平衡的。（一个BST是平衡的，如果所有节点的左子树和右子树的高度差不超过1）

5. 删除操作：
   描述：给定一个BST的根节点和一个要删除的键，实现一个方法来删除BST中的键，并保持BST的性质。

源码实现 - BST的删除操作：

public class DeleteOperationInBST {
    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) return root;
        
        if (key < root.val) {
            root.left = deleteNode(root.left, key);
        } else if (key > root.val) {
            root.right = deleteNode(root.right, key);
        } else {
            if (root.left == null) {
                return root.right;
            } else if (root.right == null) {
                return root.left;
            }
            
            TreeNode temp = root.right;
            while (temp.left != null) {
                temp = temp.left;
            }
            root.val = temp.val;
            root.right = deleteNode(root.right, temp.val);
        }
        return root;
    }

    // TreeNode 类和其他辅助方法与上题相同
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

在面试中，树表查找和BST操作是常见的算法问题，它们考察应聘者对树数据结构的理解和算法实现能力。希望这些示例能够帮助你更好地准备面试！树表查找通常与二叉搜索树（BST）相关，这是一种特殊的二叉树，其中每个节点的左子树上的节点键值都小于它，右子树上的节点键值都大于或等于它。以下是三道可能出现在大厂面试中的与BST相关的编程题目，以及相应的Java源码实现。

题目 1：实现BST的查找功能

描述：
给定一个BST的根节点和一个值，判断BST中是否存在该值。

示例：

输入：root = [2,1,3], val = 3
输出：true
1
2

Java 源码：

public class SearchBST {
    public boolean searchBST(TreeNode root, int val) {
        if (root == null) {
            return false;
        }
        if (root.val == val) {
            return true;
        }
        return val < root.val ? searchBST(root.left, val) : searchBST(root.right, val);
    }

    public static void main(String[] args) {
        SearchBST solution = new SearchBST();
        TreeNode root = new TreeNode(2);
        root.left = new TreeNode(1);
        root.right = new TreeNode(3);
        boolean result = solution.searchBST(root, 3);
        System.out.println("Does the BST contain the value 3? " + result);
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

题目 2：BST的插入操作

描述：
给定一个BST的根节点和一个值，将该值插入BST中，并返回BST的根节点。

示例：

输入：root = [4,2,7,1,3], val = 5
输出：[4,2,7,1,3,5]（BST的中序遍历）
1
2

Java 源码：

public class InsertIntoBST {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null) {
            return new TreeNode(val);
        }
        if (val < root.val) {
            root.left = insertIntoBST(root.left, val);
        } else {
            root.right = insertIntoBST(root.right, val);
        }
        return root;
    }

    public static void main(String[] args) {
        InsertIntoBST solution = new InsertIntoBST();
        TreeNode root = new TreeNode(4);
        root.left = new TreeNode(2);
        root.right = new TreeNode(7);
        root.left.left = new TreeNode(1);
        root.left.right = new TreeNode(3);
        root = solution.insertIntoBST(root, 5);
        // 中序遍历BST并输出结果
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

题目 3：BST的删除操作

描述：
给定一个BST的根节点和一个值，删除BST中的该值，并返回BST的根节点。

示例：

输入：root = [4,2,7,1,3], val = 3
输出：[4,2,7,1]（BST的中序遍历）
1
2

Java 源码：

public class DeleteFromBST {
    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) {
            return null;
        }
        if (key < root.val) {
            root.left = deleteNode(root.left, key);
        } else if (key > root.val) {
            root.right = deleteNode(root.right, key);
        } else {
            if (root.left == null) {
                return root.right;
            } else if (root.right == null) {
                return root.left;
            }
            TreeNode temp = root.right;
            while (temp.left != null) {
                temp = temp.left;
            }
            root.val = temp.val;
            root.right = deleteNode(root.right, temp.val);
        }
        return root;
    }

    public static void main(String[] args) {
        DeleteFromBST solution = new DeleteFromBST();
        TreeNode root = new TreeNode(4);
        root.left = new TreeNode(2);
        root.right = new TreeNode(7);
        root.left.left = new TreeNode(1);
        root.left.right = new TreeNode(3);
        root = solution.deleteNode(root, 3);
        // 中序遍历BST并输出结果
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

这些题目和源码展示了BST在解决实际问题中的应用。在面试中，能够根据问题的特点选择合适的算法并实现其解决方案是非常重要的。希望这些示例能够帮助你更好地准备面试！