매일 알고리즘 시리즈 (15) 를 배 웁 니 다.

제목:
이원 찾기 트 리 를 입력 하여 이 나 무 를 거울 로 변환 합 니 다. 즉, 변 환 된 이원 찾기 트 리 에서 왼쪽 나무의 결점 은 모두 오른쪽 나무의 결점 보다 큽 니 다.재 귀 와 순환 두 가지 방법 으로 나무의 미 러 전환 을 완성 하 다.예 를 들 어 입력: 8 / \ 6 10 / \ / \ 5 7 9 11 출력: 8 / \ 10 6 / \ / \ \ \ 11 9 7 5 정의 이원 탐색 트 리 의 결산 점 은 struct BSTreeNode / / a node in the binary search tree (BST) {int m nValue; / / value of node BSTreeNode * m pLeft; / / left child of node BSTreeNode * m pRight; / / right child of node} 입 니 다.
 
사고방식 1:
이 문 제 는 쉽게 해결 방안 을 떠 올 리 게 한다. 미 러 의 실현 은 여기 서 좌우 노드 를 직접 교환 하면 실현 할 수 있 고 재 귀적 으로 실현 하 는 것 이 비교적 간단 하 다. 순환 으로 실현 하면 조금 번 거 롭 고 대열 을 빌려 실현 해 야 한다.
 
코드 는 다음 과 같 습 니 다:

#include "stdafx.h"
#include <assert.h>
#include "Queue.h"

/*--------------------------------
             .
Copyright by yuucyf.     2011.07.18
----------------------------------*/

void AddBSTreeNode(S_BSTreeNode* &pRoot, int nValue)
{
	if (NULL == pRoot)
	{
		pRoot = new S_BSTreeNode;
		assert(NULL != pRoot);
		pRoot->nValue = nValue;
		return;
	}

	if (pRoot->nValue > nValue)
	{
		AddBSTreeNode(pRoot->psLeft, nValue);
	}
	else if ( pRoot->nValue < nValue)
	{
		AddBSTreeNode(pRoot->psRight, nValue);
	}
}

void SwapLeftRightNode(S_BSTreeNode* psNode)
{
	S_BSTreeNode *pTemp = psNode->psLeft;
	psNode->psLeft = psNode->psRight;
	psNode->psRight = pTemp;
}

//    .
void BuildImage_Recursion(S_BSTreeNode* psNode)
{
	if (NULL == psNode)
		return;

	SwapLeftRightNode(psNode);

	BuildImage_Recursion(psNode->psLeft);
	BuildImage_Recursion(psNode->psRight);
}


//    .(    ，       )
void BuildImage_Loop(S_BSTreeNode* psNode)
{
	if (NULL == psNode)
		return;
	
	C_Queue<S_BSTreeNode *> queueNode;
	queueNode.QInsert(psNode);
	while (!queueNode.QEmpty())
	{
		psNode = queueNode.QDelete();

		SwapLeftRightNode(psNode);
		if (psNode->psLeft)
			queueNode.QInsert(psNode->psLeft);
		if (psNode->psRight)
			queueNode.QInsert(psNode->psRight);
	}	
}

void PrintfAllNodeValue(const S_BSTreeNode* psNode)
{
	if (NULL == psNode)
		return;

	_tprintf(_T("%d
"), psNode->nValue);
	PrintfAllNodeValue(psNode->psLeft);
	PrintfAllNodeValue(psNode->psRight);
}

int _tmain(int argc, _TCHAR* argv[])
{
	S_BSTreeNode *psRoot = NULL;
	AddBSTreeNode(psRoot, 8);
	AddBSTreeNode(psRoot, 6);
	AddBSTreeNode(psRoot, 10);
	AddBSTreeNode(psRoot, 5);
	AddBSTreeNode(psRoot, 7);
	AddBSTreeNode(psRoot, 9);
	AddBSTreeNode(psRoot, 11);

	PrintfAllNodeValue(psRoot);
	//BuildImage_Recursion(psRoot);
	BuildImage_Loop(psRoot);
	PrintfAllNodeValue(psRoot);

	return 0;
}