The school has also done a similar task on data structures, and has recently been thinking about what to write about on the blog. After all, college study is still centered on exams, so I’ll just write down what I usually read.

Sequence traversal

Queues are implemented in arrays

Sequential traversal is traversal by binary tree layer by layer, which I think is pretty intuitive actually. Writing this blog is to strengthen my ability to combine binary tree and stack and queue application, after all, there is a big gap between learning truth and knocking out code.

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

#define MAXSIZE 100
typedef struct Node{
char data;
struct Node *Lchild;
struct Node *Rchild;
}BiTNode,*Bitree;

typedef struct queue{
    BiTNode *numQ[MAXSIZE];// Note here is the key. We use the same queue type as our ADT!!
    int front;
    int rear;
}Queue;// In this case I chose to operate with arrays



void CreateBinTree(BiTNode **T)
{
    char ch;
    ch=getchar();
   if(ch==The '#'){ *T=NULL;return; } *T=(BiTNode*)malloc(sizeof(BiTNode));
            (*T)->data=ch;
        CreateBinTree(&((*T)->Lchild));
        CreateBinTree(&((*T)->Rchild));
}
void PreTree(Bitree T)
{   if(T==NULL) return;
    printf("%c ",T->data);
     PreTree(T->Lchild);
     PreTree(T->Rchild);

}


// The following are the basic operations for creating a queue, which corresponds to a binary tree
void initilize(Queue *Q) { // Initialize the queue
    Q->front = 0;
    Q->rear = 0;
}

void Push(Queue *Q,BiTNode *T)/ / team
// I prefer to use * to represent the pointer
{
    Q->rear++;
    Q->numQ[Q->rear]=T;
}

BiTNode *Pop(Queue *Q)/ / out of the team
{
    Q->front++;
    return Q->numQ[Q->front];
}

int Isempty(Queue *Q)// Check whether it is null
{
    return Q->front==Q->rear;
}

void LayerOrder(BiTNode *T)// Binary tree level traversal
{
    Queue Q;
    initilize(&Q);
    BiTNode *p;
    Push(&Q,T);
    while(! Isempty(&Q)) { p=Pop(&Q);printf("%c ",p->data);// Outputs the first queue node
        if(p->Lchild) Push(&Q,p->Lchild);// Queue the left child of the node that pops off
        if(p->Rchild) Push(&Q,p->Rchild);// Queue the right child of the node that pops off}}int main(a)
{
    BiTNode *T=(BiTNode*)malloc(sizeof(BiTNode));
    CreateBinTree(&T);
    //PreTree(T);
    LayerOrder(T);
    return 0;
}



Copy the code

That’s it, as shown below:

The LayerOrder queue is created in the main function instead of the LayerOrder queue. The main function is called without am&.

void LayerOrder(Queue *Q,BiTNode *T)// Binary tree level traversal
{

    BiTNode *p;
    Push(Q,T);
    while(! Isempty(Q)) { p=Pop(Q);printf("%c ",p->data);// Outputs the first queue node
        if(p->Lchild) Push(Q,p->Lchild);// Queue the left child of the node that pops off
        if(p->Rchild) Push(Q,p->Rchild);// Queue the right child of the node that pops off}}int main(a)
{
    BiTNode *T=(BiTNode*)malloc(sizeof(BiTNode));
    CreateBinTree(&T);
    Queue Q;
    initilize(&Q);
    //PreTree(T);
    LayerOrder(&Q,T);
    return 0;
}
Copy the code

Alternatively, you can define global variables entirely, so that you don’t have to call Q at all, and you don’t have to use “. “instead of” ->”, which is a good idea.

The key here is that the array created when creating the queue is of type BitTreeNode *.

Using a chain queue

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

#define MAXSIZE 100

typedef struct TreeNode{
char data;
struct TreeNode *Lchild;
struct TreeNode *Rchild;
}BiTNode,*Bitree;

typedef BiTNode* QueueElemType;// What is a user - defined type

typedef struct Node
{
    QueueElemType data;
    struct Node *next;
}LQNode;

typedef struct {
LQNode *front;
LQNode *near;
}LinkQueue;

void CreateBinTree(BiTNode **T)
{
    char ch;
    ch=getchar();
   if(ch==The '#'){ *T=NULL;return; } *T=(BiTNode*)malloc(sizeof(BiTNode));
            (*T)->data=ch;
        CreateBinTree(&((*T)->Lchild));
        CreateBinTree(&((*T)->Rchild));
}
void PreTree(Bitree T)
{   if(T==NULL) return;
    printf("%c ",T->data);
     PreTree(T->Lchild);
     PreTree(T->Rchild);
}

// The following are the basic operations for creating a chain queue. Note the corresponding binary tree

void initilize(LinkQueue *Q) { // Initialize the queue
     Q->front=(LQNode*)malloc(sizeof(LQNode));
     Q->near=Q->front;
    Q->front->next=NULL;
}


void EnterQueue(LinkQueue *Q,BiTNode *x)/ / team
{
    LQNode *NewNode;
    NewNode=(LQNode*)malloc(sizeof(LQNode));

    if(NewNode! =NULL)
    {
        NewNode->data=x;
        NewNode->next=NULL; Q->near->next=NewNode; Q->near=NewNode; }}BiTNode *DeleteQueue(LinkQueue *Q)/ / out of the team
{
    LQNode *p;
    p=Q->front->next;
    Q->front->next=p->next;
    if(Q->near==p)  // If there is only one element
    {
        Q->front=Q->near;
    }

    return p->data;
}

int Isempty(LinkQueue *Q)
{
    return Q->front==Q->near;
}

void LayerOrder(LinkQueue *Q,BiTNode *T)// Binary tree level traversal
{

    BiTNode *p;
    EnterQueue(Q,T);
    while(! Isempty(Q)) { p=DeleteQueue(Q);printf("%c ",p->data);// Outputs the first queue node
        if(p->Lchild) EnterQueue(Q,p->Lchild);// Queue the left child of the node that pops off
        if(p->Rchild) EnterQueue(Q,p->Rchild);// Queue the right child of the node that pops off}}int main(a)
{
    BiTNode *T=(BiTNode*)malloc(sizeof(BiTNode));
    CreateBinTree(&T);
    //PreTree(T);

    LinkQueue *Q=(LinkQueue*)malloc(sizeof(LinkQueue));
    initilize(Q);

    LayerOrder(Q,T);
    return 0;

}
Copy the code

Note that when I define *Q in the main function, I need to allocate space to call the initialization function to initialize it. If the initialization is performed directly in the main function, I do not need to allocate space for Q. Like when I used array queues, I defined Q directly, but when I used Pointers, I had to define *Q. In my opinion, it is difficult to understand when to use &, and it is still determined by experience and compilation. Remember that a pointer is an address, and a variable that calls an address in a function is an address. In other words, arrays are convenient, but chain queues are too cumbersome.

Non-recursive algorithms

A non-recursive algorithm for sequential traversal

Simulation of the stack

So this is just a simulation of pushing and doing a simulation of recursion, and comparative recursion is essentially pushing.

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

#define MAXSIZE 100

typedef struct TreeNode{
char data;
struct TreeNode *Lchild;
struct TreeNode *Rchild;
}BiTNode,*Bitree;

void CreateBinTree(BiTNode **T)
{
    char ch;
    ch=getchar();
   if(ch==The '#'){ *T=NULL;return; } *T=(BiTNode*)malloc(sizeof(BiTNode));
            (*T)->data=ch;
        CreateBinTree(&((*T)->Lchild));
        CreateBinTree(&((*T)->Rchild));
}

void PreTree(Bitree T)// Medium output
{   if(T==NULL) return;

     PreTree(T->Lchild);
      printf("%c ",T->data);
     PreTree(T->Rchild);

}
void inorder(BiTNode *T)// The middle-order output is non-recursive
{
    BiTNode *s[MAXSIZE];/ / simulation stack
    int top=0;
    BiTNode *p;
    p=T;
    do{
        while(p! =NULL)
        {
            if(top>MAXSIZE) return ;
            top++;
            s[top]=p;
            p=p->Lchild;
        }// Iterate over the left subtree
        if(top! =0)
        {
            p=s[top];
            top--;
            printf("%c ",p->data);// Access the root
            p=p->Rchild;// Iterate over the right subtree}}while(p! =NULL||top! =0);
}
int main(a)
{
    BiTNode *T=(BiTNode*)malloc(sizeof(BiTNode));
    CreateBinTree(&T);
    PreTree(T);
    printf("\n");
    inorder(T);

    return 0;
}

Copy the code

The correctness can be verified as shown in the figure:

Call stack operation

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

#define MAXSIZE 100

typedef struct TreeNode{
char data;
struct TreeNode *Lchild;
struct TreeNode *Rchild;
}BiTNode,*Bitree;

typedef struct stack
{
    BiTNode *s[MAXSIZE];
    int top;
}Stack;

void CreateBinTree(BiTNode **T)
{
    char ch;
    ch=getchar();
   if(ch==The '#'){ *T=NULL;return; } *T=(BiTNode*)malloc(sizeof(BiTNode));
            (*T)->data=ch;
        CreateBinTree(&((*T)->Lchild));
        CreateBinTree(&((*T)->Rchild));
}

void PreTree(Bitree T)// Medium output
{   if(T==NULL) return;

     PreTree(T->Lchild);
      printf("%c ",T->data);
     PreTree(T->Rchild);

}
void inorder(BiTNode *T)// The middle-order output is non-recursive
{
    BiTNode *s[MAXSIZE];/ / simulation stack
    int top=0;
    BiTNode *p;
    p=T;
    do{
        while(p! =NULL)
        {
            if(top>MAXSIZE) return ;
            top++;
            s[top]=p;
            p=p->Lchild;
        }// Iterate over the left subtree
        if(top! =0)
        {
            p=s[top];
            top--;
            printf("%c ",p->data);// Access the root
            p=p->Rchild;// Iterate over the right subtree}}while(p! =NULL||top! =0);
}
// The following is the basic operation for creating a stack. Note that it corresponds to the binary tree
void InitStack(Stack *S)/ / initialization
{
    S->top=0;
}

void Push(Stack *S,BiTNode *T)/ / pressure stack
{
    S->top++;
    S->s[S->top]=T;
}

BiTNode *Pop(Stack *S)/ / out of the stack
{
    BiTNode *p;
    p=S->s[S->top];
    S->top--;
    return p;
}

int Isempty(Stack *S)
{
    if(S->top==0) return 1;
    else return 0;
}
void inordermoder2(BiTNode *T)
{
    Stack S;
    InitStack(&S);
    BiTNode *p;
    p=T;
    while(p! =NULL| |! Isempty(&S)) {if(p! =NULL)// Iterate over the left subtree
        {
            Push(&S,p);
            p=p->Lchild;
            printf("0");
        }
        else{
                 printf("1");
            p=Pop(&S);
            printf("%c ",p->data); p-p->Rchild; }}}int main(a)
{
    BiTNode *T=(BiTNode*)malloc(sizeof(BiTNode));
    CreateBinTree(&T);
    PreTree(T);
    printf("\n");
    inordermoder2(T);

    return 0;
}

Copy the code

It’s easy to build a stack after a queue.

Post-order traversal is non-recursive

// The following is the basic operation for creating a stack. Note that it corresponds to the binary tree
void InitStack(Stack *S)/ / initialization
{
    S->top=0;
}

void Push(Stack *S,BiTNode *T)/ / pressure stack
{
    S->top++;
    S->s[S->top]=T;
}

BiTNode *Pop(Stack *S)/ / out of the stack
{
    BiTNode *p;
    p=S->s[S->top];
    S->top--;
    return p;
}
void gettop(Stack *S,BiTNode **T)/ / get the stack
// Make sure you use a second-level pointer to modify the tree
{
    (*T)=S->s[S->top];
}

int Isempty(Stack *S)
{
    if(S->top==0) return 1;
    else return 0;
}
void inordermoder2(BiTNode *T)
{
    Stack S;
    InitStack(&S);
    BiTNode *p;
    p=T;
   while(p! =NULL| |! Isempty(&S)) {if(p! =NULL)// Iterate over the left subtree
        {
            Push(&S,p);
            p=p->Lchild;
            printf("0");
        }
        else{
                 printf("1");
            p=Pop(&S);
            printf("%c ",p->data); p-p->Rchild; }}}void PreTree2(Bitree T)// After output
{   if(T==NULL) return;

     PreTree(T->Lchild);

     PreTree(T->Rchild);

     printf("%c ",T->data);

}
void PostOrder(BiTNode *T)// The output is non-recursive
{
    Stack S;
    BiTNode *q,*p;
    q=NULL;
    p=T;
    InitStack(&S);
    while(p! =NULL| |! Isempty(&S)) {if(p! =NULL)
        {
            Push(&S,p);
            p=p->Lchild;
        }// Iterate over the left subtree
        else{
                gettop(&S,&p);
                if(p->Rchild==NULL||(p->Rchild==q))
                {
                    printf("%c ",p->data);
                    q=p;
                    p=Pop(&S);
                    p=NULL;
                }
                else{ p=p->Rchild; }}}}Copy the code

Finished, hand hit a feeling or have a lot of harvest.