Binary trees are followed by non-recursive traversal (many people’s blind spots?).

Hi, I’m Johngo!

Today there are fans in school want to C language implementation of the tree’s follow-up traversal of the detailed explanation, today to see. Back to all the code, you can run directly!

Backorder traversal of binary tree

The traversal mode of binary tree mainly consists of sequential traversal, middle-order traversal and subsequent traversal, followed by hierarchical traversal

After feeling the way of traversal in the first two chapters, this section will look at the sequential traversal

Post-order traversal process

A. Sequence traversal of its left subtree;

B. Sequence traversal of its right subtree;

C. Access the root node.

And then you recurse, and when you get to the node, you can do something about the node, like simply accessing the value of the node

The figure below is a binary tree. Let’s simulate the post-order traversal process manually

According to the process of post-order traversal above, the post-order traversal sequence can be obtained:

H I D E B F G C A
Copy the code

The recursive implementation

The following sequence traversal of binary tree is implemented in C language code using the above recursive idea:

Tree Structure Initialization is performed based on the preceding tree structure

# include <stdio.h>
# include <string.h>
# include <stdlib.h>
# define ElementType char

// Node structure
typedef struct BinTNode{
    ElementType data; 
    struct BinTNode * left; 
    struct BinTNode * right;
}BinTNode, *BinTree;

// Initialize the tree structure
BinTNode * CreateBiTree(BinTNode *T){
    T=(BinTNode*)malloc(sizeof(BinTNode));
    T->data='A';
    T->left=(BinTNode*)malloc(sizeof(BinTNode));
    T->left->data='B';
    T->right=(BinTNode*)malloc(sizeof(BinTNode));
    T->right->data='C';
  
    T->left->left=(BinTNode*)malloc(sizeof(BinTNode));
    T->left->left->data='D';
    T->left->right=(BinTNode*)malloc(sizeof(BinTNode));
    T->left->right->data='E';
    T->left->right->left=NULL;
    T->left->right->right=NULL;  
    T->left->left->left=(BinTNode*)malloc(sizeof(BinTNode));
    T->left->left->left->data='H';
    T->left->left->left->left=NULL;
    T->left->left->left->right=NULL;
    T->left->left->right=(BinTNode*)malloc(sizeof(BinTNode));
    T->left->left->right->data='I';
    T->left->left->right->left=NULL;
    T->left->left->right->right=NULL;
      
    T->right->left=(BinTNode*)malloc(sizeof(BinTNode));
    T->right->left->data='F';
    T->right->left->left=NULL;
    T->right->left->right=NULL;
    T->right->right=(BinTNode*)malloc(sizeof(BinTNode));
    T->right->right->data='G';
    T->right->right->left=NULL;
    T->right->right->right=NULL;

    return T;
}

// Outputs node values during traversal
void printElement(BinTNode * T){
    printf("%c ",T->data);
}

// order traversal first
void PostOrderTraverse(BinTNode * T){
    if (T) {
        PostOrderTraverse(T->left);  // Recursive access to the left child
        PostOrderTraverse(T->right); // Recursively access the right child
        printElement(T);             // Outputs the node value
    }
    // Returns when the node is empty
    return;
}

int main(a) {
    BinTNode * Tree;
    Tree = CreateBiTree(Tree);	// Initialize the tree structure
    printf("After traversal:");
    PostOrderTraverse(Tree); 		// start recursively
    printf("\n");   						// Line wrap
    return 0;
}
Copy the code

Running results:

H I D E B F G C ACopy the code

Non-recursive implementation

Compared with the previous non-recursive implementation of pre-order traversal and middle-order traversal, the non-recursive algorithm of post-order traversal is different from the previous one. The subsequent traversal needs to visit the left and right child nodes before it can access the node, which is also the difficulty of non-recursion.

Several implementations have been considered, and I’m going to present what I think is a fairly clear one for your reference: use two stacks (S1 and S2) to operate

Take a look at the pseudocode below:

The top element initializing S1 is the root of the tree;while(top1 ! =- 1) {push the top element to S2;if(The top element has children){S1 is pushed into the left and right order of children; }} loop pops the top elements of S2 one by oneCopy the code

Pseudo-code may not be easy to understand after reading it, but still look at it clearly, with the help of the following figure, will be clear (long picture issued) :

With this idea should be very clear, the following ideas in accordance with the C language:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define ElementType char
int top_S1 = - 1;   // define stack S1 top subscript
int top_S2 = - 1;   // define stack S2 top subscript

// Node structure
typedef struct BinTNode{
    ElementType data; 
    struct BinTNode * left; 
    struct BinTNode * right;
}BinTNode, *BinTree;

// Initialize the tree structure
BinTNode * CreateBiTree(BinTNode *T) {
    T=(BinTNode*)malloc(sizeof(BinTNode));
    T->data='A';
    T->left=(BinTNode*)malloc(sizeof(BinTNode));
    T->left->data='B';
    T->right=(BinTNode*)malloc(sizeof(BinTNode));
    T->right->data='C';
  
    T->left->left=(BinTNode*)malloc(sizeof(BinTNode));
    T->left->left->data='D';
    T->left->right=(BinTNode*)malloc(sizeof(BinTNode));
    T->left->right->data='E';
    T->left->right->left=NULL;
    T->left->right->right=NULL;  
    T->left->left->left=(BinTNode*)malloc(sizeof(BinTNode));
    T->left->left->left->data='H';
    T->left->left->left->left=NULL;
    T->left->left->left->right=NULL;
    T->left->left->right=(BinTNode*)malloc(sizeof(BinTNode));
    T->left->left->right->data='I';
    T->left->left->right->left=NULL;
    T->left->left->right->right=NULL;
      
    T->right->left=(BinTNode*)malloc(sizeof(BinTNode));
    T->right->left->data='F';
    T->right->left->left=NULL;
    T->right->left->right=NULL;
    T->right->right=(BinTNode*)malloc(sizeof(BinTNode));
    T->right->right->data='G';
    T->right->right->left=NULL;
    T->right->right->right=NULL;

    return T;
}

// push S1 - push push
void push_S1(BinTNode** stack,BinTNode * elem) {
    stack[++top_S1] = elem;
}

// stack S2 - push
void push_S2(BinTNode** stack,BinTNode * elem) {
    stack[++top_S2] = elem;
}

// stack S1 - stack pop
void pop_S1(a){
    if (top_S1 == - 1) {
        return ;
    }
    top_S1--;
}

// stack S2 - pop stack
void pop_S2(a){
    if (top_S2 == - 1) {
        return ;
    }
    top_S2--;
}

// Output node values during traversal
void printElement(BinTNode* elem) {
    printf("%c ",elem->data);
}

// Get the top element of the stack
BinTNode * getTop_S1(BinTNode** stack){
    return stack[top_S1];
}

// Get the top element of the stack
BinTNode * getTop_S2(BinTNode** stack){
    return stack[top_S2];
}

// Non-recursive traversal - left and right roots
void PostOrderTraverse(BinTNode * Tree) {
    BinTNode * S1[30];          / / auxiliary stack
    BinTNode * S2[30];
    BinTNode * T = Tree;        // Define a temporary pointer
    BinTNode * Temp;
    push_S1(S1, T);             The top element that initializes S1 is the root of the tree
    while(top_S1 ! =- 1) {
        T = getTop_S1(S1);      // the top element of S1 pops up
        pop_S1();               // The top element pops onto the stack
        push_S2(S2, T);

        if(T->left ! =NULL|| T->right ! =NULL) {  // The top element of the stack has children
            if(T->left ! =NULL)
                push_S1(S1, T->left);
            if(T->right ! =NULL) push_S1(S1, T->right); }}// Pop the elements of S2 one by one
    while(top_S2 ! =- 1) { printElement(getTop_S2(S2)); pop_S2(); }}int main(a) {
    BinTNode * Tree;
    Tree = CreateBiTree(Tree);
    printf("H I D E B F G C A\n");
    printf("After traversal :\t");
    PostOrderTraverse(Tree);
    printf("\n");
    return 0;
}
Copy the code

The results

H D I B E A F C GCopy the code