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

Question

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

Answer 1

你题目的解答代码如下：

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

typedef int Type;

typedef struct AVLTreeNode{
    Type key;                    // 关键字(键值)
    int height;                     //当前节点高度
    struct AVLTreeNode *left;    // 左孩子
    struct AVLTreeNode *right;    // 右孩子
}Node, *AVLTree;


#define HEIGHT(p)    ( (p==NULL) ? 0: (((Node *)(p))->height) )
#define MAX(a, b)    ( (a) > (b) ? (a) : (b) )

// 获取AVL树的高度
int avltree_height(AVLTree tree)
{
    return HEIGHT(tree);
}

// 前序遍历"AVL树" 先读取根节点，然后读取左子树，在读取右子树
void preorder_avltree(AVLTree tree)
{
    if (tree != NULL)
    {
        printf(" %d ", tree->key);
        preorder_avltree(tree->left);
        preorder_avltree(tree->right);
    }
}
// 中序遍历"AVL树" 先读取左子树，然后读取根节点，在读取右子树
void inorder_avltree(AVLTree tree)
{
    if (tree != NULL)
    {
        inorder_avltree(tree->left);
        printf(" %d ", tree->key);
        inorder_avltree(tree->right);
    }
}
// 后序遍历"AVL树" 先读取左子树，然后读取右子树，在读取根节点
void postorder_avltree(AVLTree tree)
{
    if (tree != NULL)
    {
        postorder_avltree(tree->left);
        postorder_avltree(tree->right);
        printf(" %d ", tree->key);
    }
}

/*
 * 打印"AVL树"
 * tree       -- AVL树的节点
 * key        -- 节点的键值
 * direction  --  0，表示该节点是根节点;
 *               -1，表示该节点是它的父结点的左孩子;
 *                1，表示该节点是它的父结点的右孩子。
*/
void print_avltree(AVLTree tree, Type key, int direction)
{
    if (tree != NULL)
    {
        if (direction == 0)
        {
            printf("%2d is root\n", tree->key, key);
        }
        else
        {
            printf("%2d is %2d's %6s child\n", tree->key, key, direction==1?"right" : "left");
        }

        print_avltree(tree->left, tree->key, -1);
        print_avltree(tree->right, tree->key, 1);
    }
}

// (递归实现)查找"AVL树x"中键值为key的节点
Node* avltree_search(AVLTree tree, Type key)
{
    if (tree==NULL || tree->key == key)
    {
        return tree;
    }

    if (tree->key > key) //小于根节点
    {
        avltree_search(tree->left, key);
    }
    else
    {
        avltree_search(tree->right, key);
    }
}
// (非递归实现)查找"AVL树x"中键值为key的节点
Node* iterative_avltree_search(AVLTree tree, Type key)
{
    while ((tree!=NULL) && (tree->key != key))
    {
        if (tree->key > key)
        {
            tree = tree->left;
        }
        else
        {
            tree = tree->right;
        }
    }
    return tree;
}

// 查找最小结点：返回tree为根结点的AVL树的最小结点。avl是有序树，所以查找左子树叶节点即可
Node* avltree_minimum(AVLTree tree)
{
    if (tree == NULL)
    {
        return NULL;
    }
    while (tree->left != NULL)
    {
        tree = tree->left;
    }

    return tree;
}
// 查找最大结点：返回tree为根结点的AVL树的最大结点。与最小节点相反查找右子树叶节点
Node* avltree_maximum(AVLTree tree)
{

    if (tree == NULL)
    {
        return NULL;
    }
    while (tree->right != NULL)
    {
        tree = tree->right;
    }

    return tree;
}

/*创建节点
 *left 新节点的左叶节点
 *right 新节点的右叶节点
*/
static Node* Create_AVLtree_Node(Type key, Node* left, Node* right)
{
    Node* pNode = (Node*)malloc(sizeof(Node));
    if (pNode == NULL)
    {
        return NULL;
    }

    pNode->key = key;
    pNode->height = 0;
    pNode->left = left;
    pNode->right = right;

    return pNode;
}

/*
 * LL : 左单旋转
 * 返回值：旋转后的根节点
*/
static Node* left_left_rotation(AVLTree k2)
{
    AVLTree k1;
    k1 = k2->left;
    k2->left  = k1->right;
    k1->right = k2;

    k2->height = MAX(HEIGHT(k2->left), HEIGHT(k2->right))+1;
    k1->height = MAX(HEIGHT(k1->left), k2->height)+1;

    return k1;
}

/*
 * RR : 右单旋转
 * 返回值：旋转后的根节点
*/
static Node* right_right_rotation(AVLTree k1)
{
    AVLTree k2;
    k2 = k1->right;
    k1->right  = k2->left;
    k2->left = k1;

    k1->height = MAX(HEIGHT(k1->left), HEIGHT(k1->right))+1;
    k2->height = MAX(HEIGHT(k2->right), k1->height)+1;

    return k2;
}

/*
 * LR : 左双旋转
 * 返回值：旋转后的根节点
*/
static Node* left_right_rotation(AVLTree k3)
{
    k3->left = right_right_rotation(k3->left);

    return left_left_rotation(k3);
}

/*
 * RL : 右双旋转
 * 返回值：旋转后的根节点
*/
static Node* right_left_rotation(AVLTree k1)
{
    k1->right = left_left_rotation(k1->right);

    return right_right_rotation(k1);
}

/* 将结点插入到AVL树中，返回根节点
* tree  AVL树根节点
* key   插入的节点的键值
* 返回值：根节点
*/
Node* avltree_insert(AVLTree tree, Type key)
{
    if (tree == NULL)
    {
        tree = Create_AVLtree_Node(key, NULL, NULL);
        if (tree == NULL)
        {
            printf("create Node fail\n");
            return NULL;
        }
    }
    else if (key > tree->key) //大于根节点，插入右子树
    {
        tree->right = avltree_insert(tree->right, key);
        if (HEIGHT(tree->right) - HEIGHT(tree->left) == 2)
        {
            if (key > tree->right->key)
            {
                tree = right_right_rotation(tree);
            }
            else
            {
                tree = right_left_rotation(tree);
            }
        }
    }
    else if(key < tree->key)
    {
        tree->left = avltree_insert(tree->left, key);
        if (HEIGHT(tree->left) - HEIGHT(tree->right) == 2)
        {
            if (key < tree->left->key)
            {
                tree = left_left_rotation(tree);
            }
            else
            {
                tree = left_right_rotation(tree);
            }
        }
    }
    else
    {
        printf("don't allow insert the same value\n");
    }

    tree->height = MAX( HEIGHT(tree->left), HEIGHT(tree->right)) + 1;

    return tree;
}


/*
* tree  AVL树根节点
* key   要删除的节点的键值
* 返回值：新根节点
*/
static Node* delteNode(AVLTree tree, Node* pdel)
{
    if (tree == NULL || pdel == NULL)
    {
        return NULL;
    }

    if (pdel->key < tree->key) //删除节点在左子树
    {
        tree->left = delteNode(tree->left, pdel);
        if (HEIGHT(tree->right) - HEIGHT(tree->left) == 2)
        {
            Node* pRTemp = tree->right;
            //调整平衡
            if (HEIGHT(pRTemp->left) > HEIGHT(pRTemp->right))
            {
                tree = right_left_rotation(pRTemp);
            }
            else
            {
                tree = right_right_rotation(pRTemp);
            }
        }
    }
    else if(pdel->key > tree->key) //删除节点在右子树
    {
        tree->right = delteNode(tree->right, pdel);
        if (HEIGHT(tree->left) - HEIGHT(tree->right) == 2)
        {
            Node* pLTemp = tree->left;
            if (HEIGHT(pLTemp->right) > HEIGHT(pLTemp->left))
            {
                tree = left_right_rotation(pLTemp);
            }
            else
            {
                tree = left_left_rotation(pLTemp);
            }
        }
    }
    else  //当前根节点就是要删除的节点
    {
        //节点左右孩子为空
        if ((tree->left) && (tree->right))
        {
            if (HEIGHT(tree->left) > HEIGHT(tree->right))
            {
                //左子树比右子树搞，找出tree的左子树最大节点，将该最大节点的值付给tree，然后该最大节点
                Node* maxnode = avltree_maximum(tree->left);
                tree->key = maxnode->key;
                tree->left = delteNode(tree->left, maxnode);
            }
            else
            {
                //如果左子树不比右子树高，找出tree右子树中的最小节点，将最小节点的值赋给tree，删除该最小节点
                Node* minnode = avltree_minimum(tree->right);
                tree->key = minnode->key;
                tree->right = delteNode(tree->right, minnode);
            }
        }
        else
        {
            Node* pTemp = tree;
            tree = tree->left ? tree->left : tree->right;
            free(pTemp);
        }
    }

    return tree;
}
// 删除结点(key是节点值)，返回根节点
Node* avltree_delete(AVLTree tree, Type key)
{
    Node* pTmp;

    if ((pTmp = avltree_search(tree, key)) != NULL)
    {
        tree = delteNode(tree, pTmp);
    }
    return tree;
}

// 销毁AVL树
void destroy_avltree(AVLTree tree)
{
    if (tree == NULL)
    {
        return;
    }
    if (tree->left != NULL)
    {
        destroy_avltree(tree->left);
    }
    if (tree->right != NULL)
    {
        destroy_avltree(tree->right);
    }

    free(tree);
}

int main()
{
    int i, ilen=20 , n;
    AVLTree root=NULL;
    srand((unsigned)time(NULL));
    for(i=0; i<ilen; i++)
    {
        root = avltree_insert(root, rand() % 1000);
    }
    inorder_avltree(root);
    printf("\n");

    scanf("%d", &n);
    while (n>=0)
    {
        Node *result = avltree_search(root, n);
        if(result != NULL)
        {
            root = avltree_delete(root, n);
            inorder_avltree(root);
            printf("\n");
        }
        else
            printf("-1\n");
       scanf("%d", &n);
    }
    // 销毁二叉树
    destroy_avltree(root);
    return 0;
}

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