Introduction to in-order traversal (non-recursive, recursive) after binary tree traversal

一、引言

A common method of traversing a binary tree is preorder traversal、中序遍历、Post-order traversal and hierarchical traversal, etc,本文给出了CNon-recursive and recursive algorithms for postorder traversal of binary trees in the language version.
Postorder traversal is not as simple as preorder traversal,It is the most complicated traversal method.The order in which nodes are visited is ：“左—>右—>根”,That is, the left subtree is visited first,Then visit the right subtree,最后访问树根.对于左、右子树而言,The order of its visits remains the same“左—>右—>根”.也就是说,for each subtree,Both are the last to visit the root of the tree.
It can be seen from the above description that the traversal process is actually a recursive process,So it can be implemented using recursive algorithm,But the same can also be achieved using non-recursive methods.

二、The post-order traversal of a binary tree is a detailed demonstration of the process

1、假设二叉树（left and right subtrees）如下图所示：

Then the post-order traversal process is ：左子树b—>右子树c—>树根a
2、假设二叉树（没有右子树）如下图所示：

Then the post-order traversal process is ：左子树b—>树根a
3、假设二叉树（没有左子树）如下图所示：

Then the post-order traversal process is ：右子树c—>树根a
4、For a slightly more complicated binary tree,如下图所示：

The post-order traversal process is demonstrated as follows（“左—>右—>根”）
Step 1. First visit the node d

Step 2. 访问结点 g

Step 3. 访问结点 e

Step 4. 访问结点b

Step 5. 访问结点h

Step 6. 访问结点f

Step 7. 访问结点c

Step 8. 访问树根a

At this point, the in-order traversal of the binary tree ends,遍历结果为：d g e b h f c a
5、Repeat access flag
during this traversal,It will be found that the root of the tree and the root of the subtree will be visited twice,为了避免这个问题,Don't visit when you first encounter it,And visit again the second time you meet,Hence an access flag was introduced.
三、Source code for postorder traversal of a binary tree：
1、Node structure and conditional compilation

typedef struct node
{
    
	datatype data;
	struct node *Lchild;
	struct node *Rchild;
	int    flag;
}BiTree;
#ifdef CHAR
typedef char datatype;
#else
typedef int datatype;
#endif

2、递归算法

void  PostorderSearch_Recu( BiTree  *T)
{
      
	if  (T!=NULL) 
	{
         
		PostorderSearch_Recu(T->Lchild) ;
		PostorderSearch_Recu(T->Rchild) ; 
		VisitNode(T->data) ;        
	}
} 

3、非递归算法

void PostorderSearch( BiTree *T )
{
    
	BiTree *p, *stack[ MAX_NODE ];
	int top = 0;//栈顶位置下标
	if( T == NULL ) 
	{
    
		return;
	}
	p = T;
	while( 1 )
	{
    
		if( p != NULL )//p非空,则入栈,之后p向左走 
		{
    
			stack[ top++ ] = p;
			p = p->Lchild;
		}
		else//p为空,则出栈 
		{
    
			p = stack[ --top ];
			//右为空,且flag为真,则访问,之后p置空 
			if( p->Rchild == NULL || p->flag == 1 )
			{
    
				VisitNode( p->data );
				p = NULL;
			} 
			else//右非空,则p重新入栈,Repeated push flagflag置为真,之后p向右走
			{
    
				stack[ top++ ] = p;
				p->flag = 1;
				p = p->Rchild;
			}
		} 
		if( top == 0 )//栈为空,则结束遍历
		{
    
			break;
		}
	}
}

4、VisitNode函数如下：

void VisitNode( datatype data )
{
    
#ifdef CHAR
	printf( "%5c", data );
#else
	printf( "%5d", data );
#endif
}

补充：Combine the algorithm for creating a binary tree from the previous article,The binary tree creation and post-order traversal of the binary tree can be completely implemented.The algorithm created is not repeated here.