7-6 数据结构实验四 二叉排序树

建立一个二叉排序树，根据给定值对其实施查找。

二叉排序树的二叉链表存储表示：

typedef int ElemType;
typedef  struct  BSTNode
{  
    ElemType  data;
    struct  BSTNode   *lchild,*rchild;
}BSTNode,*BSTree;

输入格式:

第一行输入二叉排序树中结点的值，以-1结束。用逐个插入的方式创建二叉排序树。

第二行输入一个要查找的值。

输出格式:

找到，输出have found!。接着空一格，输出该结点左孩子值，后再空一格，输出该结点右孩子的值。如果孩子为空，对应位置输出NULL。

如果没有找到，输出NOT FOUND!。

输入样例:

10 18 3 8 20 2 7 -1
3

输出样例:

have found! lchild:2 rchild:8

输入样例:

10 18 3 8 20 2 7 -1
8

输出样例:

have found! lchild:7 rchild:NULL

输入样例:

10 18 3 8 20 2 7 -1
5

输出样例:

NOT FOUND!

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

typedef int ElemType;
typedef struct Node
{
    ElemType data;
    struct Node *lchild, *rchild;
} Node, *tree;

// 创建新节点
Node *createNode(ElemType value)
{
    Node *newNode = (Node *)malloc(sizeof(Node));
    if (!newNode)
    {
        ;
    }
    newNode->data = value;
    newNode->lchild = NULL;
    newNode->rchild = NULL;
    return newNode;
}

// 插入节点到二叉排序树
void insert(tree *root, ElemType value)
{
    if (*root == NULL)
    {
        *root = createNode(value);
    }
    else if (value < (*root)->data)
    {
        insert(&((*root)->lchild), value);
    }
    else if (value > (*root)->data)
    {
        insert(&((*root)->rchild), value);
    }
}

// 查找节点并打印结果
void search(tree root, ElemType value)
{
    while (root != NULL && root->data != value)
    {
        if (value < root->data)
        {
            root = root->lchild;
        }
        else
        {
            root = root->rchild;
        }
    }
    if (root == NULL)
    {
        printf("NOT FOUND!\n");
    }
    else
    {
        printf("have found! lchild:");
        if (root->lchild != NULL)
        {
            printf("%d", root->lchild->data);
        }
        else
        {
            printf("NULL");
        }
        printf(" rchild:");
        if (root->rchild != NULL)
        {
            printf("%d", root->rchild->data);
        }
        else
        {
            printf("NULL");
        }
        printf("\n");
    }
}

int main()
{
    tree root = NULL;
    ElemType value;

    // 读取输入并构建二叉排序树
    while (scanf("%d", &value) && value != -1)
    {
        insert(&root, value);
    }

    // 读取要查找的值
    scanf("%d", &value);

    // 查找并输出结果
    search(root, value);

    return 0;
}