Binary tree and heap building in C language

 

Catalog

Related concepts of binary tree

Binary tree related calculation formula

The creation of binary tree

Initialization of binary tree

Destruction of binary tree

The insertion of a binary tree

The deletion of binary trees

Judge whether the binary tree is empty and the number of binary tree elements

  Building the heap

---

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