Sequence traversal of binary tree (implemented in C language)

Sequence traversal code idea

With a secondary queue .

• First join the root node of the binary tree ,
• And then out of the team , Access the outbound node ,
  • If it has a left subtree , The root node of the left subtree will be queued ;
  • If it has a right subtree , The root node of the right subtree will be queued .
  • And then out of the team ,
  • Access the outbound node …… So again and again , Until the queue is empty

void LevelOrder(BiTree T)
{
    
	InitQueue(&Q);	//  Initialize the secondary queue 
	BiTree p;
	EnQueue(&Q, T);	//  Put the root node in the team 
	while(!IsEmpty(Q))	//  If the queue is not empty, the loop  
	{
    
		DeQueue(Q, p);	//  The head of the team goes out 
		visit(p);
		if (p->lchild != NULL)
		{
    
			EnQueue(Q, p->lchild);	//  Zuozi tree is not empty , Then the root node of the left subtree joins the team  
		}
		if (p->rchild != NULL)
		{
    
			EnQueue(Q, p->rchild);	//  Right subtree is not empty , Then the root node of the right subtree joins the team  
		} 
	} 
}

Implementation process

According to the above code ideas , You need to implement two data structures , A binary tree , A line , The functions that need to be realized are

• Binary tree 、 Data structure definition of queue
• The creation of binary tree 、 Initialization of the queue
• Sequence traversal of binary tree 、 Out of queue 、 Joining operation

Code implementation

#include <stdio.h>
#include <stdlib.h>

using namespace std;

typedef char TElemType;

const int MAXSIZES = 50;

//  Binary tree storage structure  
typedef struct BiTNode {
    
	TElemType data;
	struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

typedef BiTree QElemType;

//  The storage structure of the queue  
typedef struct {
    
	QElemType data[MAXSIZES];
	int front;
	int rear;
}SqQueue;

//  Create a binary tree through preorder traversal  
void CreateBiTree(BiTree *T)
{
    
	TElemType ch;
	scanf("%c", &ch);
	if (ch == '#')
	{
    
		*T = NULL;
	}
	else
	{
    
		*T = (BiTree) malloc(sizeof(BiTNode));
		if (!T)
		{
    
			exit(0);
		}
		(*T)->data = ch;
		CreateBiTree(&(*T)->lchild);
		CreateBiTree(&(*T)->rchild);
	}
}

//  Initialize queue  
void InitQueue(SqQueue *Q)
{
    
	Q->front = Q->rear = 0;
}

//  Queue entry of auxiliary queue  
void EnQueue(SqQueue *Q, QElemType q)
{
    
	if ((Q->rear + 1) % MAXSIZES == Q->front)
		return;
	Q->data[Q->rear] = q;
	Q->rear = (Q->rear + 1) % MAXSIZES;
}

//  Outbound operation of auxiliary queue  
void DeQueue(SqQueue *Q, QElemType *q)
{
    
	if (Q->front == Q->rear)
		return;
	*q = Q->data[Q->front];
	Q->front = (Q->front + 1) % MAXSIZES;
}

//  Middle order traversal of binary trees  
void InOrderTraverse(BiTree T)
{
    
	if (!T)
	{
    
		return;
	}
	
	InOrderTraverse(T->lchild);
	printf("%c", T->data);
	InOrderTraverse(T->rchild);
}

//  Sequence traversal of binary tree  
void LevelOrder(BiTree T)
{
    
	SqQueue Q;
	InitQueue(&Q);	//  Initialize the secondary queue 
	BiTree p;
	EnQueue(&Q, T);	//  Put the root node in the team 
	while(Q.front != Q.rear)	//  If the queue is not empty, the loop  
	{
    
		DeQueue(&Q, &p);	//  The head of the team goes out 
		printf("%c", p->data);
		if (p->lchild != NULL)
		{
    
			EnQueue(&Q, p->lchild);	//  Zuozi tree is not empty , Then the root node of the left subtree joins the team  
		}
		if (p->rchild != NULL)
		{
    
			EnQueue(&Q, p->rchild);	//  Right subtree is not empty , Then the root node of the right subtree joins the team  
		} 
	} 
}

int main()
{
    
	BiTree t;
	printf(" Please expand the binary tree in the previous order to enter ：（# Represents an empty node ）\n");
	CreateBiTree(&t);
	printf(" In the sequence traversal : "); 
	InOrderTraverse(t);
	printf("\n Sequence traversal : "); 
	LevelOrder(t);
	
	return 0;
}

Reference resources :
Sequence traversal idea 《 Wang Dao data structure 》