当前位置:网站首页>C语言二叉树与建堆
C语言二叉树与建堆
2022-07-07 04:33:00 【pythoncjavac++】
目录
二叉树有关概念
二叉树:二叉树是每个节点最多有两个子树的树结构。
节点度:一个节点含有的子树的个数。
兄弟节点:具有相同父节点的节点互称为兄弟节点。
叶子节点或终端节点:没有任何子节点的节点称为叶子节点。
父节点、子节点:如果一个节点下面连接多个节点,那么该节点称为父节点,它下面的节点称为子 节点。
树的度:所有结点的度数的最大值。二叉树的度小于等于2。
树的深度:从根节点开始(其深度为0)自顶向下逐层累加的。
树的高度:从叶子节点开始(其高度为0)自底向上逐层累加的。
根节点:一棵树最上面的节点称为根节点。
节点的祖先:从根到该节点所经分支上的所有节点。
森林:由m棵互不相交的树组成的集合。
二叉树有关计算公式
1.n个节点的二叉树一共有((2n)!)/(n! * (n+1)!)种
2.n层二叉树的第n层最多为2^(n-1)个
3.二叉树节点计算公式 N = n0+n1+n2,度为0的叶子节点比度为2的节点数多一个。N=1*n1+2*n2+1
4.具有n个节点的完全二叉树的深度为log2(n) + 1
5. 树的高度:从根节点到所有叶节点中最大的边的数目。树的深度:从根节点到所有叶节点中最多的节点数目。
下面是计算父子间关系(重点)
leftchild=parent*2+1
rightchild=parent*2+2
parent=(child-1)/2
接下来是如何创建二叉树
二叉树的创建
typedef int HPDataType;
typedef struct Heap
{
HPDataType* a;
int size;
int capacity;
}HP;
二叉树的初始化
void HeapInit(HP* php)
{
php->a = NULL;
php->size = php->capacity = 0;
}
二叉树的销毁
void HeapDestroy(HP* php)
{
assert(php);
free(php->a);
php->a = NULL;
php->size = php->capacity = 0;
}
二叉树的插入
void swap(HPDataType* a, HPDataType* b)
{
HPDataType as = *a;
*a = *b;
*b = as;
}
void AdjustUpd(HPDataType* a, int child)
{
int parent = (child - 1) / 2;
while (child > 0)
{
if (a[parent] < a[child])
{
swap(&a[parent], &a[child]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
void HeapPush(HP* php, HPDataType x)
{
assert(php);
if (php->size == php->capacity)
{
int newca = php->capacity == 0 ? 4 : php->capacity * 2;
HPDataType* newhp = (HPDataType*)realloc(php->a, newca*sizeof(HPDataType));
if (newhp == NULL)
{
perror("realloc");
exit(-1);
}
php->a = newhp;
php->capacity = newca;
}
php->a[php->size] = x;
php->size++;
AdjustUpd(php->a, php->size-1);
}
二叉树的删除
void HeapPop(HP* php)
{
assert(php);
if (HeapEmpty(php))
{
return;
}
php->a[0] = php->a[php->size - 1];
php->size--;
AdjustDownd(php->a,php->size,0);
}
判断二叉树是否为空以及二叉树元素个数
bool HeapEmpty(HP* php)
{
return php->size == 0;
}
int HeapSize(HP* php)
{
assert(php);
return php->size ;
}
建堆
//小堆
void AdjustDown1(HPDataType* a, int size, int parent)
{
int child = parent * 2 + 1;
while (child < size)
{
if (child+1 < size && a[child + 1] < a[child])
{
child++;
}
if (a[child] < a[parent])
{
swap(&a[child], &a[parent]);
parent = child;
child = parent *2 +1;
}
else
break;
}
}
//大堆
void AdjustDownd(HPDataType* a, int size, int parent)
{
int child = parent * 2 + 1;
while (child < size)
{
if (child + 1 < size && a[child + 1] > a[child])
{
child++;
}
if (a[child] > a[parent])
{
swap(&a[child], &a[parent]);
parent = child;
child = parent *2 +1;
}
else
break;
}
}
这里分别是建大堆与小堆的代码
边栏推荐
- [SUCTF 2019]Game
- 快速使用 Jacoco 代码覆盖率统计
- [guess-ctf2019] fake compressed packets
- Visualization Document Feb 12 16:42
- IO流 file
- Rxjs - observable doesn't complete when an error occurs - rxjs - observable doesn't complete when an error occurs
- The configuration that needs to be modified when switching between high and low versions of MySQL 5-8 (take aicode as an example here)
- After the interview, the interviewer roast in the circle of friends
- [UVM foundation] what is transaction
- Regular e-commerce problems part1
猜你喜欢
【斯坦福计网CS144项目】Lab4: TCPConnection
自定义类加载器加载网络Class
Why should we understand the trend of spot gold?
LeetCode 90:子集 II
LeetCode 40:组合总和 II
Detailed explanation of uboot image generation process of Hisilicon chip (hi3516dv300)
buuctf misc USB
Shell 脚本的替换功能实现
Technology cloud report: from robot to Cobot, human-computer integration is creating an era
[webrtc] M98 screen and window acquisition
随机推荐
通信设备商,到底有哪些岗位?
pytest+allure+jenkins環境--填坑完畢
[UTCTF2020]file header
Pytest+allure+jenkins environment -- completion of pit filling
[OBS] win capture requires winrt
[CV] Wu Enda machine learning course notes | Chapter 8
【斯坦福计网CS144项目】Lab3: TCPSender
【斯坦福计网CS144项目】Lab4: TCPConnection
图解GPT3的工作原理
科技云报道:从Robot到Cobot,人机共融正在开创一个时代
解决:Could NOT find KF5 (missing: CoreAddons DBusAddons DocTools XmlGui)
The configuration that needs to be modified when switching between high and low versions of MySQL 5-8 (take aicode as an example here)
[GUET-CTF2019]虚假的压缩包
Route jump in wechat applet
探索干货篇!Apifox 建设思路
Qt学习28 主窗口中的工具栏
Solve could not find or load the QT platform plugin "xcb" in "
直播平台源码,可折叠式菜单栏
[Stanford Jiwang cs144 project] lab4: tcpconnection
nacos