当前位置：网站首页>On binary tree

On binary tree

2022-06-29 23:26:00 【c.Coder】

Preface ：

The binary tree is “ Trees ” A special form of , So before you know the binary tree , We need to understand some noun concepts about trees first , In order to better learn the binary tree

The definition of a tree ： Trees are n(n>=0) A finite set of nodes , And the subtrees are disjoint , Each node has and only has one parent

Some noun concepts about trees ：

Degree of node
The number of subtrees contained in a node is the degree of that node
The degree of a tree
In a tree , The degree of the largest node is called the degree of the tree
Leaf node
Degree is 0 The node of （ Terminal node ）
Child node
The root node of the subtree contained in a node is called the child node of the node
Parent node
If a node has child nodes , Then this node is called the parent node of its child node
Brother node
Nodes with the same parent node are called brother nodes
Hierarchy of nodes
Define from root , The root is the first layer , The child node of the root is the second layer , And so on
The height of the tree
That is, the maximum level of nodes in the tree

After understanding the basic concepts of trees , Let's take a look at the special properties of binary trees

On some special properties of binary trees ：

Suppose the height of a full binary tree is h, Then the number of nodes is ：N = 2^h - 1
Suppose there is N Nodes , Then the height of the binary tree is ：h= log(N+1)
Degree is 0 The node ratio of is 2 The number of nodes is one more （n0=n2+1）
The number ratio of leaf nodes is 2 The number of nodes is one more
First of all 、 Property proof of two points ：
The number of nodes in the first layer is 2^0, The number of nodes in the second layer is 2^1, The number of nodes in the third layer is 2^2…, The total number of nodes is 2^0 + 2^1 + 2^2 + … +2^(h-1) = N According to the sum formula of the sequence of proportional numbers, we can get ：N = 2^h - 1 ---> h= log(N+1)
Remember the third property , Common to any binary tree

Next, let's take a look at the more special binary tree in the binary tree

Full binary tree
Every floor is full （ The degree of each layer is 2）
A full binary tree is a special kind of complete binary tree （ Complete and full binary tree ）
Perfect binary tree
Except for the last layer of dissatisfaction , Every floor above is full （ front h-1 The layers are full ）,
But the nodes of the last layer from left to right are continuous
Search binary trees
Any tree , Left subtree val The value is bigger than the root val It's worth less , The right subtree is bigger than the root ;
AVL A tree is a balanced search tree , The left and right subtrees tend to balance , The height difference shall not be greater than 1

After knowing the properties of the basic binary tree , Learning as a data structure , Then it comes to how to traverse the binary tree , The general binary tree is not suitable for storing data （ Efficiency and complexity are too high , No practical significance ）, Therefore, in the chapter of basic binary tree, we do not involve the addition, deletion, search and modification of binary tree , But first learn to traverse .

tips： The structure of the tree itself is a recursive structure ： root subtree … The subtree is divided into roots subtree … So the divide and conquer algorithm is used to solve the related problems of the tree （ recursive ） To solve

The traversal methods of binary trees are mainly divided into the following three types ：
ps： Any binary tree must be divided into three parts ： The root node , The left subtree , Right subtree
Depth-first traversal
Recursive traversal , It mainly uses divide and conquer algorithm , Solve problems recursively
（ Through the preface / In the following order + The result of middle order traversal can restore a whole binary tree ）
The former sequence traversal （ First root through ）
That is, access the root first , Then visit zuozhu , Visit the right subtree
When accessing the left subtree , The left subtree is also a binary tree , That is, it is similar to the scale of the original problem , So, first visit the root , Then visit zuozhu , Visit the right subtree , And so on , Until you access the child nodes of the leaf node （ The left subtree is empty , The right subtree is empty ）, That is, if the accessed root is empty, it will return
Algorithm implementation source code ：
void PrevOrder(BTNode *Tree)
{
   if(!Tree)
   {
       printf("NULL ");
       return ;
   }
   printf("%c ",Tree->val);// Accessing the node values of a binary tree 
   PrevOrder(Tree->left);
   PrevOrder(Tree->right);
}
In the sequence traversal （ Middle root traversal ）
That is, first visit the left subtree , Revisit the root , Visit the right subtree
Algorithm implementation source code
void InOrder(BTNode *Tree)
{
   if(!Tree)
   {
       printf("NULL ");
       return ;
   }
   InOrder(Tree->left);
   printf("%c ",Tree->val);// Accessing the node values of a binary tree 
   InOrder(Tree->right);
}
After the sequence traversal （ Back root traversal ）
Visit the left subtree first , Visit the right subtree , Finally, visit Gen
The access process is similar to the previous sequence , It is also necessary to keep dividing until the sub problem cannot be divided
Algorithm implementation source code
void PostOrder(BTNode *Tree)
{

   if(!Tree)
   {
       printf("NULL ");
       return ;
   }
   PostOrder(Tree->left);
   PostOrder(Tree->right);
   printf("%c ",Tree->val);// Accessing the node values of a binary tree 
}
Breadth first, convenience
Non recursive traversal
The core idea ： Traversal using the queue first in first out feature , The key is that the data of the upper layer brings the data of the lower layer
Sequence traversal
First put the root into the queue , Then, if the queue is not empty, the header data will be taken out , Judge the left subtree and the right subtree at the same time ( The root node ) Is it empty , If not be empty , Then the corresponding nodes are in turn ( The left subtree , Right subtree ) Queue entry , Go through each layer in turn .
Algorithm implementation source code
void LevelOrder(BTNode *Tree)
{
    if(!Tree)
        return ;
    queue<char> q;// Traverse the use queue 
    q.push(Tree->val);
    while(!q.empty())
    {
        char ch = q.front();
        printf("%c ",ch);
        q.pop();
        LevelOrder(Tree->left);
        LevelOrder(Tree->right);
    }
}

The basic structure of binary tree is the above content , Finally, let's look at the representation of trees

General tree representation
Left child right brother
No matter how many children there are , Each has only two pointers
One keeps the first child , A brother who keeps his right
Parenting
Express in an array , Only the subscript of the parent node is stored in the array .
Representation of binary tree
Binary chain or Trident chain
Binary chain ： Two nodes , Point to their left and right children respectively
Trident chain ： Three nodes , Point to the left child , Right child and parent node

Last, last , Although it is the last , But it is also a very important knowledge point ： Pile up

Heap is also a kind of complete binary tree , It is just a data structure visualized by an array
The logical structure of the heap is a complete binary tree , The physical structure is an array

First, because the binary tree is stored in an array , Let's first see how they find the parent node / The child nodes of the

The following relationship runs through the data structure of the heap ：
Relationship between subscript parent and child nodes
leftChild = parent*2+1
rightChild = parent*2+2
parent = (child-1)/2

About heaps , There are two types of heap structures

Big pile top
The keyword of any node is the maximum of all nodes in its subtree
Small cap pile
The keyword of any node is the minimum of all nodes in its subtree

After understanding the heap structure , How do we build a heap , Here we will learn about two algorithms related to heap creation ：

Adjust the algorithm up & Adjust the algorithm down

Adjust the algorithm up (AdjustUp)： More commonly used to insert data into the heap
Algorithmic thought ： This algorithm is used when inserting data into the heap , Keep the overall structure of the heap .
namely ： If you randomly insert a number into a small heap , The structure of the small heap remains unchanged after inserting data
from From the bottom to the top adjustment （ In fact, only all the ancestor nodes of the inserted node are adjusted ）
Start with the last data , Compare with parent node , Keep changing up , Until you get to the right place
Algorithm implementation source code
void AdjustUp(HPDataType* a, int n, int child)
{
	int parent;
	assert(a);
	parent = (child-1)/2;
	//while (parent >= 0)
	while (child > 0)
	{
        // If the child is bigger than the father , swapping 
		if (a[child] > a[parent])
		{
			Swap(&a[parent], &a[child]);
			child = parent;
			parent = (child-1)/2;
		}
		else
		{
			break;
		}
	}
}
Adjust the algorithm down (AdjustDown)： More commonly used for from the heap “ Delete ” data
The premise of using this algorithm ： When building a small pile , The left and right trees are small piles ; When building a pile , There are a lot of trees on the left and right
Algorithmic thought ：（ Build a small pile ） Adjust from top to bottom
Start at the root node , Choose the younger child to compare with the father , If you are younger than your father, exchange with your father
Then continue to adjust down , Until it is adjusted to the leaf node , Or when the left and right children are younger than the father, it also indicates that the adjustment is completed , Out of the loop, too
Algorithm implementation source code
void AdjustDown(HPDataType* a, int n, int root)
{
	int parent = root;
	int child = parent*2+1;
	while (child < n)
	{
		//  Choose the larger of the left and right children's papers 
		if (child+1 < n 
			&& a[child+1] > a[child])
		{
			++child;
		}
 
		// If the child is bigger than the father , Conduct adjustment exchange  
		if(a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent*2+1;
		}
		else
		{
			break;
		}
	}
}
Implementation points of the two algorithms ： Pay attention to the subscript of the parent node or child node , Avoid crossing borders