한 걸음 한 걸음 데이터 구조의 1 - n (이 진 트 리 옮 겨 다 니 기 - 비 재 귀적 실현)

코드 만 보 내 고 코드 설명 에 있 습 니 다. 이 진 트 리 와 이 진 트 리 가 정 의 를 옮 겨 다 니 면 본 블 로그 데이터 시리즈 에서 찾 을 수 있 습 니 다. 모든 코드 가 이 진 트 리 조작 박문 에 추 가 된 코드 는 정상적으로 실 행 될 수 있 습 니 다.
 
1. 앞 순 서 를 옮 겨 다 니 기:
  앞 순 서 는 '뿌리 결점 - 왼쪽 아이 - 오른쪽 아이' 순서 로 방문 합 니 다.
    순환 실현:
 

//         

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);

}

 
2. 중간 순서 옮 겨 다 니 기:
 중 서 는 '왼쪽 아이 - 뿌리 결산 점 - 오른쪽 아이' 순서 로 방문 합 니 다.
순환 실현:

//         

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);

}

 
3. 후 서 를 옮 겨 다 닌 다
 후 서 는 '왼쪽 아이 - 오른쪽 아이 - 뿌리 결산 점' 순서에 따라 방문 합 니 다.
순환 실현:
 

//         

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);

}