Binary tree chain structure

Don't put too much pressure on 🧡
Life is not a choice, but love 🧡

Preface

We have learned the sequential structure of binary tree —> Perfect binary tree 、 Pile up
But that's a special binary tree , For ordinary binary trees , It is not suitable to use sequential structure to store
Because there may be a lot of space waste , Such as ：

Many spaces in an array do not contain data ！

0️⃣ Rub your hands on a binary tree

// Rub your hands on a binary tree 
BTNode* CreateBinaryTree()
{
    
	BTNode* node1 = BuyNode(1);
	BTNode* node2 = BuyNode(2);
	BTNode* node3 = BuyNode(3);
	BTNode* node4 = BuyNode(4);
	BTNode* node5 = BuyNode(5);
	BTNode* node6 = BuyNode(6);

	
	node1->left = node2;
	node1->right = node4;
	node2->left = node3;
	node4->left = node5;
	node4->right = node6;

	// No assignment   Some are NULL

	return node1;	
}

int main()
{
    
	BTNode* root = CreateBinaryTree();
	return 0;
}

Get such a binary tree ：

1️⃣ Traversal of binary tree

First we need to know two nouns ： Depth first traversal and breadth first traversal

• Depth-first traversal

Depth-first traversal ：DFS

Along Depth of tree Traversing the nodes of the tree , As deep as possible Branches of the search tree . When the deepest point has been reached along a certain node （ Already empty ）, Then go back and traverse the other side of the node .

As shown in the figure, it is a depth first traversal

Depth first traversal is divided into The first sequence traversal , After the sequence traversal , In the sequence traversal
The difference is the order of access to the root node

• Breadth first traversal ：

Breadth first traversal BFS(Breadth-First-Search), That is, width first ,BFS It starts at the root node , Traverse the nodes of the tree along one layer of the tree , Traverse horizontally first .

1. Depth-first traversal

① The former sequence traversal

The order of preorder traversal is The operation of accessing the root node occurs before traversing its left and right subtrees
Pictured ：

Code ：
notes ： We use # Said empty , The preceding result should be 1 2 3 # # # 4 5 # # 6 # #

//  Preorder traversal of two tree 
void PreOrder_Traversal(BTNode* root)
{
    
	// If the node is an empty tree 
	if (root == NULL)
	{
    
		printf("# ");
		return;
	}

	// First visit   Root node data  --> The left subtree  -->  Right subtree 
	printf("%d ", root->val);// Access root node data 
	PreOrder_Traversal(root->left);// Look for zuozhu 
	PreOrder_Traversal(root->right);
}

Pre order print results ：

② In the sequence traversal

Empathy , Middle order traversal is The root node does not access , Go to find Zuozi tree first , After finding the left subtree, access the root , Then go to the right subtree
On the basis of preorder traversal Pictured ：

Code ：

// Middle order traversal of binary trees 
void InOrder_Traversal(BTNode* root)
{
    
	if (root == NULL)
	{
    
		printf("# ");
		return;
	}

	// First, the left sub tree  -->  root  -->  Right subtree 
	InOrder_Traversal(root->left);
	printf("%d ", root->val);
	InOrder_Traversal(root->right);
}

③ After the sequence traversal

After the sequence traversal ： Visit the left subtree first , Then visit the right subtree , After finding the left and right subtrees, you can visit the root node

// Postorder traversal of binary trees 
void PostOrder_Traversal(BTNode*root)
{
    
	if (root == NULL)
	{
    
		printf("# ");
		return;
	}

	// Left tree  -->  Right tree  -->  root 
	PostOrder_Traversal(root->left);
	PostOrder_Traversal(root->right);
	printf("%d ", root->val);
}

2. Breadth first traversal

Sequence traversal

Sequence traversal is a breadth first traversal , This traversal will first access the nodes of the same layer , Instead of going too far
But the structure of a binary tree is like this ：

Every root Only to find his left and right children , There is no sibling node to find siblings at each layer
So how do you do that ？

—— Using queues ！

We can use queues The nature of first in first out To realize the traversal of each layer

1. Root in line , And then out of the team , Put the left child of the root node left And the right child right The team
2. left When you're out of the team left->left and left->right The team
3. right When you're out of the team right->left and right->right The team
4. Continue the above process , Until the queue is empty

But the problem here is The queue data structure is required to complete sequence traversal
C The language has no library ！ So we can only write a queue data structure by ourselves ！

The implementation of queues is relatively simple , Bloggers will stop writing ~~

Sequence traversal code

/* *  Sequence traversal of binary tree  */
void TreeLevel(BTNode* root)
{
    
	Queue q;// Create a queue 
	QueueInit(&q);// Queue initialization 
	// If root It's empty , Then go straight back 
	if (root == NULL)
		return;
	// And then put root The root node push To queue 
	//  Be careful push Yes.   An entire node of the tree ： Because you need to use the copy of this node to find the next node ！（ recursive ）
	QueuePush(&q, root);
	//  Into the loop 
	while (!QueueEmpty(&q))// If the queue is not empty 
	{
    
		// Get the team leader element （ Copy of tree node pointer ）
		BTNode* front = QueueFront(&q);
		//  Get it and leave the team 
		// Print it first 
		printf("%d ", front->val);
		QueuePop(&q);
		
		// After the current node leaves the queue   Into the root Two child nodes of （ That is, the next level joins the team ）
		if (front->left)// If the left node is not empty , The team 
		{
    
			QueuePush(&q, front->left);
		}
		if (front->right)// The right node is not empty , The team ！
		{
    
			QueuePush(&q, front->right);
		}
		// If the left and right nodes are empty , So just put the front Just get out of the team .
	}
}

2️⃣ Find the number of nodes in the binary tree

Method 1

Because binary trees are implemented recursively , So if it is simply like a linked list , Define a local variable inside the function and calculate the number of nodes through traversal , There's a problem ： Each recursion creates a new local variable , In fact, this local variable does not count

So we can use a global variable to record the number of nodes
The idea is simple ： The former sequence traversal , If the node is not empty count++

int count = 0;// Define global variables 
void TreeSize1(BTNode* root)
{
    
	if (root == NULL)
	{
    
		return;
	}

	++count;
	TreeSize1(root->left);
	TreeSize1(root->right);
}

defects ：

1. In each call, the main function must be called first count clear 0, because count Is the value of the last node count , It has not been cleared ！
2. Multithreading problem ：count Global variable , May be used by multiple threads at the same time , Calculated in this way count There are problems. ！

Method 2

We can use Return value + Recursive method
That is to say Divide and conquer thoughts ：
root Number of nodes = 1 + root->left Number of nodes + root->right Number of nodes

/*  Method 2： Use return value  // The method of partition ！！ */
int TreeSize2(BTNode* root)
{
    
	return root == NULL ? 0 : 1 + TreeSize2(root->left) + TreeSize2(root->right);
}

3️⃣ Find the number of leaf nodes

Leaf nodes have a feature ：
Both the left child and the right child of the node are NULL
So this is a limitation of our traversal

1. If the node is empty return 0
2. If the left and right children of the node are empty ： return 1 （ It's a leaf node ）
3. If they are not satisfied , This indicates that the node being searched is not a leaf node , We recursively find the left and right children of the node

/*  Find the number of leaf nodes  */
int TreeLeafSize(BTNode* root)
{
    
	return root == NULL ? 0 : ((root->left == NULL && root->right == NULL) ? 1 : TreeLeafSize(root->left) + TreeLeafSize(root->right));
}

4️⃣ Please k The number of layer nodes

/*  The second fork is the tree k The number of layer nodes  */

int KLevelSize(BTNode* root, int k)
{
    
	assert(k >= 1);
	if (root == NULL)
	{
    
		return 0;
	}
	if (k == 1)
	{
    
		return 1;
	}
	// If  k It's not equal to 1  So continue recursion 
	return KLevelSize(root->left, k - 1) + KLevelSize(root->right, k - 1);
	
}

5️⃣ Find a node

/*  Find a node  */
BTNode* TreeFind(BTNode* root,BTDataType x)
{
    
	if (root == NULL)
	{
    
		return NULL;	
	}
	if (root->val == x)
	{
    
		return root;
	}
	//  Simple logic ：  Look for zuoshu first   Find and return , If you can't find it, go find the right tree , If you can't find it   Returns an empty  
	//  Each subtree goes like this ！
	BTNode* left = TreeFind(root->left, x);
	if (left)
		return left;
	BTNode* right = TreeFind(root->right, x);
	if (right)
		return right;


	// There is no need to look for the right tree here , Directly return the result of the right tree 
	//  Because the right tree also has two results ：1.  empty  ,2.  eureka 
	//return TreeFind(root->right, x);
	return NULL;


	// The following is a three purpose approach 
	/*return TreeFind(root->left, x) != NULL ? TreeFind(root->left, x) : TreeFind(root->right, x);*/

}

6️⃣ Find the depth of the binary tree

analysis ：
seek root The depth of the That is to find out 1 + The larger value of the depth of the left and right children

/*  Find the depth of the binary tree  */
int TreeDepth(BTNode* root)
{
    
	if (root == NULL)
	{
    
		return 0;
	}
	int left = TreeDepth(root->left);
	int right = TreeDepth(root->right);
	int max = left > right ? left : right;
	return 1 + max;
	//return left > right ? left + 1 : right + 1;
}

7️⃣ Destruction of binary tree

The most direct idea is Just traverse directly Destroy and release each node ！
however Use the following sequence ！！
Because if you use the preface , Destroy the root first. How can I find it About the children ？ Can not find ！

Use post order The order of destruction should be 3 2 5 6 4 1
We can print it before each destruction to verify whether it is correct

/*  Destruction of binary tree  */
void TreeDestory(BTNode* root)
{
    
	if (root == NULL)
		return;
	// If it's not empty 
	TreeDestory(root->left);
	TreeDestory(root->right);
	// Print it out before destroying it 
	printf("%d ", root->val);
	free(root);
}

8️⃣ Determine whether it is a complete binary tree

We know that the last layer of a complete binary tree is Numbered from left to right , The last layer cannot have a right subtree but no left subtree
The graph is an incomplete binary tree 3 Is empty after , And there are non empty nodes behind the empty nodes ！

So how to judge whether it is empty ？
We can use queues ！

If it's a completely binary tree It should be

Code

/*  Judge whether it is   Perfect binary tree */
bool BinaryTreeComplete(BTNode* root)
{
    
	Queue q;
	QueueInit(&q);

	if (root == NULL)//  A complete binary tree can also be an empty tree 
		return true;

	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
    
		// Take out   Team head 
		BTNode* front = QueueFront(&q);	
		//  And then out of the team 
		QueuePop(&q);
		if (front)
		{
    
			//  There is no need to judge front Whether the left and right of is empty   Air also needs to join the team 
			QueuePush(&q, front->left);
			QueuePush(&q, front->right);
		}
		else//  If front Empty direct break
		{
    
			break;
		}

		
	}

	// When you exit the loop   Description encountered an empty 
	//  Once again into the cycle   Find out if it is not empty 
	while (!QueueEmpty(&q))
	{
    
		BTNode* front = QueueFront(&q);
		QueuePop(&q);// You must first pop once   Otherwise, there will be a dead cycle ！
		//  If you encounter non empty   return false
		if (front)
		{
    
			QueueDestory(&q);
			return false;
		}
			
	}
	QueueDestory(&q);
	// Come here   explain   The first time I met empty, it was all empty 
	return true;


}

At the end

2022 / 06 / 06 Countdown to the college entrance examination ：1 God
This time last year, I was preparing for the college entrance examination tomorrow
This year, , My repeat students are nervously reviewing
Yes, I also failed the exam last year , But life is not determined by the college entrance examination
There is still a long way to go
Calm down , Don't think how difficult the college entrance examination is , Don't listen to something “ Thousands of troops cross the single wooden bridge ”
Just take the posture of doing exercises as usual to meet the exam
2022 Of candidates , College entrance examination refueling ！
May your future As you wish

Thank you for reading ~
️ It's not easy to code words , Give me a compliment ~️