记录
21:16 2024-3-3
1. 二叉树
1.二叉查找树(BST)
2.Treap
3.平衡二叉树(AVL)
先把自己当时学的时候写的放上来 reference:《数据结构与算法分析》
嘛，现在只能记得左旋右旋了(喝左旋哈哈哈)
点击查看代码
#define _CRT_SECURE_NO_WARNINGS //vs中scanf为不安全的函数 要使用 得加上这句话
#include<stdio.h>
#include<malloc.h>
typedef struct TNode* BinTree;
typedef BinTree Position;
struct TNode
{
int Element;
BinTree Left;
BinTree Right;
int Heigth; //高度
};
int GetHeight(BinTree T)
{
if (!T)
return -1;
else
return T->Heigth;
}
int Max(int a, int b)
{
return (a > b) ? a : b;
}
BinTree NewNode(int Element)
{
BinTree T = (BinTree)malloc(sizeof(struct TNode));
T->Element = Element;
T->Left = NULL;
T->Right = NULL;
T->Heigth = 0;
return T;
}
BinTree SingleLeftRotation(BinTree T)
{
BinTree TL = T->Left;
T->Left = TL->Right;
TL->Right = T;
T->Heigth = Max(GetHeight(T->Left), GetHeight(T->Right)) + 1;
TL->Heigth = Max(GetHeight(TL->Left),T->Heigth)+1;
return TL;
}
BinTree SingleRightRotation(BinTree T)
{
BinTree TR = T->Right;
T->Right = TR->Left;
TR->Left = T;
T->Heigth = Max(GetHeight(T->Left),GetHeight(T->Right))+1;
TR->Heigth =Max(GetHeight(TR->Right),T->Heigth)+1;
return TR;
}
BinTree DoubleLeftRightRotation(BinTree T)
{ //先做一次右单旋 再做一次左单旋
T->Left = SingleRightRotation(T->Left);
return SingleLeftRotation(T);
}
BinTree DoubleRightLeftRotation(BinTree T)
{//先做一次左旋 再做一次右旋
T->Right = SingleLeftRotation(T->Right);
return SingleRightRotation(T);
}
BinTree Insert(int Element, BinTree BST)
{
if (!BST) //BST为空 生成该节点 并且返回
BST = NewNode(Element);
else if (Element < BST->Element)
{
BST->Left = Insert(Element, BST->Left); //递归插入左子树
if (GetHeight(BST->Left) - GetHeight(BST->Right) == 2) //判断是否需要进行旋转
if (Element < BST->Left->Element) //左单旋
BST=SingleLeftRotation(BST);
else
BST=DoubleLeftRightRotation(BST); //左-右双旋
}
else if (BST->Element < Element)
{
BST->Right = Insert(Element, BST->Right); //递归插入右子树
if (GetHeight(BST->Left) - GetHeight(BST->Right) == -2)
if (Element > BST->Right->Element) //右单旋
BST=SingleRightRotation(BST);
else
BST=DoubleRightLeftRotation(BST); //右-左双旋
}
BST->Heigth = Max(GetHeight(BST->Left), GetHeight(BST->Right)) + 1;
return BST;
}
BinTree MakeTree()
{
int N;
scanf("%d",&N);
int num;
scanf("%d", &num);
BinTree T = NewNode(num);
for (int i = 1; i < N; i++)
{
scanf("%d", &num);
T=Insert(num, T);
}
return T;
}
int main()
{
BinTree Root = MakeTree();
printf("%d", Root->Element);
}