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; }