输入一颗二元查找树，将该树转换为它的镜像

第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
};

[cpp] #include
#include
#include
using namespace std;
//定义二元查找树的结点为：
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
};
void cfun(BSTreeNode *pt)
{
if(!pt){
return;
}
BSTreeNode * ptem=pt->m_pLeft;
pt->m_pLeft=pt->m_pRight;
pt->m_pRight=ptem;
if(pt->m_pLeft){
cfun(pt->m_pLeft);
}
if(pt->m_pRight){
cfun(pt->m_pRight);
}
}
//考虑用循环实现这个算法
void MirrorIteratively(BSTreeNode *pTreeHead)
{
if(!pTreeHead)
return;

std::stack stackTreeNode;
stackTreeNode.push(pTreeHead);

while(stackTreeNode.size())
{
BSTreeNode *pNode = stackTreeNode.top();
stackTreeNode.pop();

// swap the right and left child sub-tree
BSTreeNode *pTemp = pNode->m_pLeft;
pNode->m_pLeft = pNode->m_pRight;
pNode->m_pRight = pTemp;

// push left child sub-tree into stack if not null
if(pNode->m_pLeft)
stackTreeNode.push(pNode->m_pLeft);

// push right child sub-tree into stack if not null
if(pNode->m_pRight)
stackTreeNode.push(pNode->m_pRight);
}
}
//这个题目展示了递归变成循环的方法
int main()
{

system("pause");
return 0;
}

#include
#include
#include
using namespace std;
//定义二元查找树的结点为：
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
};
void cfun(BSTreeNode *pt)
{
if(!pt){
return;
}
BSTreeNode * ptem=pt->m_pLeft;
pt->m_pLeft=pt->m_pRight;
pt->m_pRight=ptem;
if(pt->m_pLeft){
cfun(pt->m_pLeft);
}
if(pt->m_pRight){
cfun(pt->m_pRight);
}
}
//考虑用循环实现这个算法
void MirrorIteratively(BSTreeNode *pTreeHead)
{
if(!pTreeHead)
return;

std::stack stackTreeNode;
stackTreeNode.push(pTreeHead);

while(stackTreeNode.size())
{
BSTreeNode *pNode = stackTreeNode.top();
stackTreeNode.pop();

// swap the right and left child sub-tree
BSTreeNode *pTemp = pNode->m_pLeft;
pNode->m_pLeft = pNode->m_pRight;
pNode->m_pRight = pTemp;

// push left child sub-tree into stack if not null
if(pNode->m_pLeft)
stackTreeNode.push(pNode->m_pLeft);

// push right child sub-tree into stack if not null
if(pNode->m_pRight)
stackTreeNode.push(pNode->m_pRight);
}
}
//这个题目展示了递归变成循环的方法
int main()
{

system("pause");
return 0;
}