C语言实现二叉查找树搜索算法：代码注释详解

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

// 定义二叉查找树节点结构体 typedef struct TreeNode { int data; // 节点存储的数据 struct TreeNode* left; // 左子树指针 struct TreeNode* right; // 右子树指针 } TreeNode;

// 创建新节点 TreeNode* createNode(int value) { TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode)); // 为新节点分配内存空间 newNode->data = value; // 设置新节点的数据为传入的值 newNode->left = NULL; // 初始化左子树指针为空 newNode->right = NULL; // 初始化右子树指针为空 return newNode; // 返回新节点 }

// 向二叉查找树插入节点 TreeNode* insertNode(TreeNode* root, int value) { if (root == NULL) { // 树为空，创建新节点作为根节点 return createNode(value); } if (value < root->data) { // 插入值小于当前节点值，插入到左子树 root->left = insertNode(root->left, value); // 递归插入左子树 } else if (value > root->data) { // 插入值大于当前节点值，插入到右子树 root->right = insertNode(root->right, value); // 递归插入右子树 } return root; // 返回根节点 }

// 在二叉查找树中查找节点，返回比较次数 int searchNode(TreeNode* root, int value, int count) { if (root == NULL) { // 查找失败 return count; } if (value == root->data) { // 查找成功 return count + 1; // 返回比较次数 } if (value < root->data) { // 查找值小于当前节点值，继续在左子树中查找 return searchNode(root->left, value, count + 1); // 递归查找左子树 } else { // 查找值大于当前节点值，继续在右子树中查找 return searchNode(root->right, value, count + 1); // 递归查找右子树 } }

int main() { int N; // 元素个数 scanf('%d', &N); // 输入元素个数

int* elements = (int*)malloc(N * sizeof(int));  // 待查找集合，动态分配内存空间
for (int i = 0; i < N; i++) {
    scanf('%d', &elements[i]);  // 输入待查找集合中的元素
}

int searchValue;  // 待查值
scanf('%d', &searchValue);  // 输入待查值

TreeNode* root = NULL;  // 二叉查找树的根节点
for (int i = 0; i < N; i++) {
    root = insertNode(root, elements[i]);  // 插入节点
}

int compareCount = searchNode(root, searchValue, 0);  // 在二叉查找树中查找节点

printf('%d

', compareCount); // 输出比较次数

free(elements);  // 释放内存

return 0;