IT company’s auspicious “tree” binary tree – (heap) C language creation

1. Tree concept and structure

?Basic concept

Tree is a non-linear data structure, which is a collection with hierarchical relationship composed of n (n>=0) finite nodes. It is called a tree because it looks like an upside-down tree, that is, with the roots pointing up and the leaves pointing down.

There is a special node called the root node, the root node has no predecessor node

Except for the root node, the rest of the nodes are divided into M (M>0) disjoint sets T1, T2, …, Tm, where each set Ti (1<= i <= m ) is another subtree whose structure is similar to that of a tree. The root node of each subtree has one and only one predecessor, and can have zero or more successors.

Thus, the tree is defined recursively.

Note: In the tree structure, there can be no intersection between subtrees, otherwise it is not a tree structure.

The following are some typical non-tree structures

?Proper noun for tree

After understanding the structure of the basic tree, there is a plate of appetizers below. Please taste it carefully

The following introduces some proper nouns in some trees, taking the tree in the following figure as an example

?The degree of a node: the number of subtrees contained in a node is called the degree of the node; as shown in the figure above: A is 6

?Leaf node or terminal node: A node with a degree of 0 is called a leaf node; as shown in the above figure: B, C, H, I… and other nodes are leaf nodes

?Non-terminal node or branch node: a node whose degree is not 0; as shown in the figure above: nodes such as D, E, F, G… are branch nodes

?Parent: If a node contains child nodes, this node is called the parent node of its child nodes; as shown above: A is the parent node of B

?Child node: The root node of the subtree contained in a node is called the child node of the node; as shown in the figure above: B is the child node of A

?Sibling nodes: Nodes with the same parent node are called sibling nodes; as shown above: B and C are sibling nodes

?Degree of the tree: In a tree, the degree of the largest node is called the degree of the tree; as shown in the figure above: the degree of the tree is 6

?Node level: starting from the definition of the root, the root is the first level, the child nodes of the root are the second level, and so on

?Tree height or depth: the maximum level of nodes in the tree; as shown above: the height of the tree is 4

?Cousin nodes: Nodes whose parents are on the same layer are cousins; as shown in the figure above: H and I are sibling nodes

?Ancestor of a node: all nodes on the branch from the root to the node; as shown in the figure above: A is the ancestor of all nodes

?Descendants: Any node in the subtree rooted at a node is called the descendant of the node. As shown above: all nodes are descendants of A

?Forest: A collection of m (m>0) disjoint trees is called a forest

? Tree representation

The tree structure is more complicated than the linear table, and it is more troublesome to store and express it. Since the value range is saved, the relationship between the nodes and the nodes should also be saved. In practice, there are many kinds of trees Representation methods such as: parent representation, child representation, child parent representation, and child sibling representation, etc.

Here we simply understand the most commonly used child brother notation.

Child sibling representation

Child brother representation, as the name implies, is a representation method with only children and brothers, that is, the father’s child address only saves the leftmost child, and the child’s brother address records his brother (for example: in The father at home wants to find you brothers and sisters to eat, the father only needs to find the eldest son, and then let the eldest son find his brothers and sisters)

We still use the old routine to explain with pictures:

The following is the process of code implementation

typedef int DataType;
struct Node
{
    struct Node* _firstChild1; // the first child node
    struct Node* _pNextBrother; // point to its next brother node
    DataType _data; // data field in the node
};

Binary, binary tree concept and structure

?Concept

A binary tree is a finite set of nodes, which consists of a root node plus two binary trees, also known as the left subtree and the right subtree ( or empty).

As can be seen from the figure above:

?The binary tree does not have a node with a degree greater than 2
?The subtrees of the binary tree are divided into left and right, and the order cannot be reversed, so the binary tree is an ordered tree

Note: For any binary tree, it is composed of the following situations

A binary tree in reality (also known as the mascot of an IT company)

Students will feel sacred when they see these two pictures, I will feel sacred.

And these “trees” can definitely be the mascots of ITcompanies! ! ! (Thai pants are spicy!!!)

?Special binary tree

? Full binary tree: A binary tree, if the number of nodes in each layer reaches the maximum value, then this binary tree is a full binary tree. That is to say, if a binary tree has K layers and the total number of nodes is 2^k-1, then it is a full binary tree.

?Complete binary tree: A complete binary tree is a very efficient data structure, and a complete binary tree is derived from a full binary tree. For a binary tree with a depth of K and n nodes, it is called a complete binary tree if and only if each node has a one-to-one correspondence with the nodes numbered from 1 to n in the full binary tree with a depth of K. It should be noted that a full binary tree is a special kind of complete binary tree.
Note: A full binary tree is also a special complete binary tree! ! !

?Properties of Binary Trees

?If the number of layers of the root node is specified as 1, then there are at most 2^(i-1) nodes on the i-th layer of a non-empty binary tree.

?If the number of layers of the root node is specified as 1, then the maximum number of nodes in a binary tree with depth h is 2^h-1.

?For any binary tree, if the degree is 0, the number of leaf nodes is n. , the number of branch nodes with degree 2 is n2, so there are n. =n2+1

?If the number of layers of the root node is specified as 1, the depth of a full binary tree with n nodes, h= log2(n + 1). (ps: log2(n + 1) is log with base 2, n + 1 is the logarithm)

?For a complete binary tree with n nodes, if all nodes are numbered from 0 according to the order of the array from top to bottom and from left to right, then for the node with the sequence number i:

1. If i>0, the parent number of the node at position i: (i-1)/2; i=0, i is the root node number, no parent node
2. If 2i + 1=n, otherwise there is no left child
3. If 2i + 2=n, otherwise there is no right child

?Storage structure of binary tree

A binary tree can generally be stored in two structures, a sequence structure and a chain structure.

Sequential storage

Sequential structure storage is to use arrays to store. Generally, arrays are only suitable for representing complete binary trees, because not complete binary trees will waste space. In reality, only heaps are stored in arrays, and we will explain specifically about heaps later. Binary tree sequential storage is physically an array, logically a binary tree.

chain storage

The linked storage structure of the binary tree means that a linked list is used to represent a binary tree, that is, a link is used to indicate the logical relationship of elements. The usual method is that each node in the linked list is composed of three fields, the data field and the left and right pointer fields. The left and right pointers are used to give the storage addresses of the link points where the left child and right child of the node are located. The chain structure is divided into binary chain and triple chain. At present, we generally use binary chain in our study. Later, we will learn high-level data structures such as red-black tree, which will use triple chain.

Code of the chain storage structure to a copy! ! !

typedef int BTDataType;
// binary chain
struct BinaryTreeNode
{
    struct BinTreeNode* _pLeft; // point to the left child of the current node
    struct BinTreeNode* _pRight; // point to the right child of the current node
    BTDataType _data; // current node value domain
}
// triple chain
struct BinaryTreeNode
{
    struct BinTreeNode* _pParent; // point to the parent of the current node
    struct BinTreeNode* _pLeft; // point to the left child of the current node
    struct BinTreeNode* _pRight; // point to the right child of the current node
    BTDataType _data; // current node value domain
};

3. Heap (concept and structure of heap)

concept

Ordinary binary trees are not suitable for storage in arrays, because there may be a lot of space waste. The complete binary tree is more suitable for sequential structure storage. In reality, we usually store the heap (a binary tree) in an array of sequential structures. It should be noted that the heap here is different from the heap in the virtual process address space of the operating system. One is the data structure and the other is the operation. A segment of an area in the system that manages memory.

Small pile:

If there is a set K = {}, put it All elements of are stored in the order of a complete binary tree
In a one-dimensional array, and satisfy: and i =0，1，2…. .., it is called a small heap, and the heap with the smallest root node is called a minimum heap or a small root heap.

Big pile:

If there is a set K = {}, put it All elements of are stored in the order of a complete binary tree
In a one-dimensional array, and satisfy: =K_{2*i + 2}” class=”mathcode” src=”//i2.wp.com/latex.csdn.net/eq?K_{i}>=K_{2*i & amp;plus;2}”> i =0，1，2…. .., it is called a large heap, and the heap with the largest root node is called the largest heap or the big root heap.

The nature of the heap:

?The value of a node in the heap is always not greater than or not less than the value of its parent node.

?The heap is always a complete binary tree.

heap implementation

Heap adjustment algorithm

Now we give an array, logically regarded as a complete binary tree. We can adjust it into a small heap through the downward adjustment algorithm starting from the root node. There is a prerequisite for the downward adjustment algorithm: The left and right subtrees must be a heap before they can be adjusted.

int array[] = {27,15,19,18,28,34,65,49,25,37};

? Code implementation:

void AdjustDown(int* a, int n, int parent)
{
int child = parent * 2 + 1; // Find the child through the parent node
\t
while (child < n) // When the child node exceeds the size of the array, then jump out of the loop
{
if (child < n - 1 & amp; & amp; a[child] < a[child + 1]) // find the largest child
{
child ++ ;
}
if (a[child] > a[parent]) // The largest one is compared with the parent, if it is larger (smaller) than the parent, the position will be exchanged
{
swap( &a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
return;
}
}
}

heap creation

Below we give an array, which logically can be regarded as a complete binary tree, but it is not a heap. Now we use an algorithm to build it into a heap. The left and right subtrees of the root node are not heaps, how do we adjust it? Here we start to adjust from the subtree of the first last non-leaf node, and adjust to the tree of the root node, and then we can adjust it into piles.

heap insertion

First insert a 10 to the end of the array, and then perform an upward adjustment algorithm until the heap is satisfied.

? Code implementation:

void AdjustUp(HPDataType* a, int child)
{
int parent = (child - 1) / 2;
while (child > 0)
{
if (a[child] > a[parent])
{
swap( &a[child], &a[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
return;
}
}
}

void HeapPush(HP* php, HPDataType x)
{
assert(php); //Prevent null pointers from being passed in
if (php->capacity == php->size) //When the space is not enough, expand the space
{
int newcapacity = (php->capacity == 0 ? 4 : php->capacity * 2);
HPDataType* tmp = (HPDataType*)realloc(php->a, newcapacity * sizeof(HPDataType));
if (tmp == NULL) //judging whether the expansion is successful
{
perror("realloc fail"); // return error message on failure
return;
}
php->a = tmp; //Initialize the expanded space
php->capacity = newcapacity;
}
php->a[php->size] = x;
php->size++;
AdjustUp(php->a, php->size - 1); // adjust data upward
}

Heap deletion

Delete the heap is to delete the data at the top of the heap, replace the data at the top of the heap with the last data, then delete the last data in the array, and then perform the downward adjustment algorithm.

Exchange the top element of the heap with the last element in the heap

Remove the last element in the heap

Adjust the top element of the heap down to meet the heap characteristics

? Code Implementation:

void AdjustDown(int* a, int n, int parent)
{
int child = parent * 2 + 1; // Find the child through the parent node
\t
while (child < n) // When the child node exceeds the size of the array, then jump out of the loop
{
if (child < n - 1 & amp; & amp; a[child] < a[child + 1]) // find the largest child
{
child ++ ;
}
if (a[child] > a[parent]) // The largest one is compared with the parent, if it is larger (smaller) than the parent, the position will be exchanged
{
swap( &a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
return;
}
}
}
void HeapPop(HP* php)
{
assert(php);
assert(!HeapEmpty(php));
swap( &php->a[php->size-1], &php->a[0]);
php->size--;
AdjustDown(php->a, php->size, 0);
}

Full code of the heap

?Heap.h file (header file)

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

typedef int HPDataType; //Define the type of the heap
typedef struct Heap //Create the initial structure of the heap
{
HPDataType* a;
int size;
int capacity;
}HP;

//Adjust the data up
void AdjustUp(HPDataType* a, int child);

//Adjust the data down
void AdjustDown(int* a, int n, int parent);

//Initialize the heap
void HeapInit(HP* php);

// Destruction of the heap
void HeapDestroy(HP* php);

// Insert data into the heap
void HeapPush(HP* php, HPDataType x);

// delete the data at the top of the heap
void HeapPop(HP* php);

// Pop the data from the top of the heap
HPDataType HeapTop(HP* php);

//Check if the heap is empty
bool HeapEmpty(HP* php);

// Calculate the size of the heap
int HeapSize(HP* php);

?Heap.c file

#define _CRT_SECURE_NO_WARNINGS 1
#include "Heap.h"
//Exchange the two data specified in the heap
void swap(HPDataType* x, HPDataType* y)
{
HPDataType tmp = *x;
*x = *y;
*y = tmp;
}
//Adjust the data up
void AdjustUp(HPDataType* a, int child)
{
int parent = (child - 1) / 2;
while (child > 0)
{
if (a[child] > a[parent])
{
swap( &a[child], &a[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
return;
}
}
}
//Adjust the data down
void AdjustDown(int* a, int n, int parent)
{
int child = parent * 2 + 1;

while (child < n)
{
if (child < n - 1 & & a[child] < a[child + 1])
{
child ++ ;
}
if (a[child] > a[parent])
{
swap( &a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
return;
}
}
}
//Initialize the heap
void HeapInit(HP* php)
{
assert(php);
php->a = NULL;
php->capacity = 0;
php->size = 0;
}
// Destruction of the heap
void HeapDestroy(HP* php)
{
assert(php);
free(php->a);
php->a = NULL;
php->capacity = 0;
php->size = 0;
}

// Insert data into the heap
void HeapPush(HP* php, HPDataType x)
{
assert(php);
if (php->capacity == php->size)
{
int newcapacity = (php->capacity == 0 ? 4 : php->capacity * 2);
HPDataType* tmp = (HPDataType*)realloc(php->a, newcapacity * sizeof(HPDataType));
if (tmp == NULL)
{
perror("realloc fail");
return;
}
php->a = tmp;
php->capacity = newcapacity;
}
php->a[php->size] = x;
php->size++;
AdjustUp(php->a, php->size - 1);
}
// delete the data at the top of the heap
void HeapPop(HP* php)
{
assert(php);
assert(!HeapEmpty(php));
swap( &php->a[php->size - 1], &php->a[0]);
php->size--;
AdjustDown(php->a, php->size, 0);
}
// Pop the data from the top of the heap
HPDataType HeapTop(HP*php)
{
assert(php);
return php->a[0];
}
//Check if the heap is empty
bool HeapEmpty(HP* php)
{
return php->size == 0;
}
// Calculate the size of the heap
int HeapSize(HP* php)
{
return php->size;
}

?Test.c file

#define _CRT_SECURE_NO_WARNINGS 1
#include "Heap.h"
int main()
{
HP hp;
HeapInit( &hp);
int a[] = { 65,100,70,32,50,60 };
for (int i = 0; i < sizeof(a) / sizeof(int); + + i)
{
HeapPush( &hp, a[i]);
}
while (!HeapEmpty( &hp))
{
int top = HeapTop( &hp);
printf("%d\
", top);
HeapPop( &hp);
}

return 0;
}

The result of the operation is as follows to generate a large heap