Recursive traversal and non recursive traversal of binary tree (C language version)

Go straight to the code , It can run directly .

#include <stdio.h>
#include<string.h>
#include <stdlib.h>
#include <stdbool.h>
/** Binary tree data structure definition **/
struct treenode
{
    
    char val;
    struct treenode *left;
    struct treenode *right;
}treenode;

// Build a binary tree 
struct treenode* build_tree(char* s,int i)
{
    

    if(i>=strlen(s))return NULL;
    if(s[i]=='#')return NULL;
    //printf("%d\n",i);
    struct treenode* root=(struct treenode*)malloc(sizeof(treenode));
    root->val=s[i];
    if(2*i+1<strlen(s))root->left=build_tree(s,2*i+1);
    else root->left=NULL;
    if(2*i+2<strlen(s))root->right=build_tree(s,2*i+2);
    else root->right=NULL;
    return root;
}
// First root recursion traversal 
void preOrder(struct treenode* root)
{
    
    if(root==NULL)return ;
    printf("%c",root->val);
    if(root->left!=NULL)preOrder(root->left);
    if(root->right!=NULL)preOrder(root->right);
}
// Middle root recursive traversal 
void inOrder(struct treenode* root)
{
    
    if(root==NULL)return ;
    inOrder(root->left);
    printf("%c",root->val);
    inOrder(root->right);
}
// Post root recursive traversal 
void postOrder(struct treenode* root)
{
    
    if(root==NULL)return ;
    postOrder(root->left);
    postOrder(root->right);
    printf("%c",root->val);
}
// First root non recursive traversal 
//ABC#DE#
void Pre1Order(struct treenode *bt)
{
    
    struct treenode **s;
	struct treenode *p;
	int top=-1;
	// Create a stack ;
	s=(struct treenode **)malloc((100+1)*sizeof(struct treenode *));
	// Initialization stack ;
	s[++top]=bt;
	// Non recursive preamble traversal ;
	while(top!=-1)
	{
    
		p=s[top--];
		printf("%c",p->val);    // The characteristics of the stack , First in, then out ;
		if(p->right)
			s[++top]=p->right;
		if(p->left)
			s[++top]=p->left;
	}
	free(s);
}

void In1Order(struct treenode *bt)
{
    
	struct treenode **s;
    struct treenode *p,*q;
    int top=-1;
	// Create a stack ;
	s=(struct treenode **)malloc((100+1)*sizeof(struct treenode *));
	// Non recursive middle order traversal ;
    if(bt)
    {
    
        while(bt)   // Traverse the left subtree until the left child of the node is empty ;
        {
    
            s[++top]=bt;   // Put all the left children in the stack ;
            bt=bt->left;     // Point to the next left subtree ;
        }
        while(top!=-1)  // When the stack is empty, the loop ends ;
        {
    
            p=s[top--];// At first, it will be the most p Point to the left child in the lower left corner , And move to the parent node of the node ;
            printf("%c",p->val);  // Output the node in the lower left corner ;
            while(p->right)  // Traverse whether the node has a right node after moving ;
            {
    
                s[++top]=p->right;   // Stack the right subtree of this node ;
                q=p->right;		  // This right subtree node is assigned to q;
                while(q->left)      // Judge node q Is there a left subtree ;
                {
    
                    s[++top]=q->left;  // There's a Zuozi tree , Put all the left subtrees connected to this node on the stack ;
                    q=q->left;
                }
                break;   // End the current cycle , Back to the second while The loop continues with the previous step ;
            }
        }
    }
}


void Post1Order(struct treenode *bt)
{
    
	struct treenode **s;
	struct treenode *p;
    int top=-1;
	// Create a stack ;
	s=(struct treenode **)malloc((100+1)*sizeof(struct treenode *));
	// Non recursive postorder traversal ;
    do
    {
    
        while(bt)     // Traverse the left subtree until the left child of the left subtree is empty ;
        {
    
            s[++top]=bt;     // Put all the left children in the stack ;
            bt=bt->left;   // Point to the next left subtree ;
        }
        p=NULL;
        while(top!=-1)
        {
    
            bt=s[top];
            if(bt->right==p)  //p: Expressed as null, Or the right child node has been accessed ;
            {
    
                printf("%c",bt->val);   // Output node data field ;
                top--;           // After output ,top--;
                p=bt;  //p Record the node you just visited ;
            }
            else
            {
    
                bt=bt->right;   // Access the right subtree node ;
                break;
            }
        }
    }while(top!=-1);
}



int main()
{
    
    char s[100]={
    0};
    gets(s);
    struct treenode* root=(struct treenode*)malloc(sizeof(struct treenode));
    root=build_tree(s,0);
    printf(" Recursive traversal ：\n");
    printf(" First root  ");
    preOrder(root);
    printf("\n");

    printf(" Nakagan  ");
    inOrder(root);
    printf("\n");
    printf(" Posterior root  ");
    postOrder(root);
    printf("\n");
    printf(" Non recursive traversal ：\n");
    printf(" First root  ");
    Pre1Order(root);
    printf("\n");
    printf(" Nakagan  ");
    In1Order(root);
    printf("\n");
    printf(" Posterior root  ");
    Post1Order(root);
    printf("\n");
    return 0;

}