编写算法求给定结点在二叉排序树中所在的层数

在二叉排序树（BST）中，给定一个节点，我们可以通过递归的方式计算它所在的层数。基本思路是这样的：

1. 如果节点为空，那么层数为0，因为根节点被认为是第一层。
2. 否则，比较当前节点的值与父节点的值。如果当前节点的值小于父节点，则在左子树中继续搜索；如果大于父节点，则在右子树中查找。
3. 对于找到的非空节点，它的层数等于父节点的层数加1。因为我们是在向下一层移动。

这个过程可以用递归来表示，函数可以接收两个参数：当前节点和当前层数（初始为1）。当找到目标节点时，返回当前层数即可。

以下是Python的一个示例代码：

def find_level(root, target):
    if not root:
        return 0
    elif root.val == target:
        return 1
    else:
        left_height = find_level(root.left, target)
        right_height = find_level(root.right, target)

        # 返回较大的一边加上1，因为目标在那一边的上一层
        return max(left_height, right_height) + 1

相关问题

编写算法求给定结点在二叉排序树中所在的层数。用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;
}

设二叉树为以二叉链表为存储结构，且树中结点的关键字均不同。用c语言编写算法，判别给定二叉树是否为二叉排序树

可以使用中序遍历二叉树，将遍历结果存储在一个数组中，然后判断数组是否为升序排列即可。

具体实现代码如下：

#include <stdio.h>
#include <stdlib.h>

// 二叉树结点定义
typedef struct node {
    int data; // 结点数据
    struct node *left; // 左子树指针
    struct node *right; // 右子树指针
} Node;

// 中序遍历二叉树，将结果存储在数组中
void inorder(Node *root, int arr[], int *index) {
    if (root == NULL) {
        return;
    }
    inorder(root->left, arr, index);
    arr[(*index)++] = root->data;
    inorder(root->right, arr, index);
}

// 判断数组是否为升序排列
int isSorted(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        if (arr[i] > arr[i+1]) {
            return 0;
        }
    }
    return 1;
}

// 判断给定二叉树是否为二叉排序树
int isBST(Node *root) {
    int arr[100]; // 存储中序遍历结果的数组
    int index = 0; // 数组下标
    inorder(root, arr, &index);
    return isSorted(arr, index);
}

// 创建二叉树结点
Node* createNode(int data) {
    Node *node = (Node*) malloc(sizeof(Node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

int main() {
    // 创建二叉排序树
    Node *root = createNode(4);
    root->left = createNode(2);
    root->left->left = createNode(1);
    root->left->right = createNode(3);
    root->right = createNode(6);
    root->right->left = createNode(5);
    root->right->right = createNode(7);

    // 判断是否为二叉排序树
    if (isBST(root)) {
        printf("给定二叉树是二叉排序树\n");
    } else {
        printf("给定二叉树不是二叉排序树\n");
    }

    return 0;
}

输出结果：

给定二叉树是二叉排序树