关于#c语言#的问题：随机生成20个正整数，根据生成的顺序在内存中生成一棵平衡二叉树并在控制台输出该树
随机生成20个正整数，根据生成的顺序在内存中生成一棵平衡二叉树并在控制台输出该树。从控制台输入一个整数，如果为负数，程序结束；如果为正数，在平衡二叉树中查找该整数。如果该数不存在，输出-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;
}
您好，我是有问必答小助手，您的问题已经有小伙伴帮您解答，感谢您对有问必答的支持与关注！如有帮助，请点击我的回答下方的【采纳该答案】按钮帮忙采纳下，谢谢!
PS：问答VIP年卡 【限时加赠：IT技术图书免费领】，了解详情>>> https://vip.csdn.net/askvip?utm_source=1146287632