算法8（输入一颗二元查找树，将该树转换为它的镜像)

http://blog.csdn.net/yuucyf/article/details/6619352

 

题目：

输入一颗二元查找树，将该树转换为它的镜像，即在转换后的二元查找树中，左子树的结点都大于右子树的结点。
用递归和循环两种方法完成树的镜像转换。
例如输入：
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
};

思路一：

这道题很容易就让人想到解决方案，镜像的实现在这里可以直接交换左右节点就可以实现，用递归实现比较简单，用循环来实现的话就稍微麻烦一点，要借用队列来实现.

代码如下：

#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\n"), 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;
}