The main traversal methods of binary tree are first order traversal, middle order traversal, post order traversal and hierarchy traversal.
1. Preorder traversal
The operation process of traversal is as follows:
If the binary tree is empty, do nothing; otherwise:
(1) Access root node
(2) Preorder traversal of left subtree
(3) Preorder traversal right subtree
The corresponding algorithm code is as follows:
/* Preorder traversal */
/* *p Refers to the root node of a binary tree */
void preOrder(BTNode *p) {
if(p!=NULL) {
printf("%c",p->data);// Print tree node data
preOrder(p->lchild);// Preorder traversal of left subtree
preOrder(p->rchild);// Preorder traversal right subtree
}
}2. Middle order traversal
The operation process of middle order traversal is as follows:
If the binary tree is empty, do nothing; otherwise:
(1) Middle order traversal left subtree
(2) Access root node
(3) Middle order traversal right subtree
The corresponding algorithm code is as follows:
/* Middle order ergodic */
/* *p Refers to the root node of a binary tree */
void inOrder(BTNode *p) {
if(p!=NULL) {
inOrder(p->lchild);
printf("%c",p->data);
inOrder(p->rchild);
}
}3. Middle order traversal
The operation process of subsequent traversal is as follows:
If the binary tree is empty, do nothing; otherwise:
(1) Postorder traversal of left subtree
(2) Postorder traversal right subtree
(3) Access root node
The corresponding algorithm code is as follows:
/* Postorder ergodic */
/* *p Refers to the root node of a binary tree */
void postOrder(BTNode *p) {
if(p!=NULL) {
postOrder(p->lchild);
postOrder(p->rchild);
printf("%c",p->data);
}
}The complete code is as follows:
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<assert.h>
/* Number structure type definition*/
typedef struct BTNode {
char data;// Here, the default node data field is char type
struct BTNode *lchild;// Left child pointer field
struct BTNode *rchild;// Right child pointer field
} BTNode,*BiTree;
/* Create a binary tree based on input */
/* E.g.: ABC, De, F, GH### */
void CreatBiNode(BTNode **Node) { //Note the parameters passed here (double pointer)
char data;
scanf("%c", &data);
*Node = (BiTree)malloc(sizeof(BTNode));
if (data == '#') {
*Node = NULL;
} else if ((data != '#') && (*Node)) {
(*Node)->data = data;
(*Node)->lchild = NULL;
(*Node)->rchild = NULL;
CreatBiNode(&(*Node)->lchild);
CreatBiNode(&(*Node)->rchild);
}
}
/* Preorder traversal */
/* *p Refers to the root node of a binary tree */
void preOrder(BTNode *p) {
if(p!=NULL) {
printf("%c",p->data);// Print tree node data
preOrder(p->lchild);// Preorder traversal of left subtree
preOrder(p->rchild);// Preorder traversal right subtree
}
}
/* Middle order ergodic */
/* *p Refers to the root node of a binary tree */
void inOrder(BTNode *p) {
if(p!=NULL) {
inOrder(p->lchild);
printf("%c",p->data);
inOrder(p->rchild);
}
}
/* Postorder ergodic */
/* *p Refers to the root node of a binary tree */
void postOrder(BTNode *p) {
if(p!=NULL) {
postOrder(p->lchild);
postOrder(p->rchild);
printf("%c",p->data);
}
}
int main() {
printf("First order input binary tree(For null node'#'for): ");
BiTree T=NULL;
CreatBiNode(&T);// Create a binary tree
/* Preorder traversal */
printf("First order traversal:");
preOrder(T);
/* Middle order ergodic */
printf("\n Middle order traversal:");
inOrder(T);
/* Postorder ergodic */
printf("\n Subsequent traversal:");
postOrder(T);
return 0;
}Note: the binary tree created above uses the method of first order traversal, so when entering characters, the method of first order should be followed.
Note: the empty node is represented by "ා", and enter a sequence string, and then press enter to create a binary tree.
4. Hierarchical traversal
As shown in the figure above, first traverse each layer. The first layer is A, the second layer is BC, the third layer is DEFG, and the fourth layer is HI. So the result is ABCDEFGHI.
Figure 6-10 shows the hierarchical traversal of the binary tree, that is, according to the direction indicated by the arrow, according to the hierarchical order of 1, 2, 3 and 4, access to each node in the binary tree (this figure reflects the level traversal from left to right, and the way from right to left is similar).
To traverse the hierarchy, you need to create a circular queue. First, put the head node of binary tree into the queue, and then out of the queue to access the node. If it has a left subtree, then put the root node of the left subtree into the queue. If it has a right subtree, then put the root node of the right subtree into the queue. Then out of the queue, access to the out of the queue node. Repeat until the queue is empty.
Core code:
/* level traversal */
void level(BTNode *p) {
int front,rear;
BTNode *que[maxSize];// Define a circular queue to record the nodes in the hierarchy to be accessed
front=rear=0;
BTNode *q;
if(p!=NULL) {
rear=(rear+1)%maxSize;
que[rear]=p;// Root node joining the team
while(front!=rear) { // Loop when the queue is not empty
front=(front+1)%maxSize;
q=que[front];// Team leader out
printf("%c",q->data);// Visit team head node
if(q->lchild!=NULL) { // If the left subtree is not empty, the root node of the left subtree is queued
rear=(rear+1)%maxSize;
que[rear]=q->lchild;
}
if(q->rchild!=NULL) { // If the right subtree is not empty, the root node of the right subtree is queued
rear=(rear+1)%maxSize;
que[rear]=q->rchild;
}
}
}
}Full code:
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<assert.h>
#define maxSize 30
/* Number structure type definition*/
typedef struct BTNode {
char data;// Here, the default node data field is char type
struct BTNode *lchild;// Left child pointer field
struct BTNode *rchild;// Right child pointer field
} BTNode,*BiTree;
/* Create a binary tree based on input */
/* E.g.: ABC, De, F, GH### */
void CreatBiNode(BTNode **Node) { //Note the parameters passed here (double pointer)
char data;
scanf("%c", &data);
*Node = (BiTree)malloc(sizeof(BTNode));
if (data == '#') {
*Node = NULL;
} else if ((data != '#') && (*Node)) {
(*Node)->data = data;
(*Node)->lchild = NULL;
(*Node)->rchild = NULL;
CreatBiNode(&(*Node)->lchild);
CreatBiNode(&(*Node)->rchild);
}
}
/* level traversal */
void level(BTNode *p) {
int front,rear;
BTNode *que[maxSize];// Define a circular queue to record the nodes in the hierarchy to be accessed
front=rear=0;
BTNode *q;
if(p!=NULL) {
rear=(rear+1)%maxSize;
que[rear]=p;// Root node joining the team
while(front!=rear) { // Loop when the queue is not empty
front=(front+1)%maxSize;
q=que[front];// Team leader out
printf("%c",q->data);// Visit team head node
if(q->lchild!=NULL) { // If the left subtree is not empty, the root node of the left subtree is queued
rear=(rear+1)%maxSize;
que[rear]=q->lchild;
}
if(q->rchild!=NULL) { // If the right subtree is not empty, the root node of the right subtree is queued
rear=(rear+1)%maxSize;
que[rear]=q->rchild;
}
}
}
}
int main() {
printf("First order input binary tree(For null node'#'for): ");
BiTree T=NULL;
CreatBiNode(&T);// Create a binary tree
/* level traversal */
printf("Hierarchy traversal:");
level(T);
return 0;
}Operation result:
The following figure is an example of input (where the null node is represented by "×"). The input string is as follows:
