数据结构-------------------二叉排序树的查找

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

typedef struct BSTNode {  
    int key;  
    struct BSTNode *lchild;  
    struct BSTNode *rchild;  
} BSTNode, *BSTTree;  

// 递归实现二叉排序树的查找操作  
BSTNode *BSTSearch(BSTTree T, int key) {  
    if (T == NULL)  
        return NULL;  
    else if (key == T->key)  
        return T;  
    else if (key > T->key)  
        return BSTSearch(T->rchild, key);  
    else  
        return BSTSearch(T->lchild, key);  
}  

// 非递归实现方法  
BSTNode *BSTSearch2(BSTTree T, int key) {  
    while (T != NULL && key != T->key) {  
        if (key > T->key)  
            T = T->rchild;  
        else  
            T = T->lchild;  
    }  
    return T;  
}  

// 插入节点  
int BST_Insert(BSTTree *T, int k) {  
    if (*T == NULL) {  
        *T = (BSTNode *)malloc(sizeof(BSTNode));  
        (*T)->key = k;  
        (*T)->lchild = (*T)->rchild = NULL;  
        return 1;  
    } else if (k == (*T)->key) {  
        return -1; // 关键字相同插入失败  
    } else if (k < (*T)->key) {  
        return BST_Insert(&((*T)->lchild), k);  
    } else {  
        return BST_Insert(&((*T)->rchild), k);  
    }  
}  

// 创建二叉排序树  
void Creat_BSTTree(BSTTree *T, int str[], int n) {  
    *T = NULL; // 初始状态为空   
    for (int i = 0; i < n; i++) {  
        BST_Insert(T, str[i]);  
    }  
}  

// 释放二叉排序树的内存  
void BST_Destroy(BSTTree *T) {  
    if (*T != NULL) {  
        // 先递归释放左子树  
        BST_Destroy(&((*T)->lchild));  
        // 再递归释放右子树  
        BST_Destroy(&((*T)->rchild));  
        // 最后释放当前节点  
        free(*T);  
        *T = NULL; // 将指针置为空  
    }  
}  

int main() {  
    BSTTree tree;  
    int arr[] = {40, 20, 60, 10, 30, 50, 70};  
    int n = sizeof(arr) / sizeof(arr[0]); //用以确定元素个数 

    Creat_BSTTree(&tree, arr, n); // 创建二叉排序树  

     
    int searchKey;  
    printf("请输入要查找的值: ");  
    scanf("%d", &searchKey);  

    BSTNode *result = BSTSearch(tree, searchKey);  //递归方式查找
    if (result != NULL) {  
        printf("找到了节点: %d\n", result->key);  
    } else {  
        printf("未找到节点\n");  
    }  

    // 释放内存  
    BST_Destroy(&tree);  
    return 0;  
}