C Language version ： Binary tree in data structure , The first sequence traversal , In the sequence traversal , After the sequence traversal , And their reverse order .

Traversal of binary tree

The traversal of binary tree ： The first sequence traversal ： Around the head , In the sequence traversal ： Left head right , After the sequence traversal ： Left and right The rules of , The following is a diagram of the binary tree of this article .

Tips ： The following is the main body of this article , The following cases can be used for reference

One 、 The use of stacks

Stack operation rules ： First in, then out , For example, binary conversion is also an application of stack , The previous article introduced the conversion of binary system , The reverse order of binary tree can use stack .

Two 、 Traverse the way

1. The first sequence traversal

The code is as follows （ Example ）：

// positive sequence 
void perorder(RTreeNode* p)
{
    
	if (p != NULL)
	{
    
		printf("->%c", p->data);
		perorder(p->lchild);
		perorder(p->rchild);
	}// The first sequence traversal 
}

// The reverse 
void sperorder(RStack* S, RTreeNode* p)
{
    
	if (p != NULL)
	{
    
		push(S, p->data);// Into the stack 
		sperorder(S, p->lchild);
		sperorder(S, p->rchild);
	}
}// Tree traversal requires recursion , The condition for ending recursion is p Point to empty time 

// Print the results in reverse order 
void treeout(RStack p)
{
    
	while (!empty(&p))
	{
    
		printf("->%c", pop(&p));
	}
}

2. In the sequence traversal

The code is as follows （ Example ）：

// positive sequence 
void perorder(RTreeNode* p)
{
    
	if (p != NULL)
	{
    
		perorder(p->lchild);
		printf("->%c", p->data);
		perorder(p->rchild);
	}// The first sequence traversal 
}

// The reverse 
void sperorder(RStack* S, RTreeNode* p)
{
    
	if (p != NULL)
	{
    
		sperorder(S, p->lchild);
		push(S, p->data);// Into the stack 
		sperorder(S, p->rchild);
	}
}// Tree traversal requires recursion , The condition for ending recursion is p Point to empty time 

// Print the results in reverse order 
void treeout(RStack p)
{
    
	while (!empty(&p))
	{
    
		printf("->%c", pop(&p));
	}
}

3. After the sequence traversal

// positive sequence 
void perorder(RTreeNode* p)
{
    
	if (p != NULL)
	{
    
		perorder(p->lchild);
		perorder(p->rchild);
		printf("->%c", p->data);
	}// The first sequence traversal 
}

// The reverse 
void sperorder(RStack* S, RTreeNode* p)
{
    
	if (p != NULL)
	{
    
		sperorder(S, p->lchild);
		sperorder(S, p->rchild);
		push(S, p->data);// Into the stack 
	}
}// Tree traversal requires recursion , The condition for ending recursion is p Point to empty time 

// Print the results in reverse order 
void treeout(RStack p)
{
    
	while (!empty(&p))
	{
    
		printf("->%c", pop(&p));
	}
}

Code implementation

// The positive and negative order of subsequent traversal are examples 
//
// Created by xhh on 2021/6/30.
//
#include<stdio.h>
#include<stdlib.h>
#include<process.h>
#include<string>
#define MAX 50

typedef struct TreeNode
{
    
    struct TreeNode* lchild, * rchild;  // Left and right subtree pointers 
    char data;                  // Elements in nodes 
}RTreeNode;

// Initialize a tree 
RTreeNode* initnode(char x, RTreeNode* lchild, RTreeNode* rchild)
{
    
    RTreeNode* SS;
    SS = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    SS->data = x;
    SS->lchild = lchild;
    SS->rchild = rchild;
    return SS;
}

// Define a stack 
typedef struct Stack
{
    
    int top;                 // Shaping variables is convenient for addition and subtraction , Easy to move 
    char sa[MAX];           // Maximum stack space 
}RStack;

// Initialize a stack 
RStack init()
{
    
    RStack* SS;
    SS = (struct Stack*)malloc(sizeof(struct Stack));      // Dynamically allocate memory space 
    SS->top = 0;
    return *SS;
}

// Into the stack 
void push(RStack *S, char x)
{
    
    if (S->top == MAX)
    {
    
        printf("the stack is full");
        exit(0);
    }
    S->sa[S->top] = x;              //top Point to empty stack , So get into the position it points to 
    S->top++;
}

// Out of the stack 
char pop(RStack* S)
{
    
    if (S->top == 0)       // Empty stack or not 
    {
    
        printf(" The stack is empty ");
        exit(0);
    }

    return S->sa[--S->top];
}

// Judge stack empty 
int empty(RStack* S)
{
    
    if (S->top == 0)
    {
    
        return 1;
    }
    return 0;
}

// Empty stack elements 
void clear(RStack* S)
{
    
    S->top = 0;
}

// Make a tree 
RTreeNode* inittree()
{
    
    RTreeNode* root, * b, * c, * d, * e, * f;
    d = initnode('D', NULL, NULL);
    e = initnode('E', NULL, NULL);
    f = initnode('F', NULL, NULL);
    b = initnode('B', d, NULL);
    c = initnode('C', e, f);
    root = initnode('A', b, c);       // There is only one following node , And put it last 
    return(root);
}

// positive sequence 
void perorder(RTreeNode* p)
{
    
    if (p != NULL)
    {
    
        perorder(p->lchild);
        perorder(p->rchild);
        printf("->%c", p->data);
    }// The first sequence traversal 
}

// The reverse 
void sperorder(RStack* S, RTreeNode* p)
{
    
    if (p != NULL)
    {
    

        sperorder(S, p->lchild);
        sperorder(S, p->rchild);
        push(S, p->data);// Into the stack 
    }
}// Tree traversal requires recursion , The condition for ending recursion is p Point to empty time 

void treeout(RStack p)
{
    
    while (!empty(&p))
    {
    
        printf("->%c", pop(&p));
    }
}

int main()
{
    
    RTreeNode* tree;
    tree = inittree();   // Make a tree 
    RStack SS;
    SS = init();       // Generated a stack 
    perorder(tree);
    printf("\n");
    sperorder(&SS, tree);
    treeout(SS);
    return 0;
}

 The subsequent traversal result is ：
 positive sequence ：
->D->B->E->F->C->A
 The reverse ：
->A->C->F->E->B->D