Java中如何实现二叉搜索树整树及指定节点子树的大小获取

核心原理拆解 #

你现有的private int size(Node node)方法本身就是计算子树大小的核心逻辑——它的作用就是计算以传入的node为根节点的子树的总节点数：

• 当node为null时，子树为空，返回0；
• 当node存在时，子树大小 = 左子树大小 + 1（当前节点本身） + 右子树大小，通过递归遍历左右子树完成计算。

你之前调用size(root)得到整树大小，本质就是把整棵树看作以root为根的子树。要计算指定节点的子树大小，只需要把这个指定节点作为参数传入这个私有方法即可。

实现步骤 #

要完成需求，只需要两步：

1. 找到指定的目标节点：利用二叉搜索树的特性（左子树节点值<根节点值<右子树节点值），通过二分查找快速定位目标值对应的节点；
2. 调用现有递归方法计算子树大小：将找到的节点传入size(Node node)，得到结果。

完整代码实现 #

结合你现有的代码，补充以下内容：

1. 查找指定值对应的节点（私有辅助方法） #

private Node findNode(Node current, int targetValue) {
    if (current == null) {
        return null; // 目标值不存在
    }
    if (targetValue == current.value) {
        return current; // 找到目标节点
    } else if (targetValue < current.value) {
        return findNode(current.left, targetValue); // 去左子树查找
    } else {
        return findNode(current.right, targetValue); // 去右子树查找
    }
}

2. 对外提供的子树大小公共方法 #

public int getSubtreeSize(int targetValue) {
    Node targetNode = findNode(root, targetValue);
    if (targetNode == null) {
        System.out.println("Target node with value " + targetValue + " does not exist in the tree.");
        return -1; // 返回-1表示节点不存在，也可以根据需求抛出异常
    }
    int subtreeSize = size(targetNode);
    System.out.println("Size of subtree rooted at node with value " + targetValue + " is: " + subtreeSize);
    return subtreeSize;
}

整合后的完整代码片段 #

// 假设你的Node类定义如下（补充完整上下文）
class Node {
    int value;
    Node left;
    Node right;

    Node(int value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

class BinarySearchTree {
    private Node root;

    // 你原有的size方法
    private int size(Node node) {
        Node n = node;
        if (n == null) {
            return 0;
        } else {
            int leftside = size(n.left);
            int rightside = size(n.right);
            return leftside + 1 + rightside;
        }
    }

    // 你原有的整树大小方法
    public int size() {
        int sizeOfTree = size(root);
        System.out.println("Size of the binary tree is: " + sizeOfTree);
        return sizeOfTree;
    }

    // 新增的查找节点方法
    private Node findNode(Node current, int targetValue) {
        if (current == null) {
            return null;
        }
        if (targetValue == current.value) {
            return current;
        } else if (targetValue < current.value) {
            return findNode(current.left, targetValue);
        } else {
            return findNode(current.right, targetValue);
        }
    }

    // 新增的获取指定节点子树大小的方法
    public int getSubtreeSize(int targetValue) {
        Node targetNode = findNode(root, targetValue);
        if (targetNode == null) {
            System.out.println("Target node with value " + targetValue + " does not exist in the tree.");
            return -1;
        }
        int subtreeSize = size(targetNode);
        System.out.println("Size of subtree rooted at node with value " + targetValue + " is: " + subtreeSize);
        return subtreeSize;
    }
}

关键注意事项 #

• 如果你的二叉搜索树允许重复值，需要调整findNode方法的逻辑（比如返回第一个匹配的节点，或者所有匹配节点的子树大小总和，根据需求而定）；
• 可以根据业务需求调整节点不存在时的处理逻辑，比如抛出IllegalArgumentException而非返回-1；
• 递归方法的效率：对于平衡二叉搜索树，时间复杂度是O(h)（h为树的高度）；对于极端不平衡的树（类似链表），时间复杂度是O(n)，如果需要更高效的实现，可以在Node类中维护一个size字段，每次插入/删除节点时更新该值，这样获取子树大小可以做到O(1)时间复杂度。

内容的提问来源于stack exchange，提问作者Saif Miskin