As a data structure, binary tree is actually a very interesting structure , There can be a variety of applications
Let's look directly at the binary tree code ：
#include<stdlib.h> #include<stdio.h> #include<malloc.h> #include<string.h> #
define maxsize 100 // Basic operation of binary tree ： establish , Preamble , Middle order , Post order , arrangement , Find the number of leaves , Find the number of layers , Finding node tree // Data structure of binary tree
// Create data fields and left and right pointer fields typedef struct Tree { char data; struct tree* lchild; struct tree*
rchild; }tree; // Establish binary initialization void inittree(tree* root) { root->data = ""; root->
rchild= NULL; root->lchild = NULL; } // Creation of binary number tree* create(tree* root) { char
value; scanf_s("%c", &value); if (value == '#') { root = NULL; } else { root = (
tree*)malloc(sizeof(tree)); root->data = value; root->lchild = create(root->
lchild); root->rchild = create(root->rchild); } return root; }
// Create node of binary tree ( Secondary pointer writing ) void createnode(tree** node) { char p_data; scanf_s("%c", &
p_data); if (p_data == '#') { *node = NULL; } else { *node = (tree*)malloc(
sizeof(tree)); (*node)->data = p_data; createnode(&((*node)->lchild));
createnode(&((*node)->rchild)); } } // Judge whether the binary tree is empty int tempty(tree* root) { if (
root->data == "") { printf(" Binary tree is empty \n"); return 0; } else { printf(" Binary tree is not empty \n");
return 1; } } // Preorder traversal （ recursion ） void porder(tree* root) { if (root != NULL) { printf(
"%c\t", root->data); porder(root->lchild); porder(root->rchild); } } // Medium order traversal （ recursion ）
void morder(tree* root) { if (root != NULL) { morder(root->lchild); printf(
"%c\t", root->data); morder(root->rchild); } } // Postorder traversal （ recursion ） void torder(tree* root
) { if (root != NULL) { torder(root->lchild); torder(root->rchild); printf(
"%c\t", root->data); } } // Preorder traversal non recursive // The nodes accessing the left subtree are stored in the stack （ Keep going ） Until it can't be accessed, then let it go out of the stack to access the right subtree void
p_order(tree* root) { if (root == NULL) { return; } tree* box[10];
// Create a stack to store the location of each print node int box_top = -1;// Stack top tag , To keep consistent with array subscripts tree* move = root;
// Print from root node while (box_top != -1 || move) { while (move) { // Stack the path and print the node printf(
"%c\t", move->data); box[++box_top] = move;// Store nodes in array move = move->lchild;
// Move to the left subtree of the storage node } if (box_top != -1)// Judge if the left subtree is accessed { move = box[box_top];// Get stack top element
box_top--;// to flash back move = move->rchild;// Move access right subtree } } } // Medium order traversal non recursive
// Continue to drill down into the left subtree and store nodes until they cannot drill down, then backtrack and print , Access the right subtree after leaving the stack void m_order(tree* root) { tree* box[10];
// Create stack , Location for storing nodes int box_top = -1;// Defines the tag at the top of the stack tree* move = root;// Defines the pointer to move while (
box_top!= -1 || move) { // Drill down to the left subtree while (move) { box[++box_top] = move; move =
move->lchild; } if (box_top != -1) { move = box[box_top--];// Get stack top element and backtrace printf(
"%c\t", move->data); move = move->rchild;// Move to right subtree } } } // Postorder traversal non recursive
// Access the left subtree first and drill down until it is inaccessible , Print nodes and backtrack , Then access the right subtree , Print backtracking , Two tree roots will appear // Define the access mark. If it is accessed, it will not be printed again to solve the problem of multiple printing after backtracking
void t_order(tree* root) { if (root == NULL) { return; } tree* box[10]; int
box_top= -1; tree* move = root; tree* visit = NULL;// Access tag while (move) { box[++
box_top] = move; move = move->lchild; } while (box_top != -1) { move = box[
box_top--]; if (move->rchild == NULL || move->rchild == visit)// Judge whether the right subtree of the current node is accessed
{ printf("%c\t", move->data); visit = move;// Changing the location of the marker is to trace back to the tree root of the upper layer } else { box[++
box_top] = move; move = move->rchild; while (move) { box[++box_top] = move; move
= move->lchild; } } } } // Finding the number of leaves of binary tree int leaves(tree* root) { if (root == NULL) {
return 0; } else if (root->lchild == NULL && root->rchild == NULL) { return 1; }
else { return leaves(root->lchild) + leaves(root->rchild); } } // Recursive algorithm for finding tree depth int
deep(tree* root) { int lnum, rnum; if (root == NULL) { return 0; } else { lnum =
deep(root->lchild); rnum = deep(root->rchild); return (lnum > rnum ? lnum : rnum
) + 1; } } // Find the depth of the subtree with a value as the root in the binary tree （ recursion ） void x_deep(tree* root , char x) { int lnum = 0
, rnum = 0; if (root == NULL) { printf(" Empty tree depth is 0\n"); } if (root->data == x) {
printf("%d\n", deep(root)); } else { if (root->lchild) { x_deep(root->lchild, x)
; } if (root->rchild) { x_deep(root->rchild, x); } } } // Finding the number of layers of a specified node from a binary tree int floor(
tree* root, char x) { int lnum, rnum, fnum; if (root == NULL) { fnum = 0; } else
if (root->data == x) { fnum = 1; } else { lnum = floor(root->lchild, x); rnum =
floor(root->rchild, x); if (lnum == 0 && rnum == 0)// Search failed {
/*printf(" Find end \n");*/ fnum = 0; } else { fnum = ((lnum > rnum) ? lnum : rnum) +
1; } } return fnum; } // Number of nodes in Statistics int nodenum(tree* root) { if (root == NULL) {
return 0; } else { return(nodenum(root->lchild) + nodenum(root->rchild)) + 1; }
} // level traversal BFS // preparation ： Construct queue typedef struct queue { tree* qdata[maxsize]; int front;
int rear; }q; // Initialize queue void initqueue(q* node) { node->front = node->rear = 0;
} // Determine whether the queue is empty void empty(q* node) { if (node->front == node->rear) { printf(
" Queue is empty "); } } // Join the team void push(q* node, tree* root) { node->qdata[node->rear] =
root; node->rear++; } // Out of the team tree* pop(q* node, tree* root) { return node->qdata[(
++node->front) - 1]; } // Binary tree hierarchy traversal BFS void BFS(tree* root) { q* node; node = (q*)
malloc(sizeof(q)); initqueue(node); if (root != NULL) { push(node, root); }
while (node->front != node->rear) { tree* root1 = (tree*)malloc(sizeof(tree));
root1= pop(node, root1); printf("%c\t", root1->data); if (root1->lchild != NULL)
{ push(node, root1->lchild); } if (root1->rchild != NULL) { push(node, root1->
rchild); } } } int main() { // test ：12#46###3#5##,ABC##DE#G##F### tree* root = (
tree*)malloc(sizeof(tree)); inittree(root); printf(" Please enter the binary tree in the order of traversal first ：\n"); root =
create(root); int temp; while (1) { printf(
"***************************** Binary tree comprehensive experiment ****************************\n"); printf(
"*****************************1. Binary tree preorder traversal **************************\n"); printf(
"*****************************2. Order traversal in binary tree **************************\n"); printf(
"*****************************3. Postorder traversal of binary tree **************************\n"); printf(
"*****************************4. Binary tree preorder traversal （ non-recursive ）****************\n"); printf(
"*****************************5. Binary tree preorder traversal （ non-recursive ）****************\n"); printf(
"*****************************6. Binary tree preorder traversal （ non-recursive ）****************\n"); printf(
"*****************************7. Binary tree hierarchy traversal （BFS）*******************\n"); printf(
"*****************************8. Find the depth of binary tree （ recursion ）********************\n"); printf(
"*****************************9. Finding the number of leaves of binary tree **************************\n"); printf(
"*****************************10. Finding node number of binary tree *************************\n"); printf(
"*****************************11. Binary tree finds the number of layers of the specified node *************\n"); printf(
"*****************************12. Judge whether the binary tree is empty *******************\n"); printf(
"*****************************13. Find the depth of the subtree with a value as the root in the binary tree （ recursion ）*\n"); printf(
"*****************************14. sign out exit*******************************\n");
printf(
"***********************************************************************\n");
printf(" Enter your options ："); scanf_s("%d", &temp); if (temp == 14) { printf(" Program exit 》》》");
break; } switch (temp) { case 1: printf(" Preorder traversal of binary tree ( recursion ) by ：\n"); porder(root); printf
("\n"); break; case 2: printf(" Order traversal in binary tree ( recursion ) by ：\n"); morder(root); printf("\n");
break; case 3: printf(" Postorder traversal of binary tree ( recursion ) by ：\n"); torder(root); printf("\n"); break;
case 4: printf(" The preorder traversal of binary tree is ：\n"); p_order(root); printf("\n"); break; case 5:
printf(" The order traversal in binary tree is ：\n"); m_order(root); printf("\n"); break; case 6: printf(
" The post order traversal of binary tree is ：\n"); t_order(root); printf("\n"); break; case 7: printf(
"BFS Sequence traversal binary tree ：\n"); BFS(root); printf("\n"); break; case 8: printf(" The depth of the binary tree is %d layer \n",
deep(root)); break; case 9: printf(" Binary tree contains %d Leaf nodes \n", leaves(root)); break; case
10: printf(" Common binary tree %d Nodes \n", nodenum(root)); break; case 11: { char x; printf(
" Please enter the node you want to find ："); scanf_s(" %c", &x);// be careful ： Be sure to %c Add one before blank, Leave buffer empty ! printf(
" The number of layers of the current node is ：%d\n", floor(root, x)); } break; case 12: tempty(root); printf("\n")
; break; case 13: { char x2; printf(" Please enter the node you want to find ："); scanf_s(" %c", &x2); printf(
" with %c Is the depth of the subtree ：",x2); x_deep(root, x2); printf("\n"); } break; default: printf(
"error"); break; } } return 0; }
Program execution results ：
Technology