Binary tree (chained structure storage)

Personal business card:

About the author: A sophomore student who is willing to share what he has learned on the road of study.
Personal homepage: GOTXX
Personal WeChat: ILXOXVJE
This article is original by GOTXX and first published on CSDN
Column series: Learning C language from scratch —– The road to learning data structures
Word of the day: If you are not particularly lucky, then please work extra hard!
—————-

Article introduction:

This article is a continuation of the previous article. It mainly writes about the binary tree chain structure and the implementation of related function codes, including the front, middle, and post-order traversal, level-order traversal, etc. of the binary tree Knowledge explained in detail!

If you think the article is good, I look forward to your one-click triple connection. Your encouragement is the source of my creative motivation. Let’s work together, run together, and let’s meet at the top! ! !

1. The front, middle and back order of binary trees

Preorder:Visit the root, left subtree, and right subtree in order of access

In-order: Visit the left subtree, root, and right subtree in sequence according to the access order

Postorder: Visit the left subtree, right subtree, and root in sequence according to the access order

Layer sequence: traverse layer by layer;

Take the above picture as an example: (N means NULL)

Preorder: 1 2 4 N N 5 N N 3 6 N N 7 N N

Middle order: N 4 N 2 N 5 N 1 N 6 N 3 N 7 N

Sequence: N N 4 N N 5 2 N N 6 N N 7 3 1

Sequence: 1 2 3 4 5 6 7

2. Code implementation of front, middle and back order traversal of binary tree (recursion)

Preorder traversal code:

void PrevPrintf(BTNode* root)
{
if (root == NULL)
{
printf("N ");
return;
}

printf("%d ",root->val);
PrevPrintf(root->left);
PrevPrintf(root->right);

}

In-order traversal code:

void InPrintf(BTNode* root)
{
if (root == NULL)
{
printf("N ");
return;
}

InPrintf(root->left);
printf("%d ", root->val);
InPrintf(root->right);

}

Post-order traversal code:

void PostPrintf(BTNode* root)
{
if (root == NULL)
{
printf("N ");
return;
}

PostPrintf(root->left);
PostPrintf(root->right);
printf("%d ", root->val);

}

2. Implement several functions

1. Find the number of nodes in the tree

int TreeSize(BTNode* root);

Code ideas:

To find the nodes of the tree, you can first add the nodes of the left and right subtrees, and to find the nodes of the left and right subtrees, you can first add the nodes of the left and right subtrees of the left and right subtrees;

Implementation code:

?
//The number of nodes
int TreeSize(BTNode* root)
{
if (root == NULL)
return 0;

return TreeSize(root->left) + TreeSize(root->right) + 1;
}

?

2. Find the number of leaf nodes in the tree

int TreeLeafSize(BTNode* root);

Code ideas:

The characteristics of leaf nodes are: both left and right subtrees are NULL;

When the root node is NULL, 0 is returned directly;

When the left and right subtrees are both NULL, return 1,

If the above conditions are not met, continue to recurse the left and right subtrees of the current node;

Implementation code:

//Number of leaf nodes
int TreeLeafSize(BTNode* root)
{
if (root == NULL)
return 0;
if (root->left == NULL & amp; & amp; root->right == NULL)
return 1;

return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}

3. Find the number of nodes at the kth level in the tree

int TreeKLevel(BTNode* root);

Code ideas:

For the first layer, the number of nodes in the k-th layer is found, but for the second layer, the number of nodes in the k-1th layer is found, and for the second layer, the number of nodes in the k-th layer is found. By analogy, for k-1 layer, it is to find the number of nodes in the second layer;

Implementation code:

//Nodes of the kth layer
int TreeKLevel(BTNode* root, int k)
{
assert(k > 0);

if (root == NULL)
return 0;

if(k==1)
return 1;

return TreeKLevel(root->left, k - 1) + TreeKLevel(root->right, k - 1);

}

4. Find values in the tree

BTNode* TreeFind(BTNode* root)

Code ideas:

Compare with the root first. If it is not the root, then look for it in the left subtree. If the left subtree is not found, then look for it in the right subtree

Code implementation:

BTNode* FindBinaryTreeX(BTNode* root, int x)
{
if (root == NULL)
return;
if (root->val == x)
return root;

BTNode* ret = NULL;
ret = FindBinaryTreeX(root->left, x);

//If ret is not empty, it means it is found and returns directly without going to the other side to find it.
if (ret)
return ret;

ret = FindBinaryTreeX(root->right, x);
if (ret)
return ret;

//After searching, if not found, return empty
return NULL;
}

5. Level-order traversal of binary trees

void BinaryTreeLevelOrder(BTNode* root)

Code ideas:

Taking advantage of the first-in-first-out feature of the queue, first put the root node in, take out the front number of the queue, print it, and then pop the root node out of the queue, and then put the left and right subtrees of the node into it, as shown in the figure :

Code implementation:

void BinaryTreeLevelOrder(BTNode* root)
{
Qu1p;

//Queue initialization
QueueInit( & amp;p);
//If the root node is not empty, put the root into the queue
if(root)
QueuePush( & amp;p, root);

while (!QueueEmpty( & amp;p))
{
BTNode* front = QueueFront( & amp;p);
QueuePop( & amp;p);
printf("%d ",front->val);
if(front->left!=NULL)
QueuePush( & amp;p, front->left);
if (front->right!= NULL)
QueuePush( & amp;p, front->right);
}
//Queue destruction
QueueDestory( & amp;p);
}

6. Destruction of binary trees

void BinaryTreeDestory(BTNode** root)

Code implementation

//Binary tree destruction
void BinaryTreeDestory(BTNode* root)
{
if (root == NULL)
return;

BinaryTreeDestory(root->left);
BinaryTreeDestory(root->right);
free(root);

//Here root is a formal parameter, changing it will not change the actual parameters;
root = NULL;
}