[데이터 구조] 이 진 트 리 회전 양 방향 링크

목차

예제 설명

코드 구현

코드 구현 2

예제 설명
이 두 갈래 나 무 를 정렬 된 양 방향 링크 로 변환 합 니 다.새로운 노드 를 만 들 수 없고 트 리 의 노드 포인터 의 방향 만 조정 할 수 있 습 니 다.
이 진 트 리 결점 구조 체 정의

struct TreeNode {
	struct TreeNode *left;
	struct TreeNode *right;
};

코드 구현

Node *prev = NULL;		//              
void NodeToDoublyLink(Node *node) {
	node->left = prev;	// node->prev = prev;
	if (prev != NULL) {
		prev->right = node;	// prev->next = node;
	}
	prev = node;
}
void InOrder(Node *root) {
	if (root != NULL) {
		InOrder(root->left);
		NodeToDoublyLink(root);	//   root
		InOrder(root->right);
	}
}

코드 구현 2

Node*  Convert(Node* pRoot){
	Node* pLastNode = NULL;	
	ConvertNode(pRoot ， pLastNode);
 	
 	//pLastNode           ，         。
	Node* pHead = pLastNode;
	while (pHead  && pHead->pLeft ){ //          
		pHead = pHead->Left;
	}
	return pHead;
}
 
void ConvertNode(Node* pNode ，Node*&  pLastNode){
	if (pNode == NULL)
		return;
		
	Node* pCur = pNode;
	//            
	if (pCur->Left)
		ConvertNode(pCur->Left, pLastNode);
		
	pCur->Left = pLastNode;  //   
 
	if (pLastNode)
		pLastNode->Right = pCur;
		
	pLastNode = pCur;    //   
 
	if (pCur->Right)
		ConvertNode(pCur->Right, pLastNode);
}

만약 ConvertNode 함수 의 두 번 째 매개 변수 가 2 급 지침 이 라면 Node*& pLastNode 을 Node** pLastNode 로 바 꾸 는 것 을 제외 하고 코드 에서 모든 pLastNode 을 *pLastNode 로 바 꾸 면 됩 니 다.