Various operations of C language data structure binary tree

Hello everyone who clicks on my article!

At the time of posting this article, I am a freshman student, and I will blog about my learning journey!

This is my second blog post about the manipulation of binary trees of C language data structures.

I hope you pay more attention to me and recommend me to your friends, I will post at least one article a week!

Next, I will decompose each operation and attach the source code at the end of the article (Visual Studio2022 runs perfectly)!

Let me show you the page first:

Let’s get straight to the point!

First, the various definitions at the beginning of the code:

#define _CRT_SECURE_NO_WARNINGS //With this, we can use scanf instead of scanf_s
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_NODE 50
typedef char ElemType;
typedef struct BTnode
{
ElemType data;
struct BTnode* Lchild, * Rchild;
}BTNode;

Second, it is the output of the tree node: (this will be often used in the subsequent output)

void visit(BTNode*T) //output operation
{
printf("%c", T->data); // We need to use %c because we set the input into the node is a letter
}

Three: Build a binary tree:

The method I use here is to first construct a full binary tree whose values in the nodes are all empty, that is to say, we have to fill in the data in the corresponding numbered node. Like this, fill in the data in the corresponding numbered node

Stop building when the node number is 0

BTNode* Create_BiTree() //Create a binary tree
{
BTNode* T, * p, * s[MAX_NODE]; //array stack
ElemType ch;
T = NULL;
int i, j;
system("cls");
while (1)
{
printf("Enter the number of the node:\\
");
scanf("%d", &i);
if (i == 0) break; //Stop building when the number of the input node is 0
printf("Enter the value of the node:\\
");
getchar(); //Prevent the Enter key from destroying the input
scanf("%c", &ch);
p = (BTNode*)malloc(sizeof(BTNode));
p->data = ch;
p->Lchild = p->Rchild = NULL; //constantly construct an empty complete binary tree
s[i] = p;
if (i == 1) T = p;
else {
j = i / 2;
if (i % 2 == 0)
s[j]->Lchild = p;
else
s[j]->Rchild=p;
}
i + + ;
}
system("cls");
printf("Enter successfully\\
");
return T;
}

Fourth, pre-order traversal of the binary tree (non-recursive)

void PreorderTraverse(BTNode* T)
/*Non-recursive pre-order traversal of the binary tree T*/
{
BTNode* s[MAX_NODE], * p,*q; // Simulate stack with array
int top=0;
p = T;
system("cls");
if (T == NULL) printf("The tree is an empty tree\\
");
else {
while (p & amp; & amp; top != -1)
{
visit(p);
q = p->Rchild;
if (q != NULL)
s[++top] = q;
p = p->Lchild;
if (p == NULL)
p = s[top--];
}
}
}

5. Inorder traversal of a binary tree (non-recursive)

void InorderTraverse(BTNode* T)
/*Non-recursive inorder traversal of a binary tree*/
{
BTNode* s[MAX_NODE], * p; //array simulation stack
int top = 0;
int flag = 1;
system("cls");
p = T;
if (T == NULL) printf("The tree is an empty tree\\
");
else {
do {
while (p)
{
s[++top] = p;
p = p->Lchild;
}
if (top == 0) flag = 0;
else {
p = s[top--];
visit(p);
p = p->Rchild;
}
} while (flag != 0);
}
}

6. Recursive post-order traversal:

void PostorderTraverse(BTNode* T)
/* Subsequent traversal of the binary tree T*/
{
if (T != NULL)
{
system("cls");
PostorderTraverse(T->Lchild);
PostorderTraverse(T->Rchild);
visit(T); /* visit the root node */
}
}

Seven, level traversal binary tree:

void LevelorderTraverse(BTNode* T) //level traversal binary tree
{
BTNode* DL[MAX_NODE], * p; //array simulation queue
int rear=0, front=0;
system("cls");
p = T;
if (p != NULL) //In fact, it exits when the tail of the queue points to NULL
{
DL[++ rear] = p;
while (front < rear)
{
p = DL[++front];
visit(p);
if (p->Lchild != NULL)
DL[ + + rear] = p->Lchild;
if (p->Rchild != NULL)
DL[ + + rear] = p->Rchild;
}
}
}

8. Find the depth of the binary tree:

int search_depth(BTNode* T)
{
BTNode* Queue[MAX_NODE], * p = T;
int front = 0, rear = 0, depth = 0, level;
/* level always points to the position of the last node of the access layer in the queue */
if (T != NULL)
{
Queue[ + + rear] = p; /* root node enqueue */
level = rear; /* root is the last node of level 1 */
while (front < rear)
{
p = Queue[++front];
if (p->Lchild != NULL) // the left child node is not empty, join the queue
Queue[ + + rear] = p->Lchild;
if (p->Rchild != NULL) // the right child node is not empty, join the queue
Queue[ + + rear] = p->Rchild;
if (front == level) // visit the last node of the current layer
{
depth++;
level = rear;
}
}
}
return depth;
}

9. Output leaf nodes and non-leaf nodes:

void leaves(BTNode* T)
/*Output leaf nodes and non-leaf nodes*/
{
BTNode* DL[MAX_NODE], * p = T; //array queue
int front = 0, rear = 0;
system("cls");
if (p != NULL)
{
DL[++ rear] = p;
front = 1;
while (front <= rear) {
if (p->Lchild == NULL & amp; & amp; p->Rchild == NULL)
printf("Leaf node: %c\\
", p->data);
else {
printf("Non-leaf node: %c\\
", p->data);
if (p->Lchild != NULL)
DL[ + + rear] = p->Lchild;
if (p->Rchild != NULL)
DL[ + + rear] = p->Rchild;
}
p = DL[++front];
}
}
}

10. Determine whether the binary tree is a complete binary tree:

int Judge(BTNode* T)//judging whether the binary tree is a complete binary tree (level traversal)
{
BTNode* DL[MAX_NODE],*p; //queue array
int rear = 0, front = 0;
system("cls");
p = T;
if (p != NULL)
{
DL[++ rear] = p;
while (front < rear) {
p = DL[++front];
if ( p->Lchild == NULL & amp; & amp; p->Rchild != NULL) //When the left subtree is empty and the right subtree is not empty, it does not meet the properties of a complete binary tree
return 0;
else {
if (p->Lchild != NULL)
DL[ + + rear] = p->Lchild;
if (p->Rchild != NULL)
DL[ + + rear] = p->Rchild;
}
}
}
return 1;
}

Eleven, the main function:

Made a menu:

int main()
{
BTNode* T = NULL;
char ch[10];
while (1)
{
printf("\\
============================================== =============\\
");
printf("| 1. Build a binary tree T |\\
");
printf("| 2. Use non-recursive pre-order traversal to output the nodes of tree T |\\
");
printf("| 3. Use non-recursive inorder traversal to output the nodes of tree T |\\
");
printf("| 4. Use the post-order traversal method to output the nodes of the tree T |\\
");
printf("| 5. Use hierarchical traversal to output the nodes of tree T |\\
");
printf("| 6. The depth of the output tree T |\\
");
printf("| 7. Output the leaf nodes and non-leaf nodes of tree T |\\
");
printf("| 8. Determine whether the binary tree is a complete binary tree (level traversal) |\\
");
printf("| 0. Exit the program |\\
");
printf("================================================ =========\\
");
printf("Please enter the operation to be performed:");
scanf("%s", ch);
if (strcmp(ch, "1") == 0)
T = Create_BiTree();
else if (strcmp(ch, "2") == 0)
PreorderTraverse(T);
else if (strcmp(ch, "3") == 0)
InorderTraverse(T);
else if (strcmp(ch, "4") == 0)
{
system("cls");
PostorderTraverse(T);
}
else if (strcmp(ch, "5") == 0)
LevelorderTraverse(T);
else if (strcmp(ch, "6") == 0)
{
int depth = search_depth(T);
system("cls");
printf("The depth of the binary tree is: %d", depth);
}
else if (strcmp(ch, "7") == 0)
leaves(T);
else if (strcmp(ch, "8") == 0)
{
int n = 0;
n=Judge(T);
if (n == 0)
printf("This tree is not a complete binary tree\\
");
else printf("The tree is a complete binary tree\\
");
}
else if (strcmp(ch, "0") == 0)
{
system("cls");
printf("Thanks for using!\\
\\
");
break;
printf("The program failed to exit!\\
");
exit(0);
}
else
{
system("cls");
printf("\\
Illegal input!\\
\\
");
}
}
}

The input to build a binary tree here is to select the number and fill in the data. The operation can be like this. Of course, you can also create your own binary tree.

Finally, attach my source code:

#define _CRT_SECURE_NO_WARNINGS
#include 
#include 
#include 
#define MAX_NODE 50
typedef char ElemType;
typedef struct BTnode
{
ElemType data;
struct BTnode* Lchild, * Rchild;
}BTNode;

void visit(BTNode*T) //output operation
{
printf("%c", T->data);
}

BTNode* Create_BiTree() //Create a binary tree
{
BTNode* T, * p, * s[MAX_NODE]; //array stack
ElemType ch;
T = NULL;
int i, j;
system("cls");
while (1)
{
printf("Enter the number of the node:\\
");
scanf("%d", &i);
if (i == 0) break;
printf("Enter the value of the node:\\
");
getchar(); //Prevent the Enter key from destroying the input
scanf("%c", &ch);
p = (BTNode*)malloc(sizeof(BTNode));
p->data = ch;
p->Lchild = p->Rchild = NULL; //constantly construct an empty complete binary tree
s[i] = p;
if (i == 1) T = p;
else {
j = i / 2;
if (i % 2 == 0)
s[j]->Lchild = p;
else
s[j]->Rchild=p;
}
i + + ;
}
system("cls");
printf("Enter successfully\\
");
return T;
}

void PreorderTraverse(BTNode* T)
/*Non-recursive pre-order traversal of the binary tree T*/
{
BTNode* s[MAX_NODE], * p, *q;
int top=0;
p = T;
system("cls");
if (T == NULL) printf("The tree is an empty tree\\
");
else {
while (p & amp; & amp; top != -1)
{
visit(p);
q = p->Rchild;
if (q != NULL)
s[++top] = q;
p = p->Lchild;
if (p == NULL)
p = s[top--];
}
}
}

void InorderTraverse(BTNode* T)
/*Non-recursive inorder traversal of a binary tree*/
{
BTNode* s[MAX_NODE], * p;
int top = 0;
int flag = 1;
system("cls");
p = T;
if (T == NULL) printf("The tree is an empty tree\\
");
else {
do {
while (p)
{
s[++top] = p;
p = p->Lchild;
}
if (top == 0) flag = 0;
else {
p = s[top--];
visit(p);
p = p->Rchild;
}
} while (flag != 0);
}
}

void PostorderTraverse(BTNode* T)
/* Subsequent traversal of the binary tree T*/
{
if (T != NULL)
{
system("cls");
PostorderTraverse(T->Lchild);
PostorderTraverse(T->Rchild);
visit(T); /* visit the root node */
}
}

void LevelorderTraverse(BTNode* T) //level traversal binary tree
{
BTNode* DL[MAX_NODE], * p;
int rear=0, front=0;
system("cls");
p = T;
if (p != NULL) //In fact, it exits when the tail of the queue points to NULL
{
DL[++ rear] = p;
while (front < rear)
{
p = DL[++front];
visit(p);
if (p->Lchild != NULL)
DL[ + + rear] = p->Lchild;
if (p->Rchild != NULL)
DL[ + + rear] = p->Rchild;
}
}
}

int search_depth(BTNode* T)
{
BTNode* Queue[MAX_NODE], * p = T;
int front = 0, rear = 0, depth = 0, level;
/* level always points to the position of the last node of the access layer in the queue */
if (T != NULL)
{
Queue[ + + rear] = p; /* root node enqueue */
level = rear; /* root is the last node of level 1 */
while (front < rear)
{
p = Queue[++front];
if (p->Lchild != NULL) // the left child node is not empty, join the queue
Queue[ + + rear] = p->Lchild;
if (p->Rchild != NULL) // the right child node is not empty, join the queue
Queue[ + + rear] = p->Rchild;
if (front == level) // visit the last node of the current layer
{
depth++;
level = rear;
}
}
}
return depth;
}

void leaves(BTNode* T)
/*Output leaf nodes and non-leaf nodes*/
{
BTNode* DL[MAX_NODE], * p = T; //array queue
int front = 0, rear = 0;
system("cls");
if (p != NULL)
{
DL[++ rear] = p;
front = 1;
while (front <= rear) {
if (p->Lchild == NULL & amp; & amp; p->Rchild == NULL)
printf("Leaf node: %c\\
", p->data);
else {
printf("Non-leaf node: %c\\
", p->data);
if (p->Lchild != NULL)
DL[ + + rear] = p->Lchild;
if (p->Rchild != NULL)
DL[ + + rear] = p->Rchild;
}
p = DL[++front];
}
}
}

int Judge(BTNode* T)//judging whether the binary tree is a complete binary tree (level traversal)
{
BTNode* DL[MAX_NODE],*p; //queue array
int rear = 0, front = 0;
system("cls");
p = T;
if (p != NULL)
{
DL[++ rear] = p;
while (front < rear) {
p = DL[++front];
if ( p->Lchild == NULL & amp; & amp; p->Rchild != NULL) //When the left subtree is empty and the right subtree is not empty, it does not conform to the nature of a complete binary tree
return 0;
else {
if (p->Lchild != NULL)
DL[ + + rear] = p->Lchild;
if (p->Rchild != NULL)
DL[ + + rear] = p->Rchild;
}
}
}
return 1;
}

int main()
{
BTNode* T = NULL;
char ch[10];
while (1)
{
printf("\\
============================================== =============\\
");
printf("| 1. Build a binary tree T |\\
");
printf("| 2. Use non-recursive pre-order traversal to output the nodes of tree T |\\
");
printf("| 3. Use non-recursive inorder traversal to output the nodes of tree T |\\
");
printf("| 4. Use the post-order traversal method to output the nodes of the tree T |\\
");
printf("| 5. Use hierarchical traversal to output the nodes of tree T |\\
");
printf("| 6. The depth of the output tree T |\\
");
printf("| 7. Output the leaf nodes and non-leaf nodes of tree T |\\
");
printf("| 8. Determine whether the binary tree is a complete binary tree (level traversal) |\\
");
printf("| 0. Exit the program |\\
");
printf("================================================ =========\\
");
printf("Please enter the operation to be performed:");
scanf("%s", ch);
if (strcmp(ch, "1") == 0)
T = Create_BiTree();
else if (strcmp(ch, "2") == 0)
PreorderTraverse(T);
else if (strcmp(ch, "3") == 0)
InorderTraverse(T);
else if (strcmp(ch, "4") == 0)
{
system("cls");
PostorderTraverse(T);
}
else if (strcmp(ch, "5") == 0)
LevelorderTraverse(T);
else if (strcmp(ch, "6") == 0)
{
int depth = search_depth(T);
system("cls");
printf("The depth of the binary tree is: %d", depth);
}
else if (strcmp(ch, "7") == 0)
leaves(T);
else if (strcmp(ch, "8") == 0)
{
int n = 0;
n=Judge(T);
if (n == 0)
printf("This tree is not a complete binary tree\\
");
else printf("The tree is a complete binary tree\\
");
}
else if (strcmp(ch, "0") == 0)
{
system("cls");
printf("Thanks for using!\\
\\
");
break;
printf("The program failed to exit!\\
");
exit(0);
}
else
{
system("cls");
printf("\\
Illegal input!\\
\\
");
}
}
}