Data structure | Chained binary tree (C language)

1. Data structure definition

1. Chained binary tree

/* chained binary tree definition */
typedef char TreeType;
typedef struct BinaryTreeNode {
TreeType data;
struct BinaryTreeNode* lchild, * rchild;
}*BiTree, BiTNode;

The structure of the binary tree in this code is shown in the figure below, which can be expressed as ABD##E#H##CF##G##

2. Chained stack

/* chain stack definition */
typedef BiTNode* StackType;
typedef struct StackNode {
StackType data;
struct StackNode* next;
}StackNode;

typedef struct {
StackNode* top;
}LinkStack;

Non-recursive traversal of a binary tree (pre-order traversal, in-order traversal, subsequent traversal) needs to be assisted by a stack

3. Chain queue

/* chain queue definition */
typedef BiTNode* QueueType;
typedef struct QueueNode {
QueueType data;
struct QueueNode* next;
}QueueNode;

typedef struct {
QueueNode* front, * rear;
}LinkQueue;

The level traversal of a binary tree needs to be assisted by a queue

2. Method overview

1. Binary tree

BiTree createTree();//Preorder method to create a binary tree
int count_TreeSize(BiTree root);//calculate the number of all nodes
int count_LeafNode(BiTree root);//calculate the number of leaf nodes
int count_TreeDepth(BiTree root);//calculate the depth of the tree
int count_TreeLevelSize(BiTNode* root, int level);//Calculate the number of i-th layer nodes
void changeRight_Left(BiTree root);//Exchange the left and right subtrees of the binary tree
void destructionTree(BiTree* root);//Binary tree destruction
void visit(BiTNode* node);//Operation on node T
void preOrder_recursion(BiTree root);//Preorder traversal (recursion)
void inOrder_recursion(BiTree root);//Inorder traversal (recursion)
void postOrder_recursion(BiTree root);//post-order traversal (recursion)
void inOrder_non_recursion(BiTree root);//In-order traversal (non-recursive)
void preOrder_non_recursion(BiTree root);//Preorder traversal (non-recursive)
void levelOrder(BiTree root);//level traversal

2. Stack

void initStack(LinkStack* S);//Initialize the stack
int isStackEmpty(LinkStack S);//judging whether the stack is empty
int pushStack(LinkStack* L, StackType data);//Into the stack
int popStack(LinkStack* L, StackType* data);// pop the stack
int getStackTop(LinkStack* L, StackType* x);//Get the top element of the stack
int destroyStack(LinkStack* L);//destroy the stack

3. Queue

void initQueue(LinkQueue* Q);//Initialize the queue
int isQueueEmpty(LinkQueue Q);//Judge whether the queue is empty
void enQueue(LinkQueue* Q, QueueType data);//enqueue
int deQueue(LinkQueue* Q, QueueType* x);//Queue

3. Detailed method

1. Stack

/*------------- stack basic operations ---------------*/
//Initialize the stack
void initStack(LinkStack* S) {
S->top = (StackNode*)malloc(sizeof(StackNode)); // allocate head node
S->top = NULL; //Initialize to empty
}
// Check if the stack is empty
int isStackEmpty(LinkStack S) {
if (S. top == NULL) return 1;
else return 0;
}
//Push into the stack
int popStack(LinkStack* L, StackType* data) {
StackNode* del;
if (L->top == NULL) return -1;
else {
del = L->top;
*data = del->data;
L->top = L->top->next;
free(del);
return 0;
}
}
// pop out
int pushStack(LinkStack* L, StackType data) {
StackNode* news = (StackNode*)malloc(sizeof(struct StackNode));
if (news == NULL) return -1;
else {
news->data = data;
news->next = L->top;
L->top = news;
return 0;
}
}
//Get the top element of the stack
int getStackTop(LinkStack* L, StackType* x) {
if (L->top == NULL) {
*x = NULL;
return -1;
}
else {
*x = L->top->data;
return 1;
}
}
//Destroy the stack
int destroyStack(LinkStack* L) {
int cnt = 0;
if (L == NULL) return 0;
struct StackNode* p = L->top, * q;
free(L);
while (p->next != NULL) {
q = p->next;
cnt + + ;
free(p);
p = q;
}
return cnt;
}

2. Queue

/*------------- Queue basic operations ---------------*/
//Initialize the queue
void initQueue(LinkQueue* Q) {
Q->front = Q->rear = (QueueNode*)malloc(sizeof(QueueNode)); // allocate head node
Q->front->next = NULL; //initialize to empty
}
// Check if the queue is empty
int isQueueEmpty(LinkQueue Q) {
if (Q. front == Q. rear) return 1;
else return 0;
}
//enqueue
void enQueue(LinkQueue* Q, QueueType data) {
QueueNode* news = (QueueNode*)malloc(sizeof(QueueNode));
news->data = data; // Create a new node and insert it at the end of the queue
news->next = NULL;
Q->rear->next = news;
Q->rear = news;
}
//dequeue
int deQueue(LinkQueue* Q, QueueType* x) {
if (Q->front == Q->rear) return 0;
QueueNode* del = Q->front->next;
*x = del->data;
Q->front->next = del->next;
if (Q->rear == del)
Q->rear = Q->front; // If the original queue has only one node, it becomes empty after deletion
free(del);
return 1;
}

3. Basic operation of binary tree

/*------------- tree operations ---------------*/
//Preorder method to create a binary tree
BiTree createTree() {
BiTree root;
TreeType data;
scanf("%c", & amp; data);

if (data == '#') root = NULL;
else {
root = (struct BinaryTreeNode*)malloc(sizeof(struct BinaryTreeNode));
root->data = data;
root->lchild = createTree();
root->rchild = createTree();
}
return root;
}
// count all nodes
int count_TreeSize(BiTree root) {
if (root == NULL) return 0;
return count_TreeSize(root->lchild) + count_TreeSize(root->rchild) + 1;
}
// Calculate the number of leaf nodes
int count_LeafNode(BiTree root) {
if (root == NULL) return 0;
else if (root->lchild == NULL & amp; & amp; root->rchild == NULL) return 1;
else return count_LeafNode(root->lchild) + count_LeafNode(root->rchild);
}
// Calculate the depth of the tree
int count_TreeDepth(BiTree root) {
if (root == NULL) {
return 0;
}
else {
int l = count_TreeDepth(root->lchild);
int r = count_TreeDepth(root->rchild);
return l > r ? l + 1 : r + 1;
}
}
//Calculate the number of i-level nodes
int count_TreeLevelSize(BiTNode* root, int level) {
if (root == NULL) return 0;
if (level == 1) return 1;
return count_TreeLevelSize(root->lchild, level - 1) + count_TreeLevelSize(root->rchild, level - 1);
}
//Swap the left and right subtrees of the binary tree
void changeRight_Left(BiTree root) {
BiTree temp;
if (root == NULL);
else if (root->lchild == NULL & amp; & amp; root->rchild == NULL);
else {
temp = root->lchild;
root->lchild = root->rchild;
root->rchild = temp;
changeRight_Left(root->lchild);
changeRight_Left(root->rchild);
}
}
//binary tree destruction
void destroyTree(BiTree* root) {
if (*root != NULL) {
if ((*root)->lchild) //has a left child
destructionTree( & amp;(*root)->lchild);
if ((*root)->rchild) //has a right child
destructionTree( & amp;(*root)->rchild);
free(*root); //Release the root node
*root = NULL; //null pointer NULL
}
}

4. Binary tree recursive traversal

(1) Operation on nodes

//Operation on node T
void visit(BiTNode* node) {
printf(" %c", node->data);
}

(2) Preorder traversal

//Preorder traversal (recursion)
void preOrder_recursion(BiTree root) {
if (root != NULL) {
visit(root);
preOrder_recursion(root->lchild);
preOrder_recursion(root->rchild);
}
}

(3) Inorder traversal

//Inorder traversal (recursion)
void inOrder_recursion(BiTree root) {
if (root != NULL) {
inOrder_recursion(root->lchild);
visit(root);
inOrder_recursion(root->rchild);
}
}

(4) Postorder traversal

//post-order traversal (recursive)
void postOrder_recursion(BiTree root) {
if (root != NULL) {
postOrder_recursion(root->lchild);
postOrder_recursion(root->rchild);
visit(root);
}
}

5. Binary tree non-recursive traversal

(1) Preorder traversal

//Preorder traversal (non-recursive)
void preOrder_non_recursion(BiTree root) {
LinkStack S;
initStack( &S);
BiTree p = root;
while (p || !isStackEmpty(S)) {
if (p) {
visit(p);
pushStack( &S, p);
p = p->lchild;
}
else {
popStack( &S, &p);
p = p->rchild;
}
}
}

(2) Inorder traversal

//In-order traversal (non-recursive)
void inOrder_non_recursion(BiTree root) {
LinkStack S;
initStack( &S);
BiTree p = root;
while (p || !isStackEmpty(S)) {
if (p) {
pushStack( &S, p);
p = p->lchild;
}
else {
popStack( &S, &p);
visit(p);
p = p->rchild;
}
}
}

(3) Postorder traversal

// Subsequent traversal (non-recursive)
void postOrder_non_recursion(BiTree root) {
LinkStack S;
initStack( &S);
BiTNode* p = root;
BiTNode* r = NULL;
while (p || !isStackEmpty(S)) {
if (p) {
pushStack( &S, p);
p = p->lchild;
}
else {
getStackTop( &S, &p);
if (p->rchild & amp; & amp; p->rchild != r)
p = p->rchild;
else {
popStack( &S, &p);
visit(p);
r = p;
p = NULL;
}
}
}
}

6. Binary tree level traversal

//level traversal
void levelOrder(BiTree root) {
LinkQueue Q;
initQueue( & Q);
BiTree p;
enQueue( & amp;Q, root);
while (!isQueueEmpty(Q)) {
deQueue( &Q, &p);
visit(p);
if (p->lchild != NULL) {
enQueue( &Q, p->lchild);
}
if (p->rchild != NULL) {
enQueue( &Q, p->rchild);
}
}
}

4. Running results

The main method code is as follows:

int main() {
// Input preorder sequence ABD##E#H##CF##G## Create binary tree
printf("Enter the preorder sequence to create a binary tree:");
BiTree root = createTree();

printf("\\
Preorder traversal (recursion):");
preOrder_recursion(root);
printf("\\
Preorder traversal (non-recursive):");
preOrder_non_recursion(root);

printf("\\
Inorder traversal (recursion):");
inOrder_recursion(root);
printf("\\
Inorder traversal (non-recursive):");
inOrder_non_recursion(root);

printf("\\
post-order traversal (recursion):");
postOrder_recursion(root);
printf("\\
post-order traversal (non-recursive):");
postOrder_non_recursion(root);

printf("\\
level traversal:");
levelOrder(root);

changeRight_Left(root);
printf("\\
Preorder traversal after exchanging left and right subtrees:");
postOrder_recursion(root);

printf("\\
The depth of the tree = %d", count_TreeDepth(root));
printf("\\
Number of all nodes = %d", count_TreeSize(root));
printf("\\
Number of leaf nodes = %d", count_LeafNode(root));

int level;
printf("\\
Input layer number:");
scanf("%d", & level);
printf("Number of nodes in layer %d = %d", level, count_TreeLevelSize(root, level));

return 0;
}

The result of the operation is as follows:

Five, source code

#define _CRT_SECURE_NO_WARNINGS
#include 
#include 


/* chained binary tree definition */
typedef char TreeType;
typedef struct BinaryTreeNode {
TreeType data;
struct BinaryTreeNode* lchild, * rchild;
}*BiTree, BiTNode;

/* Linked stack definition */
typedef BiTNode* StackType;
typedef struct StackNode {
StackType data;
struct StackNode* next;
}StackNode;

typedef struct {
StackNode* top;
}LinkStack;

/* chained queue definition */
typedef BiTNode* QueueType;
typedef struct QueueNode {
QueueType data;
struct QueueNode* next;
}QueueNode;

typedef struct {
QueueNode* front, * rear;
}LinkQueue;


void initQueue(LinkQueue* Q);//initialize the queue
int isQueueEmpty(LinkQueue Q);//Judge whether the queue is empty
void enQueue(LinkQueue* Q, QueueType data);//enqueue
int deQueue(LinkQueue* Q, QueueType* x);//Dequeue

void initStack(LinkStack* S);//Initialize the stack
int isStackEmpty(LinkStack S);//judging whether the stack is empty
int pushStack(LinkStack* L, StackType data);//Into the stack
int popStack(LinkStack* L, StackType* data);// pop the stack
int getStackTop(LinkStack* L, StackType* x);//Get the top element of the stack
int destroyStack(LinkStack* L);//destroy the stack

BiTree createTree();//Preorder method to create a binary tree
int count_TreeSize(BiTree root);//calculate the number of all nodes
int count_LeafNode(BiTree root);//calculate the number of leaf nodes
int count_TreeDepth(BiTree root);//calculate the depth of the tree
int count_TreeLevelSize(BiTNode* root, int level);//Calculate the number of i-th layer nodes
void changeRight_Left(BiTree root);//Exchange the left and right subtrees of the binary tree
void destructionTree(BiTree* root);//Binary tree destruction
void visit(BiTNode* node);//Operation on node T
void preOrder_recursion(BiTree root);//Preorder traversal (recursion)
void inOrder_recursion(BiTree root);//Inorder traversal (recursion)
void postOrder_recursion(BiTree root);//post-order traversal (recursion)
void inOrder_non_recursion(BiTree root);//In-order traversal (non-recursive)
void preOrder_non_recursion(BiTree root);//Preorder traversal (non-recursive)
void levelOrder(BiTree root);//level traversal


/*------------- Queue basic operations ---------------*/
//Initialize the queue
void initQueue(LinkQueue* Q) {
Q->front = Q->rear = (QueueNode*)malloc(sizeof(QueueNode)); // allocate head node
Q->front->next = NULL; //initialize to empty
}
// Check if the queue is empty
int isQueueEmpty(LinkQueue Q) {
if (Q. front == Q. rear) return 1;
else return 0;
}
//enqueue
void enQueue(LinkQueue* Q, QueueType data) {
QueueNode* news = (QueueNode*)malloc(sizeof(QueueNode));
news->data = data; // Create a new node and insert it at the end of the queue
news->next = NULL;
Q->rear->next = news;
Q->rear = news;
}
//dequeue
int deQueue(LinkQueue* Q, QueueType* x) {
if (Q->front == Q->rear) return 0;
QueueNode* del = Q->front->next;
*x = del->data;
Q->front->next = del->next;
if (Q->rear == del)
Q->rear = Q->front; // If the original queue has only one node, it becomes empty after deletion
free(del);
return 1;
}


/*------------- stack basic operations ---------------*/
//Initialize the stack
void initStack(LinkStack* S) {
S->top = (StackNode*)malloc(sizeof(StackNode)); // allocate head node
S->top = NULL; //Initialize to empty
}
// Check if the stack is empty
int isStackEmpty(LinkStack S) {
if (S.top == NULL) return 1;
else return 0;
}
//Push into the stack
int popStack(LinkStack* L, StackType* data) {
StackNode* del;
if (L->top == NULL) return -1;
else {
del = L->top;
*data = del->data;
L->top = L->top->next;
free(del);
return 0;
}
}
// pop out
int pushStack(LinkStack* L, StackType data) {
StackNode* news = (StackNode*)malloc(sizeof(struct StackNode));
if (news == NULL) return -1;
else {
news->data = data;
news->next = L->top;
L->top = news;
return 0;
}
}
//Get the top element of the stack
int getStackTop(LinkStack* L, StackType* x) {
if (L->top == NULL) {
*x = NULL;
return -1;
}
else {
*x = L->top->data;
return 1;
}
}
//Destroy the stack
int destroyStack(LinkStack* L) {
int cnt = 0;
if (L == NULL) return 0;
struct StackNode* p = L->top, * q;
free(L);
while (p->next != NULL) {
q = p->next;
cnt + + ;
free(p);
p = q;
}
return cnt;
}


/*------------- tree operations --------------*/
//Preorder method to create a binary tree
BiTree createTree() {
BiTree root;
TreeType data;
scanf("%c", & amp; data);

if (data == '#') root = NULL;
else {
root = (struct BinaryTreeNode*)malloc(sizeof(struct BinaryTreeNode));
root->data = data;
root->lchild = createTree();
root->rchild = createTree();
}
return root;
}
// count all nodes
int count_TreeSize(BiTree root) {
if (root == NULL) return 0;
return count_TreeSize(root->lchild) + count_TreeSize(root->rchild) + 1;
}
// Calculate the number of leaf nodes
int count_LeafNode(BiTree root) {
if (root == NULL) return 0;
else if (root->lchild == NULL & amp; & amp; root->rchild == NULL) return 1;
else return count_LeafNode(root->lchild) + count_LeafNode(root->rchild);
}
// Calculate the depth of the tree
int count_TreeDepth(BiTree root) {
if (root == NULL) {
return 0;
}
else {
int l = count_TreeDepth(root->lchild);
int r = count_TreeDepth(root->rchild);
return l > r ? l + 1 : r + 1;
}
}
//Calculate the number of i-level nodes
int count_TreeLevelSize(BiTNode* root, int level) {
if (root == NULL) return 0;
if (level == 1) return 1;
return count_TreeLevelSize(root->lchild, level - 1) + count_TreeLevelSize(root->rchild, level - 1);
}
//Swap the left and right subtrees of the binary tree
void changeRight_Left(BiTree root) {
BiTree temp;
if (root == NULL);
else if (root->lchild == NULL & amp; & amp; root->rchild == NULL);
else {
temp = root->lchild;
root->lchild = root->rchild;
root->rchild = temp;
changeRight_Left(root->lchild);
changeRight_Left(root->rchild);
}
}
//binary tree destruction
void destroyTree(BiTree* root) {
if (*root != NULL) {
if ((*root)->lchild) //has a left child
destructionTree( & amp;(*root)->lchild);
if ((*root)->rchild) //has a right child
destructionTree( & amp;(*root)->rchild);
free(*root); //Release the root node
*root = NULL; //null pointer NULL
}
}
//Operation on node T
void visit(BiTNode* node) {
printf(" %c", node->data);
}
// preorder traversal (recursion)
void preOrder_recursion(BiTree root) {
if (root != NULL) {
visit(root);
preOrder_recursion(root->lchild);
preOrder_recursion(root->rchild);
}
}
//Inorder traversal (recursive)
void inOrder_recursion(BiTree root) {
if (root != NULL) {
inOrder_recursion(root->lchild);
visit(root);
inOrder_recursion(root->rchild);
}
}
// post-order traversal (recursive)
void postOrder_recursion(BiTree root) {
if (root != NULL) {
postOrder_recursion(root->lchild);
postOrder_recursion(root->rchild);
visit(root);
}
}
// Preorder traversal (non-recursive)
void preOrder_non_recursion(BiTree root) {
LinkStack S;
initStack( &S);
BiTree p = root;
while (p || !isStackEmpty(S)) {
if (p) {
visit(p);
pushStack( &S, p);
p = p->lchild;
}
else {
popStack( &S, &p);
p = p->rchild;
}
}
}
//Inorder traversal (non-recursive)
void inOrder_non_recursion(BiTree root) {
LinkStack S;
initStack( &S);
BiTree p = root;
while (p || !isStackEmpty(S)) {
if (p) {
pushStack( &S, p);
p = p->lchild;
}
else {
popStack( &S, &p);
visit(p);
p = p->rchild;
}
}
}
// Subsequent traversal (non-recursive)
void postOrder_non_recursion(BiTree root) {
LinkStack S;
initStack( &S);
BiTNode* p = root;
BiTNode* r = NULL;
while (p || !isStackEmpty(S)) {
if (p) {
pushStack( &S, p);
p = p->lchild;
}
else {
getStackTop( &S, &p);
if (p->rchild & amp; & amp; p->rchild != r)
p = p->rchild;
else {
popStack( &S, &p);
visit(p);
r = p;
p = NULL;
}
}
}
}
// level traversal
void levelOrder(BiTree root) {
LinkQueue Q;
initQueue( & Q);
BiTree p;
enQueue( & amp;Q, root);
while (!isQueueEmpty(Q)) {
deQueue( &Q, &p);
visit(p);
if (p->lchild != NULL) {
enQueue( &Q, p->lchild);
}
if (p->rchild != NULL) {
enQueue( &Q, p->rchild);
}
}
}


int main() {
// Input preorder sequence ABD##E#H##CF##G## Create binary tree
printf("Enter the preorder sequence to create a binary tree:");
BiTree root = createTree();

printf("\\
Preorder traversal (recursion):");
preOrder_recursion(root);
printf("\\
Preorder traversal (non-recursive):");
preOrder_non_recursion(root);

printf("\\
Inorder traversal (recursion):");
inOrder_recursion(root);
printf("\\
Inorder traversal (non-recursive):");
inOrder_non_recursion(root);

printf("\\
post-order traversal (recursion):");
postOrder_recursion(root);
printf("\\
post-order traversal (non-recursive):");
postOrder_non_recursion(root);

printf("\\
level traversal:");
levelOrder(root);

changeRight_Left(root);
printf("\\
Preorder traversal after exchanging left and right subtrees:");
postOrder_recursion(root);

printf("\\
The depth of the tree = %d", count_TreeDepth(root));
printf("\\
Number of all nodes = %d", count_TreeSize(root));
printf("\\
Number of leaf nodes = %d", count_LeafNode(root));

int level;
printf("\\
Input layer number:");
scanf("%d", & level);
printf("Number of nodes in layer %d = %d", level, count_TreeLevelSize(root, level));

return 0;
}