编辑代码

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

typedef int KeyType;  // 定义关键字类型为整型

// 二叉排序树节点结构
typedef struct Node {
    KeyType key;               // 关键字值
    struct Node *lchild, *rchild;  // 左右指针
} BSTNode;

// 插入节点到二叉排序树中
void InsertBST(BSTNode **bst, int key) {
    /* 若在二叉排序树中不存在关键字等于key的记录,插入该记录 */
    BSTNode *s;
    if (*bst == NULL) {  // 递归结束条件
        s = (BSTNode *)malloc(sizeof(BSTNode));  // 申请新的节点s
        s->key = key;
        s->lchild = NULL;
        s->rchild = NULL;
        *bst = s;
    } else {
        if (key < (*bst)->key)
            InsertBST(&((*bst)->lchild), key);  // 将s插入左子树
        else if (key > (*bst)->key)
            InsertBST(&((*bst)->rchild), key);  // 将s插入右子树
        // 如果key等于(*bst)->key,则不做任何操作(假设不插入重复值)
    }
}

// 从键盘输入记录的值,创建相应的二叉排序树
void CreateBST(BSTNode **bst) {
    /* 输入0时结束 */
    int key;
    *bst = NULL;
    printf("请输入一系列整数(以0结束):\n");
    scanf("%d", &key);
    while (key != 0) {
        InsertBST(bst, key);
        scanf("%d", &key);
    }
}

// 在二叉排序树中查找某关键字等于key的记录
BSTNode *SearchBST(BSTNode *bst, int key) {
    /* 若查找成功,返回指向该记录节点指针,否则返回空指针 */
    if (!bst)
        return NULL;
    else if (bst->key == key)
        return bst;  // 查找成功
    else if (bst->key > key)
        return SearchBST(bst->lchild, key);  // 在左子树继续查找
    else
        return SearchBST(bst->rchild, key);  // 在右子树继续查找
}

// 中序遍历二叉排序树(用于验证树结构)
void InOrderTraverse(BSTNode *bst) {
    if (bst) {
        InOrderTraverse(bst->lchild);
        printf("%d ", bst->key);
        InOrderTraverse(bst->rchild);
    }
}

int main() {
    BSTNode *bst = NULL;
    int key;
    
    // 创建二叉排序树
    CreateBST(&bst);
    
    // 中序遍历输出验证树结构
    printf("\n中序遍历结果(应为升序排列):");
    InOrderTraverse(bst);
    printf("\n");
    
    // 查找节点
    printf("\n请输入要查找的关键字(输入0结束查找):\n");
    scanf("%d", &key);
    while (key != 0) {
        BSTNode *result = SearchBST(bst, key);
        if (result)
            printf("找到关键字 %d\n", key);
        else
            printf("未找到关键字 %d\n", key);
        
        scanf("%d", &key);
    }
    
    return 0;
}