두 갈래 정렬 트 리 에서 귀속 파라미터 의 전달 을 보다

재 귀 를 사용 한 후부 터 재 귀 는 예술 이 라 고 말 할 수 밖 에 없다!재 귀적 인 주요 사상 은 스 택 의 순서 방문 구 조 를 모방 하여 과정 에서 프로그램 설계 에서 아래 에서 위로 방문 하 는 순서 에서 방문 하 는 데이터 구조 에 대한 저장 을 절약 하 는 것 이다.
재 귀 호출 에서 적 게 보충 하여 각 재 귀 함수 에서 파 라 메 터 를 전달 합 니 다.본 고 는 이 진 트 리 를 링크 로 전환 하 는 것 을 예 로 들 어 두 가지 매개 변수 전달 방안 을 제시 했다. 즉, 전체 변수 와 매개 변수 전달 이다.
1. 이 진 트 리 를 링크 로 변환
마이크로소프트 면접 100 문제 참조, 문제 1;
2. 전역 변수 전달 재 귀 매개 변수 - 중간 순서 로 이 진 트 리 옮 겨 다 니 기
 이 문 제 를 처음 보면 재 귀적 으로 실현 할 수 있 습 니 다. 현재 노드 의 방문 에서 전구 결점 을 참조 하여 현재 노드 의 왼쪽 지침 을 그의 전구 결점 을 가리 킬 수 있 습 니 다.그리고 전구 결점 의 오른쪽 지침 을 바 꾸 어 현재 값 을 가리 키 게 합 니 다.
중간 순서 로 이 진 트 리 를 한 번 옮 겨 다 니 면 이 진 트 리 가 바 뀌 는 양 방향 링크 를 얻 을 수 있 습 니 다.

/************************************************************************/
/*                                                                 */
/*
    ，         ；               ，       ，        */
/************************************************************************/
//            ，
/*pnode phead = NULL,ptail = NULL;
void incover_point(pnode pcurrent)
{
	//pn->lchild       ，ptail         ，                 
	//              
	pcurrent->lchild = ptail;
	if (!ptail)
		phead = pcurrent;
	else //              
              ptail->rchild = pcurrent;
	ptail = pcurrent;
	printf("current data :%d
", pcurrent->key);
}
int tree_to_list(pnode ptree)
{
	if (!ptree)
	 return 0;
	if (ptree->lchild)
		tree_to_list(ptree->lchild);
	incover_point(ptree);
	if (ptree->rchild)
	   tree_to_list(ptree->rchild);
     return 0;	
}*/

3. 매개 변수 전달 재 귀 매개 변수 - 이 진 트 리 를 추가 로 옮 겨 다 니 기
다음 에 옮 겨 다 니 면 이 진 트 리 링크 가 뒤 집 히 는데 주로 현재 노드 의 직접 전구 와 직접 후계 한 다음 에 세 개의 노드 의 방향 을 바 꿉 니 다.실 현 된 코드 는 다음 과 같다.

/************************************************************************/
/*        ，                                          */
/*
phead            ，ptail           
*/
/************************************************************************/

void helper(pnode *phead, pnode *ptail, pnode ptree)
{
	pnode left = NULL, right =NULL;
	if(!ptree)
	{
		*phead = NULL;
		*ptail = NULL;
		return;
	}
	//&&&&&     ，     &&&&&&，      
	//left         ，        
	//right         ，        
	helper(phead, &left,  ptree->lchild);//          
	helper(&right, ptail, ptree->rchild);//          
	printf("node %d
",  ptree->key);
	if ((left) != NULL )
	{
		printf("left node is %d
", (left)->key);
		(left)->rchild = ptree;
		ptree->lchild = left;
	}
	else//phead            
	{   
		//   ，         
		*phead = ptree;
		printf("head node is %d
", (*phead)->key);
	}
	if ((right) != NULL)
	{
		printf("right node is %d
", (right)->key);
		ptree->rchild = right;
		(right)->lchild = ptree;
	}
	else//ptail           
	{
		//   ，         
		*ptail = ptree;
	    printf("ptail node is %d
", (*ptail)->key);
	}
	//, head is %d tail is %d left is  %d right is  %d
", (*phead)->key, (*ptail)->key, left->key, right->key);
}
pnode tree_to_list(pnode ptree)
{
	pnode phead, ptail;
	helper(&phead, &ptail, ptree);
	return phead;
}

10 결점 의 전구 결점 을 찾 는 것 을 예 로 들 면:
1.helper(&right, ptail, 6->rchild);의 접근 에서 ptail 의 값 을 바 꾸 어 8 을 가리 키 게 합 니 다.
2. 결점 6 의 귀속 차원 을 되 돌려 주 고 결점 이 변 경 된 값 은 helper (phead, & left, ptree - > lchild) 로 되 돌려 줍 니 다.인자 left 에서 10 결점 의 전구 결점 으로 되 돌아 갑 니 다.
 
helper(phead, &left,  ptree->lchild);//왼쪽 재 귀 는 체인 의 첫 번 째 매듭 점 만 바 꿉 니 다.  
             ↓       ↑
helper(&right, ptail, ptree->rchild);//오른쪽 재 귀 는 체인 끝 점 만 변경 합 니 다.  
  구체 적 으로 말 하면 왼쪽 트 리 를 옮 겨 다 니 면서 가장 오른쪽 에 있 는 결점 으로 돌아 가 는 것 이다.오른쪽 트 리 를 옮 겨 다 니 면서 가장 왼쪽 의 결점 을 되 돌려 줍 니 다.