【C】 Recursive and non recursive writing of binary tree traversal

Preface

Three recursive ways of traversing binary trees , Just understand the thought , A few lines of code can complete . But non recursive writing is not easy . Here is a special summary , Thoroughly analyze their non recursive writing . among , The non recursive writing of middle order traversal is the simplest , Post order traversal is the most difficult .

The non recursive writing of middle order traversal

non-recursive algorithm , The stack must be used （ Refer to the implementation of stack in the complete code ）. Here we will focus on the writing method of middle order traversal .

void InorderTraversal(BinTree BT)
{
    
    BinTree T;
    Stack TreeStack;
    TreeStack = CreateStack();

    T = BT;
    while (T || !IsEmpty(TreeStack)){
    // Note the conditions for the end of the cycle 
        while (T){
       				// Put all the left sub trees into the stack at one go 
            Push(TreeStack,T);		
            T = T->Left;			
        }
        T = Pop(TreeStack);			//  When exiting the loop ,T It's empty , That is, there is no left subtree 
        printf("%d ", T->Data);	// here , Print the node value 
        T = T->Right;				// Then , Turn to the right subtree , If the node is a leaf node ,
        							// be T It's still empty , The next cycle is directly out of the stack ,
        							// Here, the codes of leaf nodes and regular nodes are cleverly unified 
    }
}

The non recursive writing method of post order traversal

Post order traversal requires putting the parent node on the stack twice , Print the second time out of the stack , So it needs to be marked . The code is modified on the basis of medium order traversal , Understand the middle order traversal , The following code is not difficult to understand .

void PostOrderTraversal(BinTree BT)
{
    
    BinTree T;
    Stack TreeStack;
    TreeStack = CreateStack();

    T = BT;
    while (T || !IsEmpty(TreeStack)){
    
        while (T){
                              // Traverse left subtree 
            Push(TreeStack,T);
            T = T->Left;
        }
        T = Pop(TreeStack);
        if (T->flag != 54321){
                  //54321 Magic word , Indicates that the right subtree has been stacked 
            T->flag = 54321; 
            Push(TreeStack,T);              // Stack again , And traverse the right subtree 
            T = T->Right;
        } else {
    
            printf("%d ", T->Data);
            T = NULL;                       // Make good use of NULL Lead to the right subtree in the next cycle 
        }
    }
}

Complete code

/*  Tree traversal  */
#include "stdio.h"
#include "stdbool.h"
#include <stdlib.h>

/* type define for Tree */
typedef struct TNode *Position;
typedef Position BinTree; /*  Binary tree type  */
struct TNode{
               /*  Tree node definition  */
    int Data;           /*  Node data  */
    BinTree Left;       /*  Point to the left subtree  */
    BinTree Right;      /*  Point to the right subtree  */
    int flag;           /*  Used for post order traversal , Stack mark  */
};

/* type define for stack */
typedef BinTree ElementType;
typedef struct SNode *PtrToSNode;
struct SNode {
    
    ElementType Data;
    PtrToSNode Next;
};
typedef PtrToSNode Stack;

Stack CreateStack( ) 
{
     /*  Build a stack's head node , Return the node pointer  */
    Stack S;
 
    S = (Stack)malloc(sizeof(struct SNode));
    S->Next = NULL;
    return S;
}
 
bool IsEmpty ( Stack S )
{
     /*  Judgment stack S Is it empty , If you go back true; Otherwise return to false */
    return ( S->Next == NULL );
}
 
bool Push( Stack S, ElementType X )
{
     /*  Put the element X Push into the stack S */
    PtrToSNode TmpCell;
 
    TmpCell = (PtrToSNode)malloc(sizeof(struct SNode));
    TmpCell->Data = X;
    TmpCell->Next = S->Next;
    S->Next = TmpCell;
    return true;
}
 
ElementType Pop( Stack S )  
{
     /*  Delete and return to the stack S Top element of  */
    PtrToSNode FirstCell;
    ElementType TopElem;
 
    if( IsEmpty(S) ) {
    
        printf(" Stack empty "); 
        return NULL;
    }
    else {
    
        FirstCell = S->Next; 
        TopElem = FirstCell->Data;
        S->Next = FirstCell->Next;
        free(FirstCell);
        return TopElem;
    }
}

BinTree TreeCreat()    // Build the tree to be verified 
{
    
    BinTree T,BT;
    BT = (BinTree)malloc(sizeof(struct TNode));
    /* A */
    T = BT;             
    T->Data = 1;
    T->Left = (BinTree)malloc(sizeof(struct TNode));
    T->Right = (BinTree)malloc(sizeof(struct TNode));
    /* B */
    T = BT->Left;       
    T->Data = 2;        
    T->Left = (BinTree)malloc(sizeof(struct TNode));
    T->Right = (BinTree)malloc(sizeof(struct TNode));
    /* C */
    T = BT->Right;      
    T->Data = 3;
    T->Left = (BinTree)malloc(sizeof(struct TNode));
    T->Right = (BinTree)malloc(sizeof(struct TNode));
    /* D */
    T = BT->Left->Left; 
    T->Data = 4;
    T->Left = NULL;
    T->Right = NULL;
    /* E */
    T = BT->Left->Right; 
    T->Data = 5;
    T->Left = (BinTree)malloc(sizeof(struct TNode));
    T->Right = NULL;
    /* F */
    T = BT->Right->Left; 
    T->Data = 6;
    T->Left = NULL;
    T->Right = (BinTree)malloc(sizeof(struct TNode)); 
    /* G */
    T = BT->Right->Right; 
    T->Data = 7;
    T->Left = NULL;
    T->Right = NULL;
    /* H */
    T = BT->Left->Right->Left; 
    T->Data = 8;
    T->Left = NULL;
    T->Right = NULL;    
    /* I */
    T = BT->Right->Left->Right; 
    T->Data = 9;
    T->Left = NULL;
    T->Right = NULL;

    return BT;
}
void InorderTraversal(BinTree BT)
{
    
    BinTree T;
    Stack TreeStack;
    TreeStack = CreateStack();

    T = BT;
    while (T || !IsEmpty(TreeStack)){
    
        while (T){
    
            Push(TreeStack,T);
            T = T->Left;
        }
        T = Pop(TreeStack);
        printf("%d ", T->Data);
        T = T->Right;
    }

}
void PreOrderTraversal(BinTree BT)
{
    
    BinTree T;
    Stack TreeStack;
    TreeStack = CreateStack();

    T = BT;
    while (T || !IsEmpty(TreeStack)){
    
        while (T){
    
            printf("%d ", T->Data);
            Push(TreeStack,T);
            T = T->Left;
        }

        T = Pop(TreeStack);
        T = T->Right;
    }

}

void PostOrderTraversal(BinTree BT)
{
    
    BinTree T;
    Stack TreeStack;
    TreeStack = CreateStack();

    T = BT;
    while (T || !IsEmpty(TreeStack)){
    
        while (T){
                              // Traverse left subtree 
            Push(TreeStack,T);
            T = T->Left;
        }
        T = Pop(TreeStack);
        if (T->flag != 54321){
                  //54321 Magic word , Indicates that the right subtree has been stacked 
            T->flag = 54321; 
            Push(TreeStack,T);              // Stack again , And traverse the right subtree 
            T = T->Right;
        } else {
    
            printf("%d ", T->Data);
            T = NULL;                       // Make good use of NULL Lead to the right subtree in the next cycle 
        }
    }
}

void PreOrderTraversal_R(BinTree BT)
{
    
    if(BT){
    
        printf("%d ", BT->Data);
        PreOrderTraversal(BT->Left);
        PreOrderTraversal(BT->Right);
    }
}
void InOrderTraversal_R(BinTree BT)
{
    
    if(BT){
    
        InOrderTraversal_R(BT->Left);
        printf("%d ", BT->Data);
        InOrderTraversal_R(BT->Right);
    }
}
void PostOrderTraversal_R(BinTree BT)
{
    
    if(BT){
    
        PostOrderTraversal_R(BT->Left);
        PostOrderTraversal_R(BT->Right);
        printf("%d ", BT->Data);
    }
}
int main()
{
    
    BinTree BT = TreeCreat();
    printf("PostOrderTraversal_R:");
    PostOrderTraversal_R(BT);
    printf("\r\n");
    printf("PostOrderTraversal_L:");
    PostOrderTraversal(BT);
    printf("\r\n");
    return 0;
}

The structure of the tree constructed in the code