编写算法求给定结点在二叉排序树中所在的层数。用C++代码实现

在二叉排序树（BST）中，每个节点的左子树的值都小于该节点的值，右子树的值都大于该节点的值。因此，我们可以采用递归的方式计算给定节点所在层次。首先，我们比较节点的值与根节点的值，如果相等则返回1，因为根节点在第一层；如果比根节点小，我们在左子树中递归查找；反之，在右子树中。同时，每进入一层，层数加1。

以下是C++代码实现：

class TreeNode {
public:
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

int findHeight(TreeNode* root, TreeNode* node) {
    if (root == NULL || root == node) {
        return root == node ? 0 : -1; // 如果到达空节点或者找到了目标节点，返回对应的层数
    }

    // 计算当前节点的左子树高度
    int left_height = findHeight(root->left, node);

    // 计算当前节点的右子树高度
    int right_height = findHeight(root->right, node);

    // 返回较大的一边的高度+1，因为当前节点在那一边的上一层
    return std::max(left_height, right_height) + 1;
}

int main() {
    // 创建二叉排序树并设置节点
    TreeNode* root = new TreeNode(4); // 根节点
    root->left = new TreeNode(2);
    root->right = new TreeNode(6);
    root->left->left = new TreeNode(1);
    root->left->right = new TreeNode(3);
    root->right->left = new TreeNode(5);
    root->right->right = new TreeNode(7);

    TreeNode* targetNode = root->left->right; // 目标节点

    int height = findHeight(root, targetNode);
    std::cout << "The given node is on the " << height << "th level." << std::endl;

    return 0;
}