如何编写代码，计算二叉排序树T中，关键字key的查找长度

Question

Help，如何编写代码，计算二叉排序树T中，关键字key的查找长度

Answer 1

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

// 二叉排序树节点定义
typedef struct node {
    int key;           // 节点关键字
    struct node* left; // 左子节点
    struct node* right; // 右子节点
} Node;

// 在二叉排序树T中插入关键字key
Node* insert(Node* T, int key) {
    if (T == NULL) {
        T = (Node*)malloc(sizeof(Node));
        T->key = key;
        T->left = NULL;
        T->right = NULL;
    } else {
        if (key < T->key) {
            T->left = insert(T->left, key);
        } else if (key > T->key) {
            T->right = insert(T->right, key);
        }
    }
    return T;
}

// 在二叉排序树T中查找关键字key的查找长度，初始长度为0
int search(Node* T, int key, int len) {
    if (T == NULL) {
        return -1; // 没找到
    } else if (key < T->key) {
        return search(T->left, key, len + 1);
    } else if (key > T->key) {
        return search(T->right, key, len + 1);
    } else {
        return len + 1; // 找到了
    }
}

int main() {
    // 创建一个二叉排序树
    Node* T = NULL;
    T = insert(T, 8);
    T = insert(T, 3);
    T = insert(T, 10);
    T = insert(T, 1);
    T = insert(T, 6);
    T = insert(T, 4);
    T = insert(T, 7);
    T = insert(T, 14);
    T = insert(T, 13);

    // 查找和计算查找长度
    int key = 7;
    int len = search(T, key, 0);

    // 输出结果
    if (len < 0) {
        printf("Key not found\n");
    } else {
        printf("Key %d found, search length: %d\n", key, len);
    }

    return 0;
}