[one · data | chained binary tree]

All in all

   Simple implementation of chain binary tree (C Language )

  
  

The whole model

BinaryTree.c

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include"Queue.h"




typedef int BTDataType;
typedef struct BinaryTreeNode
{
    
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
	BTDataType data;
}BTNode;


// The creation of a single node in a binary tree 
BTNode* BuyNode(BTDataType x)
{
    
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	assert(node);
	node->data = x;
	node->left = node->right = NULL;
	return node;
}




//
// The former sequence traversal 
void PreOrder(BTNode* root)
{
    
	if (root == NULL)// If it is empty, return 
	{
    
		printf("# ");
		return;
	}
	printf("%d ", root->data);// Visit root first 
	PreOrder(root->left);// Then visit zuozhu 
	PreOrder(root->right);// Finally, visit the right subtree 
	// Recursion problem 
}

// In the sequence traversal 
void InOrder(BTNode* root)
{
    
	if (root == NULL)
	{
    
		printf("# ");
		return;
	}
	InOrder(root->left);// Visit the left subtree first 
	printf("%d ", root->data);// Revisit the root 
	InOrder(root->right);// Finally, visit the right subtree 
}

// After the sequence traversal 
void PostOrder(BTNode* root)
{
    
	if (root == NULL)
	{
    
		printf("# ");
		return;
	}
	PostOrder(root->left);// Visit the left subtree first 
	PostOrder(root->right);// Then visit the right subtree 
	printf("%d ", root->data);// Finally, visit Gen 
}
//







//
// Sequence traversal of binary tree ： You need to use queues to help complete , Stored in the queue are pointers to binary tree nodes ( reflection ： Why is this the type of data stored ？)
void LevelOrder(BTNode* root)
{
    
	Queue q;
	QueueInit(&q);
	if (root)// When the current node of the tree is not empty 
	{
    
		QueuePush(&q, root);// Put the pointer to the node of the tree in the queue 
	}
	while (!QueueEmpty(&q))// When the queue is not empty 
	{
    
		BTNode* front = QueueFront(&q);// Out of line header data （ Out of the root node ）
		printf("%d ", front->data);// Print the nodes of the binary tree at this time 
		QueuePop(&q);// Delete header data 
		// Notice here QueuePop The meaning of , What is deleted is the queue head node , Instead of nodes in the actual binary tree 
		// This means that we only use the characteristics of queues to assist in the sequence traversal of binary trees , I don't care about how the bottom of the queue is implemented ( Low coupling and high cohesion ).

		if (front->left)// Enter the data of the next layer of the current node in the queue 
		{
    
			QueuePush(&q, front->left);
		}
		if (front->right)
		{
    
			QueuePush(&q, front->right);
		}
	}
	QueueDestroy(&q);
}
//






//
// Determine whether a binary tree is a complete binary tree 
// Ideas ： The complete binary tree was first encountered NULL after , All subsequent nodes are NULL
int TreeComplete(BTNode* root)
{
    
	Queue q;
	QueueInit(&q);

	if (root)// When the current node of the tree is not empty 
	{
    
		QueuePush(&q, root);// Put the pointer to the node of the tree in the queue 
		//（ You can also put a single node of a binary tree , That is, the structure copy is stored in the queue , But the structure itself occupies a large memory space , Therefore, it is better to select the pointer corresponding to the structure ）
	}

	while (!QueueEmpty(&q))// When the queue is not empty 
	{
    
		BTNode* front = QueueFront(&q);// Out of line header data （ Out of the root node ）
		QueuePop(&q);// Delete header data 

		if (front)// If the current node is not NULL, Then continue to store the node pointer in the queue 
		{
    
			QueuePush(&q, front->left);
			QueuePush(&q, front->right);
		}
		else
		{
    
			break;// If the current node is NULL, Then jump out of sequence traversal , Just judge whether all the queued pointers from this node are empty .
		}
	}

	//1、 When first encountered in the queue NULL when , If all subsequent pointers are NULL, Is a complete binary tree 
	//2、 If there is a non null condition in the subsequent pointer , Then incomplete binary tree 
	while (!QueueEmpty(&q))
	{
    
		BTNode* front = QueueFront(&q);
		QueuePop(&q);

		if (front )
		{
    
			QueueDestroy(&q);
			return false;
		}
	}

	QueueDestroy(&q);
	return true;
}
//





//
// Find the total number of nodes in the binary tree 
// Ideas ： Based on the traversal of binary tree , Define a global variable for counting ( The variable used for counting here must be a global variable )
int count = 0;
void BinaryTreeSize(BTNode* root)
{
    
	if (root == NULL)
	{
    
		return;
	}
	// The traversal here can be in the previous order 、 Middle preface 、 Choose one of the following .
	count++;// This sentence is equivalent to the printing of the current node in traversal ( It's just that the printing here is replaced by counting )
	BinaryTreeSize(root->left);// This sentence is equivalent to traversing the left subtree 
	BinaryTreeSize(root->right);// This sentence is equivalent to traversing the right subtree 
}


// Find the total number of nodes in the binary tree · Improve your thinking 
// Ideas ： Divide and conquer algorithm 
int BinaryTreeSize2(BTNode* root)
{
    
	return root == 0 ? 0 :
		(BinaryTreeSize2(root->left) + BinaryTreeSize2(root->right)+1);
	// Node Statistics ： The total node of the left subtree + Total node of right subtree + The root node 
	// According to the idea of divide and rule , Take each node and its left and right children as the minimum unit , Finally, the function recurses to the leaf node , That is, two children root->left and root->right by NULL when , here +1 What counts is itself .
	// When there are child nodes , The function will continue to recurse until the above situation is counted to itself , When all values are returned layer by layer, the total number is counted .

	// An example of the above ：
	// For layers of recursion ： If the school wants to count the total number of students , Just assign the task to each department , Each department will assign tasks to counselors of each grade , The counselor assigns the task to the class monitor , The monitor will inform the dormitory head .
	// For the return layer by layer after recursion ： The monitor gets the total number of people in a class through the report of the dormitory head , The counselor gets the total number of students in each grade according to the report of the monitor of each class , The number of counselors in each grade is summed up to get the number of a department , The total number of students in each department is calculated .
}
//








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


// If you use global variables ：
void BinaryTreeLeafSize1(BTNode* root)
{
    
	if (root == NULL)
		return;
	if (root->left == NULL && root->right == NULL)
		count++;
	BinaryTreeLeafSize1(root->left);
	BinaryTreeLeafSize1(root->right);
}
//





//
// Find the second in a binary tree K Total number of nodes in the layer 
// Ideas ： Turn it into a sub problem 
// Require the second in the binary tree K Total number of nodes in the layer , That is, find the number of left subtree K-1 Total number of layer nodes + The... In the right subtree K-1 Total number of layer nodes 
int TreeKLevelSize(BTNode* root,int k)// It is considered here that K≥1, That is, count from the first layer 
{
    
	assert(k >= 1);

	if (root == NULL)
	{
    
		return 0;
	}

	if (k == 1)//K Not less than 0, Because here when K==1 Trigger when if Statement returns ,assert The assertion at is to ensure that K Not any number 
	{
    
		return 1;
	}
	
	return TreeKLevelSize(root->left,k-1) + TreeKLevelSize(root->right,k-1);// In recursion, the number of layers decreases 

}
//




//
// Find the depth of the binary tree 
// Ideas ： It is still a sub problem of divide and rule , But the above is to find the total number of nodes , That is to add , Here is the branch that finds the deepest depth , Comparison .
int  BinaryTreeDepth(BTNode* root)
{
    
	if (root == NULL)
		return 0;
	int ret1 = BinaryTreeDepth(root->left);
	int ret2 = BinaryTreeDepth(root->right);
	return ret1 > ret2 ? ret1+1 : ret2+1;
}
//




//
// The binary tree lookup value is X The node of ( Additional explanation : If there are multiple qualified values , Just return the first found )
// Ideas ： Traverse the binary tree ,
BTNode* TreeFind(BTNode* root, BTDataType x)
{
    
	if (root == NULL)// If root , It returns null 
	{
    
		return NULL;
	}

	if (root->data == x)// For the current node , If you find , Then return to the corresponding node 
	{
    
		return root;
	}

	BTNode* ret1 = TreeFind(root->left, x);// If the current node is not found , Then find the left subtree of the current node 
	if (ret1)// Add... Here if Judgment statement , Then judge the value of the left subtree alone , In this way, if there is a target value in the left subtree , You don't have to traverse the right subtree to find .
		return ret1;
	BTNode* ret2 = TreeFind(root->right, x);// If the left subtree of the current node is not found , Then find the right subtree of the current node 
	if (ret2)
		return ret2;
	// Although you can also use middle order or post order , But if the current root node is the target node , Use the middle order 、 The next sequence will traverse the subtree first and then access the root , That is, a few more steps 
	// Using the preamble will access the root node first and then its subtree , Relatively better in efficiency .

	return NULL;// I can't even find it 
}
//






//
// Destruction of binary tree 
// paraphrase ： It is convenient to destroy the binary tree nodes in the subsequent traversal 
void DestroyTree(BTNode* root)
{
    
	if (root == NULL)
		return;

	// Destroy the left subtree 
	DestroyTree(root->left);
	// Destroy right subtree 
	DestroyTree(root->right);
	// Destroy the root node 
	free(root);

}
//







// Hand rubbed binary tree 
BTNode* CreatBinaryTree()
{
    
	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;
	node2->right = node6;
	node4->left = node5;
	

	return node1;
}




int main()
{
    
	// Rub the binary tree with your hands 
	BTNode* root = CreatBinaryTree();

	// Traversal of binary tree 
	printf("Preorder Traversal：");
	PreOrder(root);
	printf("\n");

	printf("Inorder Traversal：");
	InOrder(root);
	printf("\n");

	printf("postorder Traversal：");
	PostOrder(root);
	printf("\n");



	// Count the total number of binary tree nodes 
	count = 0;// Details of using global variables , This is to prevent multiple calls to the node statistics function count Add up , Therefore, it is necessary to check count Zeroing .
	BinaryTreeSize(root);
	printf("BinaryTreeSize:%d\n", count);

	count = 0;
	BinaryTreeSize(root);
	printf("BinaryTreeSize:%d\n", count);
	// The above statistical methods still have problems , I will learn this knowledge when using multithreading 



	// Count the total number of binary tree nodes · Improved version of thinking 
	printf("BinaryTreeSize:%d\n", BinaryTreeSize2(root));



	// Count the total number of leaf nodes of binary tree 
	printf("Binarytree Size:%d\n", BinaryTreeLeafSize(root));

	count = 0;
	BinaryTreeLeafSize1(root);
	printf("Binarytree Size:%d\n", count);



	// Find the second in a binary tree K Total number of nodes in the layer 
	printf("KLevelSize K=2:%d\n", TreeKLevelSize(root, 2));
	printf("KLevelSize K=3:%d\n", TreeKLevelSize(root, 3));
	printf("KLevelSize K=4:%d\n", TreeKLevelSize(root, 4));



	// Find the node depth of binary tree 
	printf("BinarytreeDepth:%d\n", BinaryTreeDepth(root));



	// Sequence traversal of binary tree 
	printf("LevelOrder Traversal：");
	LevelOrder(root);

	// Determine whether a binary tree is a complete binary tree 
	printf("BinaryTreeComplete:%d \n", TreeComplete(root));


	// Destruction of binary tree 
	DestroyTree(root);

	return 0;
}

  
  

Queue.h

#pragma once
#define _CRT_SECURE_NO_WARNINGS

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


struct BinaryTreeNode;// Forward declaration , Solve the problem of header file inclusion 

// Define a single linked list as the implementation queue 
typedef struct BinaryTreeNode* QDataType;
typedef struct QueueNode
{
    
	struct QueueNode* next;
	QDataType data;
}QNode;

typedef struct Queue
{
    
	//QueueSize One of the ways to do it , Add a new variable for statistical nodes , Change as the queue changes 
	//int size;
	QNode* head;
	QNode* tail;// For the convenience of queue tail insertion , Re create a structure , Add tail pointer 
}Queue;

// Queue basic function interface ：
void QueueInit(Queue* pq);// Queue initialization 
void QueueDestroy(Queue* pq);// Queue destruction 
void QueuePush(Queue* pq, QDataType x);// Insert data at the end of the queue 
void QueuePop(Queue* pq);// The team leader deletes the data 
QDataType QueueFront(Queue* pq);// Extract header data 
QDataType QueueBack(Queue* pq);// Extract tail data 
bool QueueEmpty(Queue* pq);// Determines if the queue is empty 
int QueueSize(Queue* pq);// View the total number of queues 

  
  

Queue.c

#include"Queue.h"


void QueueInit(Queue* pq)
{
    
	assert(pq);// Initialize the queue node , Naturally, nodes cannot be null pointers 
	pq->head = pq->tail = NULL;
}


// Queue insertion , Tail insertion 
void QueuePush(Queue* pq, QDataType x)
{
    
	// There are two cases , One is the linked list ( queue ) It's empty time , The second is linked list ( queue ) When there are nodes in 
	// When the linked list is empty , Yes tail、head All have to be handled ; When there are nodes in the linked list ,head There is a definite point , Only need to tail To deal with ( Every link node ,tail The direction needs to follow the change )
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));// Open up new nodes , Note the difference between the single linked list and the sequential list 
	if (newnode == NULL)// Sentenced to empty 
	{
    
		perror("QueuePush::malloc");
		exit(-1);
	}
	// Processing data in nodes ：
	newnode->data = x;
	newnode->next = NULL;
	// Handle pointer relations to nodes ：
	if (pq->head == NULL)
	{
    
		pq->head = pq->tail = newnode;
	}
	else
	{
    
		pq->tail->next = newnode;// Node already exists , Just link the node relationship , And update the tail pointer to 
		pq->tail = newnode;//pq->tail->next
	}
}



// Queue delete , Head deletion ( Here we can see why single linked list is better , Insert the header in the sequence table to move the data , In the linked list, you only need to change the header pointer and release the corresponding node )
void QueuePop(Queue* pq)
{
    
	// Think about the problem ： Header deletion boundary , Because there are limited nodes , Header deletion has a lower limit 
	// Besides , To find the header node of the chain after the header is deleted , Delete the header by saving the next node , Loop down and eventually the head pointer will point to NULL,
	// At this time, the tail pointer tail Point to NULL The tail node of the front , This node has been free, There is tail The problem of pointing to a wild pointer , We need to pay attention to 
	assert(pq);// Used to check whether the pointer entered by the function parameter is null （ That is, it may not point to the linked list , And point NULL）
	assert(!QueueEmpty(pq));// Used to check whether the linked list itself is empty （ namely pq The pointer points to the linked list , But this is an empty linked list ）

	if (pq->head->next == NULL)// There is only one node left in the linked list , That is, the chain header pointer and tail pointer coincide here , This node next Point to NULL
	{
    
		free(pq->head);
		pq->head = pq->tail = NULL;// At this time, in order to prevent tail For the wild pointer , Both need to be left blank 
	}
	else// When there are multiple nodes in the linked list ( If the head node with sentinel position is used here , When the head is deleted to the lower limit, only the sentry position is left , There are some differences in details )
	{
    
		QNode* next = pq->head->next;// Save the next node after the header node 
		free(pq->head);// Head deletion 
		pq->head = next;// New head node 
	}
}


// Check linked list ( queue ) Function that is null or not 
bool QueueEmpty(Queue* pq)
{
    
	assert(pq);
	return pq->head == NULL;
}


// Propose queue header data 
QDataType QueueFront(Queue* pq)
{
    
	assert(pq);// The pointer itself is not empty 
	assert(!QueueEmpty(pq));// The linked list itself is not empty 
	return pq->head->data;
}

// Extract the data of the end node of the queue 
QDataType QueueBack(Queue* pq)
{
    
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->tail->data;
}


// Count the total number of queue data 
int QueuSize(Queue* pq)
{
    
	// If variables are not defined in the initial structure to count the number of nodes , Then you need to traverse the linked list and actively obtain （ Relatively inefficient ）
	assert(pq);
	QNode* cur = pq->head;
	int size=0;
	while (cur)
	{
    
		++size;
		cur = cur->next;
	}
	return size;
}


// Queue destruction 
void QueueDestroy(Queue* pq)
{
    
	assert(pq);
	QNode* cur=pq->head;
	while (cur)
	{
    
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;
}

  
  

Block mode

Test of hand rubbed binary tree

// Hand rubbed binary tree 
BTNode* CreatBinaryTree()
{
    
	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;
	node2->right = node6;
	node4->left = node5;
	

	return node1;
}

int main()
{
    
	// Rub the binary tree with your hands 
	BTNode* root = CreatBinaryTree();
	return 0;
}

  
  

Three traversal methods and their writing

Before the order 、 Middle preface 、 The following traversal is briefly introduced ：

   The code is as follows ：

//
// The former sequence traversal 
void PreOrder(BTNode* root)
{
    
	if (root == NULL)// If it is empty, return 
	{
    
		printf("# ");
		return;
	}
	printf("%d ", root->data);// Visit root first 
	PreOrder(root->left);// Then visit zuozhu 
	PreOrder(root->right);// Finally, visit the right subtree 
	// Recursion problem 
}

// In the sequence traversal 
void InOrder(BTNode* root)
{
    
	if (root == NULL)
	{
    
		printf("# ");
		return;
	}
	InOrder(root->left);// Visit the left subtree first 
	printf("%d ", root->data);// Revisit the root 
	InOrder(root->right);// Finally, visit the right subtree 
}

// After the sequence traversal 
void PostOrder(BTNode* root)
{
    
	if (root == NULL)
	{
    
		printf("# ");
		return;
	}
	PostOrder(root->left);// Visit the left subtree first 
	PostOrder(root->right);// Then visit the right subtree 
	printf("%d ", root->data);// Finally, visit Gen 
}
//

int main()
{
    
	// Rub the binary tree with your hands 
	BTNode* root = CreatBinaryTree();

	// Traversal of binary tree 
	printf("Preorder Traversal：");
	PreOrder(root);
	printf("\n");

	printf("Inorder Traversal：");
	InOrder(root);
	printf("\n");

	printf("postorder Traversal：");
	PostOrder(root);
	printf("\n");
	return 0;
}

   Result diagram ：

  
  

Before the order 、 Middle preface 、 Diagram of recursive part of post order traversal ：

   Before the order ：

// The former sequence traversal 
void PreOrder(BTNode* root)
{
    
	if (root == NULL)// If it is empty, return 
	{
    
		printf("# ");
		return;
	}
	printf("%d ", root->data);// Visit root first 
	PreOrder(root->left);// Then visit zuozhu 
	PreOrder(root->right);// Finally, visit the right subtree 
	// Recursion problem 
}

   Middle preface ：

// In the sequence traversal 
void InOrder(BTNode* root)
{
    
	if (root == NULL)
	{
    
		printf("# ");
		return;
	}
	InOrder(root->left);// Visit the left subtree first 
	printf("%d ", root->data);// Revisit the root 
	InOrder(root->right);// Finally, visit the right subtree 
}

   In the following order ：

// After the sequence traversal 
void PostOrder(BTNode* root)
{
    
	if (root == NULL)
	{
    
		printf("# ");
		return;
	}
	PostOrder(root->left);// Visit the left subtree first 
	PostOrder(root->right);// Then visit the right subtree 
	printf("%d ", root->data);// Finally, visit Gen 
}

  
  

Find the total number of binary tree nodes

Ideas ：

// Find the total number of nodes in the binary tree 
// Ideas ： Based on the traversal of binary tree , Define a global variable for counting ( The variable used for counting here must be a global variable )
int count = 0;
void BinaryTreeSize(BTNode* root)
{
    
	if (root == NULL)
	{
    
		return;
	}
	// The traversal here can be in the previous order 、 Middle preface 、 Choose one of the following .
	count++;// This sentence is equivalent to the printing of the current node in traversal ( It's just that the printing here is replaced by counting )
	BinaryTreeSize(root->left);// This sentence is equivalent to traversing the left subtree 
	BinaryTreeSize(root->right);// This sentence is equivalent to traversing the right subtree 
}

Train of thought improvement ：

// Find the total number of nodes in the binary tree · Improve your thinking 
// Ideas ： Divide and conquer algorithm 
int BinaryTreeSize2(BTNode* root)
{
    
	return root == 0 ? 0 :
		(BinaryTreeSize2(root->left) + BinaryTreeSize2(root->right)+1);
	// Node Statistics ： The total node of the left subtree + Total node of right subtree + The root node 
	// According to the idea of divide and rule , Take each node and its left and right children as the minimum unit , Finally, the function recurses to the leaf node , That is, two children root->left and root->right by NULL when , here +1 What counts is itself .
	// When there are child nodes , The function will continue to recurse until the above situation is counted to itself , When all values are returned layer by layer, the total number is counted .

	// An example of the above ：
	// For layers of recursion ： If the school wants to count the total number of students , Just assign the task to each department , Each department will assign tasks to counselors of each grade , The counselor assigns the task to the class monitor , The monitor will inform the dormitory head .
	// For the return layer by layer after recursion ： The monitor gets the total number of people in a class through the report of the dormitory head , The counselor gets the total number of students in each grade according to the report of the monitor of each class , The number of counselors in each grade is summed up to get the number of a department , The total number of students in each department is calculated .
}

  
  

The total number of leaf nodes in a binary tree

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


// If you use global variables ：
void BinaryTreeLeafSize1(BTNode* root)
{
    
	if (root == NULL)
		return;
	if (root->left == NULL && root->right == NULL)
		count++;
	BinaryTreeLeafSize1(root->left);
	BinaryTreeLeafSize1(root->right);
}
//

  
  

The second in a binary tree K Total number of nodes in the layer

//
// Find the second in a binary tree K Total number of nodes in the layer 
// Ideas ： Turn it into a sub problem 
// Require the second in the binary tree K Total number of nodes in the layer , That is, find the number of left subtree K-1 Total number of layer nodes + The... In the right subtree K-1 Total number of layer nodes 
int TreeKLevelSize(BTNode* root,int k)// It is considered here that K≥1, That is, count from the first layer 
{
    
	assert(k >= 1);

	if (root == NULL)
	{
    
		return 0;
	}

	if (k == 1)//K Not less than 0, Because here when K==1 Trigger when if Statement returns ,assert The assertion at is to ensure that K Not any number 
	{
    
		return 1;
	}
	
	return TreeKLevelSize(root->left,k-1) + TreeKLevelSize(root->right,k-1);// In recursion, the number of layers decreases 

}
//

  
  

Diagram of depth traversal of binary tree

//
// Find the depth of the binary tree 
// Ideas ： It is still a sub problem of divide and rule , But the above is to find the total number of nodes , That is to add , Here is the branch that finds the deepest depth , Comparison .
int  BinaryTreeDepth(BTNode* root)
{
    
	if (root == NULL)
		return 0;
	int ret1 = BinaryTreeDepth(root->left);
	int ret2 = BinaryTreeDepth(root->right);
	return ret1 > ret2 ? ret1+1 : ret2+1;
}
//

  
  

The binary tree lookup value is X The node of

//
// The binary tree lookup value is X The node of ( Additional explanation : If there are multiple qualified values , Just return the first found )
// Ideas ： Traverse the binary tree ,
BTNode* TreeFind(BTNode* root, BTDataType x)
{
    
	if (root == NULL)// If root , It returns null 
	{
    
		return NULL;
	}

	if (root->data == x)// For the current node , If you find , Then return to the corresponding node 
	{
    
		return root;
	}

	BTNode* ret1 = TreeFind(root->left, x);// If the current node is not found , Then find the left subtree of the current node 
	if (ret1)// Add... Here if Judgment statement , Then judge the value of the left subtree alone , In this way, if there is a target value in the left subtree , You don't have to traverse the right subtree to find .
		return ret1;
	BTNode* ret2 = TreeFind(root->right, x);// If the left subtree of the current node is not found , Then find the right subtree of the current node 
	if (ret2)
		return ret2;
	// Although you can also use middle order or post order , But if the current root node is the target node , Use the middle order 、 The next sequence will traverse the subtree first and then access the root , That is, a few more steps 
	// Using the preamble will access the root node first and then its subtree , Relatively better in efficiency .

	return NULL;// I can't even find it 
}
//

  
  

Sequence traversal

//
// Sequence traversal of binary tree ： You need to use queues to help complete , Stored in the queue are pointers to binary tree nodes ( reflection ： Why is this the type of data stored ？)
void LevelOrder(BTNode* root)
{
    
	Queue q;
	QueueInit(&q);
	if (root)// When the current node of the tree is not empty 
	{
    
		QueuePush(&q, root);// Put the pointer to the node of the tree in the queue 
	}
	while (!QueueEmpty(&q))// When the queue is not empty 
	{
    
		BTNode* front = QueueFront(&q);// Out of line header data （ Out of the root node ）
		printf("%d ", front->data);// Print the nodes of the binary tree at this time 
		QueuePop(&q);// Delete header data 
		// Notice here QueuePop The meaning of , What is deleted is the queue head node , Instead of nodes in the actual binary tree 
		// This means that we only use the characteristics of queues to assist in the sequence traversal of binary trees , I don't care about how the bottom of the queue is implemented ( Low coupling and high cohesion ).

		if (front->left)// Enter the data of the next layer of the current node in the queue 
		{
    
			QueuePush(&q, front->left);
		}
		if (front->right)
		{
    
			QueuePush(&q, front->right);
		}
	}
	QueueDestroy(&q);
}
//

  
  

Determine whether a binary tree is a complete binary tree

//
// Determine whether a binary tree is a complete binary tree 
// Ideas ： The complete binary tree was first encountered NULL after , All subsequent nodes are NULL
int TreeComplete(BTNode* root)
{
    
	Queue q;
	QueueInit(&q);

	if (root)// When the current node of the tree is not empty 
	{
    
		QueuePush(&q, root);// Put the pointer to the node of the tree in the queue 
		//（ You can also put a single node of a binary tree , That is, the structure copy is stored in the queue , But the structure itself occupies a large memory space , Therefore, it is better to select the pointer corresponding to the structure ）
	}

	while (!QueueEmpty(&q))// When the queue is not empty 
	{
    
		BTNode* front = QueueFront(&q);// Out of line header data （ Out of the root node ）
		QueuePop(&q);// Delete header data 

		if (front)// If the current node is not NULL, Then continue to store the node pointer in the queue 
		{
    
			QueuePush(&q, front->left);
			QueuePush(&q, front->right);
		}
		else
		{
    
			break;// If the current node is NULL, Then jump out of sequence traversal , Just judge whether all the queued pointers from this node are empty .
		}
	}

	//1、 When first encountered in the queue NULL when , If all subsequent pointers are NULL, Is a complete binary tree 
	//2、 If there is a non null condition in the subsequent pointer , Then incomplete binary tree 
	while (!QueueEmpty(&q))
	{
    
		BTNode* front = QueueFront(&q);
		QueuePop(&q);

		if (front )
		{
    
			QueueDestroy(&q);
			return false;
		}
	}

	QueueDestroy(&q);
	return true;
}
//

  
  

Destruction of binary tree

//
// Destruction of binary tree 
// paraphrase ： It is convenient to destroy the binary tree nodes in the subsequent traversal 
void DestroyTree(BTNode* root)
{
    
	if (root == NULL)
		return;

	// Destroy the left subtree 
	DestroyTree(root->left);
	// Destroy right subtree 
	DestroyTree(root->right);
	// Destroy the root node 
	free(root);

}
//