当前位置:网站首页>Binary tree and heap building in C language
Binary tree and heap building in C language
2022-07-07 07:57:00 【pythoncjavac++】
Catalog
Related concepts of binary tree
Binary tree related calculation formula
The insertion of a binary tree
Judge whether the binary tree is empty and the number of binary tree elements
Related concepts of binary tree
Binary tree : A binary tree is a tree structure in which each node has at most two subtrees .
Node degree : The number of subtrees a node contains .
Brother node : Nodes with the same parent are called siblings .
Leaf node or terminal node : A node without any children is called a leaf node .
Parent node 、 Child node : If multiple nodes are connected under a node , Then this node is called the parent node , The node below it is called a child node .
The degree of a tree : The maximum degree of all nodes . The degree of a binary tree is less than or equal to 2.
Depth of tree : Start at the root node ( Its depth is 0) Accumulated layer by layer from top to bottom .
The height of the tree : Start with the leaf node ( Its height is 0) Accumulated layer by layer from bottom to top .
The root node : The top node of a tree is called the root node .
The ancestor of node : From the root to all nodes on the branch through which the node passes .
The forest : from m A collection of disjoint trees .
Binary tree related calculation formula
1.n A binary tree of nodes has a total of ((2n)!)/(n! * (n+1)!) Kind of
2.n The second layer of a binary tree n Layers up to 2^(n-1) individual
3. Binary tree node calculation formula N = n0+n1+n2, Degree is 0 The leaf node ratio of is 2 The number of nodes is one more .N=1*n1+2*n2+1
4. have n The depth of a complete binary tree of nodes is log2(n) + 1
5. The height of the tree : The number of edges from the root node to the largest of all leaf nodes . Depth of tree : The maximum number of nodes from the root node to all leaf nodes .
Here is how to calculate the relationship between father and son ( a key )
leftchild=parent*2+1
rightchild=parent*2+2
parent=(child-1)/2
Next is how to create a binary tree
The creation of binary tree
typedef int HPDataType;
typedef struct Heap
{
HPDataType* a;
int size;
int capacity;
}HP;
Initialization of binary tree
void HeapInit(HP* php)
{
php->a = NULL;
php->size = php->capacity = 0;
}
Destruction of binary tree
void HeapDestroy(HP* php)
{
assert(php);
free(php->a);
php->a = NULL;
php->size = php->capacity = 0;
}
The insertion of a binary tree
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);
}
The deletion of binary trees
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);
}
Judge whether the binary tree is empty and the number of binary tree elements
bool HeapEmpty(HP* php)
{
return php->size == 0;
}
int HeapSize(HP* php)
{
assert(php);
return php->size ;
}
Building the heap
// Little heap
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;
}
}
// A lot
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;
}
}
Here are the codes for building large piles and small piles
边栏推荐
- 知识点滴 - 关于苹果认证MFI
- Figure out the working principle of gpt3
- Asemi rectifier bridge rs210 parameters, rs210 specifications, rs210 package
- IO stream file
- Leetcode 40: combined sum II
- Qt学习26 布局管理综合实例
- 芯片资料 网站 易特创芯
- [performance pressure test] how to do a good job of performance pressure test?
- Common validation comments
- 2022制冷与空调设备运行操作复训题库及答案
猜你喜欢
Explore Cassandra's decentralized distributed architecture
SQL优化的魅力!从 30248s 到 0.001s
Li Kou interview question 04.01 Path between nodes
[unity] several ideas about circular motion of objects
[webrtc] M98 screen and window acquisition
buuctf misc USB
[experience sharing] how to expand the cloud service icon for Visio
Leetcode 40: combined sum II
[CV] Wu Enda machine learning course notes | Chapter 8
Linux server development, MySQL transaction principle analysis
随机推荐
Is the test cycle compressed? Teach you 9 ways to deal with it
探索Cassandra的去中心化分布式架构
Problem solving: unable to connect to redis
C语言队列
Wx is used in wechat applet Showtoast() for interface interaction
What is the interval in gatk4??
[SUCTF 2019]Game
今日现货白银操作建议
【p2p】本地抓包
通信设备商,到底有哪些岗位?
微信小程序基本组件使用介绍
Custom class loader loads network class
Linux server development, redis protocol and asynchronous mode
Info | webrtc M97 update
LeetCode 40:组合总和 II
【数学笔记】弧度
Route jump in wechat applet
Use and analysis of dot function in numpy
Rust versus go (which is my preferred language?)
[unity] several ideas about circular motion of objects