C语言实现二叉查找树：查找操作比较次数统计

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

// 定义二叉查找树的结点结构 typedef struct Node { int data; // 结点值 struct Node* left; // 左子树指针 struct Node* right; // 右子树指针 } Node;

// 创建新的结点 Node* createNode(int data) { Node* newNode = (Node*)malloc(sizeof(Node)); newNode->data = data; newNode->left = NULL; newNode->right = NULL; return newNode; }

// 在二叉查找树中插入结点 Node* insertNode(Node* root, int data) { // 如果根结点为空，则直接插入新的结点作为根结点 if (root == NULL) { return createNode(data); } // 如果插入的值小于根结点的值，则插入到左子树中 if (data < root->data) { root->left = insertNode(root->left, data); } // 如果插入的值大于等于根结点的值，则插入到右子树中 else { root->right = insertNode(root->right, data); } return root; }

// 在二叉查找树中查找结点 Node* searchNode(Node* root, int data, int* comparisons) { // 如果根结点为空或者与根结点的值相等，则返回根结点 if (root == NULL || root->data == data) { return root; } // 如果查找的值小于根结点的值，则继续在左子树中查找 if (data < root->data) { (*comparisons)++; // 比较次数加1 return searchNode(root->left, data, comparisons); } // 如果查找的值大于根结点的值，则继续在右子树中查找 else { (*comparisons)++; // 比较次数加1 return searchNode(root->right, data, comparisons); } }

// 主函数 int main() { Node* root = NULL; // 初始化二叉查找树的根结点 int comparisons = 0; // 初始化比较次数为0

// 插入结点
root = insertNode(root, 5);
root = insertNode(root, 3);
root = insertNode(root, 7);
root = insertNode(root, 1);
root = insertNode(root, 4);

// 查找结点并统计比较次数
Node* result = searchNode(root, 7, &comparisons);

// 输出结果
if (result == NULL) {
    printf("未找到该结点\n");
} else {
    printf("找到该结点，比较次数为：%d\n", comparisons);
}

return 0;

}

// 算法分析： // - 创建新结点的时间复杂度为O(1) // - 在二叉查找树中插入结点的时间复杂度为O(logn)，其中n为二叉查找树的结点个数 // - 在二叉查找树中查找结点的时间复杂度为O(logn)，其中n为二叉查找树的结点个数 // - 空间复杂度为O(n)，其中n为二叉查找树的结点个数