Data structure-binary tree·heap (implementation of sequential structure)

Personal business card:

About the author: A sophomore student who is willing to share what he has learned on the road of study.
Personal homepage: GOTXX
Personal WeChat: ILXOXVJE
This article is original by GOTXX and first published on CSDN
Column series: Learning C language from scratch —– The road to learning data structures
Word of the day: If you are not particularly lucky, then please work extra hard!
—————-

Article introduction:

This article explains in detail the related concepts and structures of trees, the concepts and structures of binary trees (heaps), the sequential structure and implementation of binary trees! Binary tree chain structure will be explained in the next chapter!

If you think the article is good, I look forward to your one-click triple connection. Your encouragement is the source of my creative motivation. Let’s work together, run together, and let’s meet at the top! ! !

Table of Contents

1. Concept and structure of tree

1.1 Concept of tree

Related concepts:

1.2 Representation of tree

2. Concept and structure of binary tree

2.1 The concept of binary tree

Binary tree:

2.2 Two special binary trees

Full binary tree:

Complete binary tree:

3. Binary tree sequence structure and implementation

3.1 Binary tree sequence structure

Heap storage classification: large root heap, small root heap

3.2 Implementation of binary tree (heap) sequential structure

Here we focus on analyzing the upward/downward adjustment function

Adjust upward:

Adjust downward:

Complete code: Heap.h Heap.c

1. The concept and structure of trees

A tree is a nonlinear data structure. It is a collection of k nodes (k>=0) with hierarchical relationships, as shown in Figure 1. Turn the above figure upside down. As shown in Figure 2, it looks like a tree, so it is called a tree;

Similar to the characteristics of a tree, the top node (A) is called the root node;

In addition to the root node, the remaining nodes can be divided into several tree-like subtrees, as shown below:

Sotrees are defined recursively;

1. The degree of the node: and the number of subtrees the node contains (how many children it has), as shown in the figure above: the degree of 1 is 3, the degree of 2 is 1, and the degree of 4 is 2;

2. Leaf node (terminal node): a node with degree 0, such as 3, 5, 6, 7 in the figure above;

3. Branch nodes (non-terminal nodes): nodes other than the root node and leaf nodes, such as 2, 4;

4. Parent node (parent node): A node contains a child node, which is called the parent node of the child node. For example, 1 is the parent node of 2, 3, and 4, and 4 is the parent node of 6 and 7. the parent node;

5. Child node (child node): For example, 5 is the child node of 2, and 4 is the child node of 1;

6. Brother nodes: Nodes with the same parent node are called brother nodes. For example, the parent nodes of 6 and 7 are both 4, so 6 and 7 are brother nodes;

7. Degree of tree: In a tree, the degree of the largest node is called the degree of the tree. For example, the degree of the tree above is 3 (because the degree of 1 is the largest, which is 3);

8. Node level: the root is the first level, and so on;

9. The height (depth) of the tree: As shown in the picture above, the height of the tree is 3;

10. Forest: a collection of many disjoint trees;

11. The number of nodes with degree 0 is N0, and the number of nodes with degree 2 is N2; then N0=N2 + 1;

1.2 tree representation

The most common is the child brother notation

Parent representation (generally using structure array): Only the subscript or pointer of the parent is stored;

For example:

The tree above is represented in parent notation:

Blue: The stored subscript or pointer of the parent node of this node;

If there is no father, store -1 (-1 is not a valid subscript);

2. The concept and structure of binary trees

2.1 Concept of Binary Tree

Binary tree:

1. There is no tree with a node with degree greater than 2; at most two, which can be 1 or 0;

Degree is 0 (empty tree);

2. The subtrees of a binary tree are divided into left and right subtrees, and the order cannot be reversed, so the binary tree is ordered;

2.2 Two special binary trees

Full binary tree:

A binary tree, if the number of nodes at each level reaches the maximum, this number is a full binary tree;

Assuming that a full binary tree has h levels, the total nodes of the binary tree are 2^h-1;

Complete binary tree:

It is a binary tree with n nodes of depth k. The nodes in the tree are numbered from top to bottom and from left to right. If the node numbered i1≤i≤n is the same as the node numbered in the full binary tree, The nodes of i have the same position in the binary tree;

3. Binary tree sequence structure and implementation

3.1 Binary tree sequence structure

According to the characteristics of a complete binary tree, we can draw the following conclusion:

If a complete binary tree is stored in an array, then any parent node can be obtained, the child can be found through the subscript, and the subscript of the parent node can also be found through the child subscript;

The rules are as follows:

liftchild = perent*2 + 1;

rightchild = parent*2 + 2;

parent = (child-1)/2;

Heap storage classification: large root heap, small root heap

3.2 Implementation of Binary Tree (Heap) Sequential Structure

Here we focus on the analysis of upward/downward adjustment functions

Adjust up:

Idea: Insert the tail of the inserted data into the array, and make adjustments based on the upward comparison between the parent node and the subscript of the child node. If the data of the father node is greater (less than) the child node, exchange it: as shown in the figure:

Implementation code:

//Exchange function
void Swap(HPDataType* x, HPDataType* y)
{
HPDataType tmp = *x;
*x = *y;
*y = tmp;
}

//Adjust upward
void Adjustup(HPDataType* a, int child)
{
assert(a);

int parent = (child - 1) / 2;
while (child>0)
{
if (a[parent] > a[child])
{
Swap( & amp;a[parent], & amp;a[child]);
child = parent;
parent = (parent - 1) / 2;
}
else
{
break;
}
}
}

Adjust downward:

Thought: If we want to delete the node at the top (root) of the heap, if we delete it directly and then cover it forward, the order of the heap will change and it will no longer be a big heap (small heap), as shown in the figure. Here we need to use Adjust downward, first exchange the last data with the first data, and then delete the last data. This ensures that except for the root, the following nodes are all large piles (small piles);

Then use the root to exchange with the smaller of the two children, and repeat the above action downwards one at a time. The diagram is as follows:

Implementation code:

//Adjust downwards
void Adjustdown(HPDataType* a, int parent, int n)
{
assert(a);
int child = parent * 2 + 1;
while (child<n)
{
//Assume that the left child is small
if (child + 1<n & amp; & amp; a[child] > a[child + 1]) //Assumption error, correct it
{
child = child + 1;
}
if (a[child] < a[parent])
{
Swap( & amp;a[parent], & amp;a[child]);
parent = child;
child = child * 2 + 1;
}
else
{
break;
}
}
}

Full code: Heap.h Heap.c

Heap.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
#include<string.h>

#define HPDataType int


typedef struct Heap
{
//array to store data
HPDataType* a;
int size;
int capacity;
}Heap;

//Initialization function, two types
//Don't open the space first, then open it when you use it
void HeapInit(Heap* php);
//There is already an array of data. Open space first and put an array of data into the heap array.
void HeapInitArray(Heap* php,int* a,int n);

//Destroy the function to prevent memory leaks
void HeapDestory(Heap* php);
//Print function
void HeapPrintf(Heap* php);

//Upward adjustment function
void Adjustup(HPDataType* a, int child);
//Adjust function downwards
void Adjustdown(HPDataType* a, int child, int n);

//Function to insert data into the heap
void HeapPush(Heap* php, HPDataType x);
//Function that pops the root node in the heap
void HeapPop(Heap* php);

//Function to retrieve root node data
HPDataType HeapTop(Heap* php);

//Function to determine whether the heap is empty
bool HeapEmpty(Heap* php);

Heap.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "Heap.h"

void HeapInit(Heap* php)
{
assert(php);

php->a = NULL;
php->capacity = 0;
php->size = 0;

}

void HeapInitArray(Heap* php,int* a,int n)
{
assert(a);
assert(php);

php->a = (HPDataType*)malloc( n * sizeof(int));
if (php->a == NULL)
{
perror("malloc fail");
exit(-1);
}
memcpy(php->a, a, n * sizeof(int));

//Adjust the heap upward
for (int i = 1; i < n; i + + )
{
Adjustup(php->a, i);
}

php->size = n;
php->capacity = n;
}

void HeapDestory(Heap* php)
{
assert(php);

php->a = NULL;
php->capacity = php->size = 0;

}

void HeapPrintf(Heap* php)
{
assert(php);

for (int i = 0; i < php->size; i + + )
{
printf("%d ",php->a[i]);
}
printf("\
");
}

//exchange function
void Swap(HPDataType* x, HPDataType* y)
{
HPDataType tmp = *x;
*x = *y;
*y = tmp;
}

//Upward adjustment function
void Adjustup(HPDataType* a, int child)
{
assert(a);

int parent = (child - 1) / 2;
while (child>0)
{
if (a[parent] > a[child])
{
Swap( & amp;a[parent], & amp;a[child]);
child = parent;
parent = (parent - 1) / 2;
}
else
{
break;
}
}
}

//Adjust function downwards
void Adjustdown(HPDataType* a, int parent, int n)
{
assert(a);
int child = parent * 2 + 1;
while (child<n)
{
//Assume that the left child is small
if (child + 1<n & amp; & amp; a[child] > a[child + 1])
{
child = child + 1;
}
if (a[child] < a[parent])
{
Swap( & amp;a[parent], & amp;a[child]);
parent = child;
child = child * 2 + 1;
}
else
{
break;
}
}
}

//Insert function
void HeapPush(Heap* php, HPDataType x)
{
assert(php);

if (php->capacity == php->size)
{
int newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;
HPDataType* tmp = (HPDataType*)realloc(php->a, newcapacity * sizeof(HPDataType));
if (tmp == NULL)
{
perror("realloc fail");
exit(-1);
}
php->a=tmp;
php->capacity = newcapacity;
}
php->a[php->size] = x;
php->size + + ;

Adjustup(php->a,php->size-1);
}

//Delete the top node of the heap
void HeapPop(Heap* php)
{
assert(php);

Swap( & amp;php->a[0], & amp;php->a[php->size - 1]);
php->size--;

Adjustdown(php->a, 0,php->size);

}

//Function to take out the top data of the heap
HPDataType HeapTop(Heap* php)
{
assert(php);

return php->a[0];
}

//empty function
bool HeapEmpty(Heap* php)
{
assert(php);

return php->size;
}

The knowledge points of the article match the official knowledge files, and you can further learn related knowledge. Algorithm skill tree Home page Overview 57281 people are learning the system

1. The concept and structure of trees

Concepts of 1.1 trees

Related concepts:

1.2 tree representation

2. The concept and structure of binary trees

2.1 Concept of Binary Tree

Binary tree:

2.2 Two special binary trees

Full binary tree:

Complete binary tree:

3. Binary tree sequence structure and implementation

3.1 Binary tree sequence structure

Heap storage classification: large root heap, small root heap

3.2 Implementation of Binary Tree (Heap) Sequential Structure

Here we focus on the analysis of upward/downward adjustment functions

Adjust up:

Adjust downward:

Full code: Heap.h Heap.c