数据结构实验之查找二:平衡二叉树 (SDUT 3374)
2023-06-13 09:17:22 时间
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
struct node
{
int data;
int h;
struct node *lc,*rc; //平衡二叉树 需要一个 h 来记录平衡因子
};
int max(int x ,int y)
{
if(x > y) return x;
else return y;
}
int fin(struct node *root) // 返回这个结点的平衡因子,也就是左右子树的差值
{
if(root == NULL) return -1;
else return root -> h;
}
struct node *LL(struct node *root) // 如果是左左型,也就是呈现 根 - 左子树 p - 左子树2 , 我们要把 根 变成 p 的右子树
{
struct node *p = root -> lc;
root -> lc = p -> rc;
p -> rc = root;
p -> h = max(fin(p->lc),fin(p->rc)) + 1; // 更新这两个点的平衡因子
root -> h = max(fin(root->lc),fin(root->rc)) + 1;
return p; //别忘记返回 p
}
struct node *RR(struct node *root) // 同上相反
{
struct node *p = root -> rc;
root -> rc = p -> lc;
p -> lc = root;
p -> h = max(fin(p->lc),fin(p->rc)) + 1;
root -> h = max(fin(root->lc),fin(root->rc)) + 1;
return p;
}
struct node *LR(struct node *root) //LR型, 形如 根 - 左子树 - 右子树
{
root -> lc = RR(root -> lc);
return LL(root);
}
struct node *RL(struct node *root)
{
root -> rc = LL(root -> rc);
return RR(root);
}
struct node *creat(struct node *root, int x) // 建树的过程
{
if(root == NULL) //如何到底层或者到可以放这个数的地方
{
root = (struct node *)malloc(sizeof(struct node));
root -> data = x;
root -> lc = root -> rc = NULL; // 左右孩子、h 初始化
root -> h = 0;
}
else if(root -> data > x) // 如果小的话,找左子树,
{
root -> lc = creat(root -> lc, x);
if(fin(root->lc) - fin(root->rc) > 1) // 如果找完之后,放进去之后,判断时候不平衡了,如果不平衡,判断是什么样子的类型,再旋转
{
if(root -> lc -> data > x) root = LL(root); // LL型,因为如果 root -> lc -> data > x,那么 x 是放在了这个的左子树
else root = LR(root); //相反,这样子会放在右子树
}
}
else if(root -> data < x)
{
root -> rc = creat(root -> rc, x);
if(fin(root->rc) - fin(root->lc) >1)
{
if(root -> rc -> data < x) root = RR(root);
else root = RL(root);
}
}
root -> h = max(fin(root->lc),fin(root->rc)) + 1; // 每插入一次新值,更新 root 的平衡因子
return root;
}
int main()
{
int n,m;
scanf("%d",&n);
struct node *root = NULL;
for(int i = 0; i < n; i ++)
{
scanf("%d",&m);
root = creat(root,m);
}
printf("%d\n",root->data);
return 0;
}
相关文章
- LeetCode每日一题:翻转二叉树
- 数据结构与算法二叉树的算法_数据结构c语言二叉树的深度
- JavaScript——二叉树层序遍历
- 二叉树的详解与实现「建议收藏」
- 二叉树 二叉搜索树_二叉树和二叉搜索树
- 年会 (记忆化搜索+二叉树思想)------------------------------C语言—菜鸟级
- 二叉树前序遍历详解[通俗易懂]
- 「数据结构与算法Javascript描述」二叉树
- 104. 二叉树的最大深度
- 算法与数据结构之二叉树的遍历
- JavaScript刷LeetCode拿offer-二叉树层序遍历篇
- 数据结构:C语言实现二叉树及相关操作(递归,迭代)
- Go 数据结构和算法篇(十八):平衡二叉树
- MySQL 6种索引数据结构详解:BTree、B+Tree、红黑树、平衡二叉树、二叉树、Hash
- 【初阶数据结构】树和二叉树的基本概念和结构
- 数据结构小记【Python/C++版】——树与二叉树篇
- 【数据结构】建立二叉树以及哈夫曼树及哈夫曼编码
- 数据结构实验之二叉树三:统计叶子数 SDUT 3342
- 数据结构实验之二叉树七:叶子问题(SDUT 3346)
- 数据结构之AVL平衡二叉树
- [数据结构]二叉树的链式存储结构
- 【数据结构初阶】树+二叉树+堆的实现+堆的应用
- 【数据结构初阶】链式二叉树接口实现+痛苦的OJ题
- 【数据结构】二叉树
- 算法-按之字形顺序打印二叉树详解编程语言
- 算法-二叉树中和为某一值的路径详解编程语言
- python数据结构之二叉树的遍历实例