ステップ1は、データ構造の1−−nを学びます.

コードのみを送信します.コードのコメントには、二叉樹と二叉樹が含まれています.このブログのデータ系列で検索できます.すべてのコードは二叉樹操作博文のコードに加えて正常に実行できます.
 
一.前の順序を巡回:
  「ルートノード-左の子供-右の子供」の順に巡回して訪問します.
    再帰的に実現する:
 

//         

void pre_order_traversal(BTreeNode* root)

{

	if(NULL != root)

	{

		printf("%c, ", ((Node*)root)->v);

		

		pre_order_traversal(root->left);

		pre_order_traversal(root->right);

	}

}

 
   再帰的に実現されない:
       順を追って訪問の順にルートを訪問し、左の子供と右の子供をそれぞれ訪問します.つまり、いずれの結点についても、ルートの結点と見なすことができるので、直接に訪問してから、その左の子供が空でない場合は、同じ規則でその左の子樹を訪問することができる.左のツリーにアクセスすると、その右のツリーにアクセスします.

//          

void pre_orther_traversal(BTreeNode* root)

{

	/*

	      P：

 

     1)    P，    P  ;

 

     2)    P        ，   ，             ，

	                    P，   1);    ，  P 

	             P;

 

     3)  P NULL     ，     。

	*/

	LinkStack* stack = LinkStack_Create();

	

	BTreeNode* p = root;

	

	while((NULL != p) || (!LinkStack_Empty(stack)))

	{

		while(NULL != p)

		{

			printf("%c, ", ((Node*)p)->v);

			

			LinkStack_Push(stack, p);

			

			p = p->left;

		}

		

		if(!LinkStack_Empty(stack))

		{

			p = LinkStack_Top(stack);

			

			LinkStack_Pop(stack);

			

			p = p->right;

		}

	}

	

	LinkStack_Destroy(stack);

}

 
二.中の順序:
 中順で「左の子供-ルートの結点-右の子供」の順に訪問します.
再帰的に実現する:

//         

void middle_order_traversal(BTreeNode* root)

{

	if(NULL != root)

	{

		middle_order_traversal(root->left);

		

		printf("%c, ", ((Node*)root)->v);

		

		middle_order_traversal(root->right);

	}

}

 
再帰的に実現されない:
       順序よく通る順に、いずれかの結点については、左の子供を優先的に訪問し、左の子供は結点として見られ、左の子供の結点に続き、左の子供が結点が空いている結点に出会うまで訪問し、同じ規則で右の子樹にアクセスします.

//          

void middle_orther_traversal(BTreeNode* root)

{

	/*

	      P，

 

  1)        ，  P    P         P，       P        ；

 

  2)       ，             ，       ，      P          ；

 

  3)  P NULL          



	*/

	LinkStack* stack = LinkStack_Create();

	

	BTreeNode* p = root;

	

	while((NULL != p) || (!LinkStack_Empty(stack)))

	{

		while(NULL != p)

		{



			

			LinkStack_Push(stack, p);

			

			p = p->left;

		}

		

		if(!LinkStack_Empty(stack))

		{

			p = LinkStack_Top(stack);

			

			printf("%c, ", ((Node*)p)->v);

			

			LinkStack_Pop(stack);

			

			p = p->right;

		}

	}

	

	LinkStack_Destroy(stack);

}

 
三.後序を巡回する
 「左の子供-右の子供-ルートの接合点」の順に巡回して訪問します.
再帰的に実現する:
 

//         

void post_order_traversal(BTreeNode* root)

{

	if(NULL != root)

	{

		post_order_traversal(root->left);

		post_order_traversal(root->right);

		

		printf("%c, ", ((Node*)root)->v);

	}

}

 
再帰的に実現されない:

//          

void post_orther_traversal(BTreeNode* root)

{

	/*

	                      ，        P，     。

	           P          ，        ；

	           P          ，

	                          ，            。

	        ，  P            ，                ，

	            ，                 。

	*/

	LinkStack* stack = LinkStack_Create();

	

	BTreeNode* cur ;//    

	BTreeNode* pre = NULL;//         

	

	LinkStack_Push(stack, root);

	

	while(!LinkStack_Empty(stack))

	{

		//                         

		cur = (BTreeNode*)LinkStack_Top(stack);

		

		if(((NULL==cur->left)&&(NULL==cur->right)) || 

		  (

		    (NULL!=pre) && ((pre==cur->left) || (pre==cur->right))  ))

		  {

  				printf("%c, ", ((Node*)cur)->v);

  				

  				LinkStack_Pop(stack);

  				

  				pre = cur;

  		}

  		else

  		{

		  	if(NULL != cur->right)

		  	{

	  			LinkStack_Push(stack, cur->right);

	  		}

	  		if(NULL != cur->left)

	  		{

		  		LinkStack_Push(stack, cur->left);

		  	}

  		}

	}

	

	LinkStack_Destroy(stack);

}