关于#c语言#的问题：随机生成20个正整数，根据生成的顺序在内存中生成一棵二叉搜索树并在控制台输出该树

Question

随机生成20个正整数，根据生成的顺序在内存中生成一棵二叉搜索树并在控制台输出该树。从控制台输入一个整数，如果为负数，程序结束；如果为正数，在二叉搜索树中查找该整数。如果该数不存在，输出-1；如果存在，删除该结点并输出删除结点后的树。

Answer 1

你题目的解答代码如下：

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

#define TREE_TYPE int
#define size 20

/**定义树形结构*/
typedef struct Tree
{
    TREE_TYPE value;
    struct Tree *left;
    struct Tree *right;
}Tree_node;

/**根节点做为全局静态变量*/
static Tree_node *root;

/**初始化树*/
void create_tree()
{
    root = NULL;
}

/**向树种插入数据*/
Tree_node* insert(Tree_node *node,TREE_TYPE value)
{
    if(node == NULL)
    {
        node = (Tree_node*)malloc(sizeof(Tree_node) * 1);
        node-> value = value;
        node -> left = NULL;
        node -> right = NULL;
        if(root == NULL) //若是为根节点
            root = node;
    }
    else
    {
        if(value < node->value) //比该节点值小，写向左子树
            node->left = insert(node->left,value);
        else //比该节点值大，写向右子树
            node->right = insert(node->right,value);
    }
    return node;
}

/**显示树中全部节点内容*/
void show_all(Tree_node *node)
{
    if(node != NULL)
    {
        if(node->left != NULL)
            show_all(node->left);
        printf("%d ",node->value);
        if(node->right != NULL);
            show_all(node->right);
    }
}

/**根据值查找某一特定节点*/
Tree_node* search(Tree_node *node,TREE_TYPE value)
{
    Tree_node *result = NULL;
    if(node != NULL)
    {
        if(value == node->value)
            result = node;
        else if(value < node->value)
            result = search(node->left,value);
        else
            result = search(node->right,value);
    }
    return result;
}

/**找到某一值对应节点的父节点*/
Tree_node* find_parent(Tree_node *parent,TREE_TYPE value)
{
    Tree_node *result = NULL;
    if(parent != NULL)
    {
        if(value < parent->value && parent->left != NULL) //比父节点值小，访问左子树
        {
            if(value == parent->left->value)
                result = parent;
            else
            {
                result = find_parent(parent->left,value);
                if(result == NULL)
                    result = find_parent(parent->right,value);
            }
        }
        if(value > parent->value && parent->right != NULL) //比父节点值大，访问右子树
        {
            if(value == parent->right->value)
                result = parent;
            else
            {
                result = find_parent(parent->left,value);
                if(result == NULL)
                    result = find_parent(parent->right,value);
            }
        }
    }
    return result;
}

void delete(TREE_TYPE value)
{
    Tree_node *parent = find_parent(root,value); //找到待删节点的父节点
    Tree_node *node = search(root,value); //找到待删节点
    if(node == NULL) //待删节点不存在
        printf("没有待删节点\n");
    else //待删节点存在
    {
        if(node->left == NULL && node->right == NULL) //若是待删节点是叶子节点
        {
           // assert(parent != NULL);
            if(parent == NULL) //若是是根节点
                root = NULL;
            else //其余节点
            {
                if(node == parent->left)
                    parent->left = NULL;
                else
                    parent->right = NULL;
            }
        }
        else if(node->right == NULL) //若是待删节点只有左子树节点
        {
            if(parent == NULL) //若是是根节点
                root = node->left;
            else //其余节点
            {
                if(node == parent->left)
                    parent->left = node->left;
                else
                    parent->right = node->left;
            }
        }
        else if(node->left == NULL) //若是待删节点只有右子树节点
        {
            if(parent == NULL) //若是是根节点
                root = node->right;
            else //其余节点
            {
                if(node == parent->left)
                    parent->left = node->right;
                else
                    parent->right = node->right;
            }
        }
        else //若是带删节点左右子树节点都存在
        {
            Tree_node *new_node = node->right; //须要找到右子树的最左那个
            Tree_node *new_node_parent = NULL;
            while(new_node->left != NULL)
            {
                new_node_parent = new_node;
                new_node = new_node->left;
            }
            if(new_node != node->left)
                new_node->left = node->left;
            if(new_node != node->right)
                new_node->right = node->right;
            if(parent == NULL)
                root = new_node;
            else
            {
                if(node == parent->left) //若是带删节点是父节点的左节点
                    parent->left = new_node;
                else //若是待删节点是父节点的右节点
                    parent->right = new_node;
            }
            if(new_node_parent != NULL)//将原来的右子树最左节点删掉
                new_node_parent->left = NULL;
        }
    }
}

int main()
{
    /**初始化*/
    create_tree();

    /**插入*/
    int i,n;
    srand((unsigned)time(NULL));
    for(i = 0; i < size; i++)
        insert(root, rand() % 100);

    /**显示所有*/
    show_all(root);
    putchar('\n');

    /**根据值查找某节点*/
    scanf("%d", &n);
    while (n>=0)
    {
        Tree_node *result = search(root,n);
        if(result != NULL)
        {
            delete(n); //删除叶子节点
            show_all(root);
            printf("\n");
        }
        else
            printf("-1\n");
       scanf("%d", &n);
    }

    return 0;
}

如有帮助，请点击我的回答下方的【采纳该答案】按钮帮忙采纳下，谢谢!