c语言 二叉排序树的查找算法

二叉排序树（Binary Sort Tree或 Binary Search Tree）是一种用于实现数据快速查找的数据结构。它具有以下特点：左子树上的元素都小于树根，右子树上的元素都大于树根，所有的子树也满足这个性质。在二叉排序树上查找某个节点，可以使用以下算法：

1. 从树根开始遍历二叉树。
2. 如果待查找元素小于树根元素，则向左遍历。
3. 如果待查找元素大于树根元素，则向右遍历。
4. 如果待查找元素等于树根元素，则结束遍历，找到了目标节点。
5. 如果遍历到叶子节点仍未找到目标节点，则说明目标节点不存在于二叉排序树中。

下面是一个具体的C语言实现二叉排序树查找算法的例子：

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

// 定义二叉排序树的节点结构
typedef struct BSTNode {
    int data;
    struct BSTNode* left;
    struct BSTNode* right;
} BSTNode;

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

// 向二叉排序树插入节点
BSTNode* insertNode(BSTNode* root, int data) {
    if (root == NULL) {
        return createNode(data);    }
    if (data < root->data) {
        root->left = insertNode(root->left, data);
    } else if (data > root->data) {
        root->right = insertNode(root->right, data);
    }
    return root;
}

// 在二叉排序树中查找节点
BSTNode* searchNode(BSTNode* root, int data) {
    if (root == NULL || root->data == data) {
        return root;
    }
    if (data < root->data) {
        return searchNode(root->left, data);
    } else {
        return searchNode(root->right, data);
    }
}

// 销毁二叉排序树
void destroyTree(BSTNode* root) {
    if (root != NULL) {
        destroyTree(root->left);
        destroyTree(root->right);
        free(root);
    }
}

int main() {
    BSTNode* root = NULL;
    root = insertNode(root, 50);
    insertNode(root, 30);
    insertNode(root, 20);
    insertNode(root, 40);
    insertNode(root, 70);
    insertNode(root, 60);
    insertNode(root, 80);

    int target = 40;
    BSTNode* result = searchNode(root, target);
    if (result != NULL) {
        printf("找到了目标节点：%d\n", result->data);
    } else {
        printf("未找到目标节点：%d\n", target);
    }

    destroyTree(root);

    return 0;
}