二元查找树的翻转（镜像）的两种思路

问题描述：
输入一颗二元查找树，将该树转换为它的镜像，即在转换后的二元查找树中，左子树的结点都大于右子树的结点。算法：测试用例：
10 / 5 11 / 3 7 / / 2 4 6 9 / / 1 8算法：
有两种思路：①递归。对树翻转，只需对他的左右子树翻转，再交换左右子树的位置即可。②非递归。设置一个队列queue，从根节点开始处理：人节点先入列，当队列非空时，循环进行以下处理：从队列中取出一节点，交换他的左右子树的位置，将它的左右子节点入列（若存在的话）。当队列为空时，返回。代码实现：①递归template<class T>
void ReverseTree（BinaryTreeNode<T>* t）
{
if （！t）
return;
BinaryTreeNode<T>* temp = new BinaryTreeNode<T>;
temp = t->LeftChild;
t->LeftChild = t->RightChild;
t->RightChild = temp;
ReverseTree（t->LeftChild）;
ReverseTree（t->RightChild）;
return;
}非递归：//非递归
template<class T>
void ReverseTree2（BinaryTreeNode<T>* t）
{
if （！t）
return;
Queue<BinaryTreeNode<T>*> q;
q.Add（t）;
BinaryTreeNode<T>* tt = new BinaryTreeNode < T >;
while （！q.IsEmpty（））
{
q.Delete（tt）;
BinaryTreeNode<T>* temp = new BinaryTreeNode < T >;
temp = tt->LeftChild;
tt->LeftChild = tt->RightChild;
tt->RightChild = temp;
if （tt->LeftChild）
q.Add（tt->LeftChild）;
if （tt->RightChild）
q.Add（tt->RightChild）;
}
}输出测试：InOrder（n10）;
cout << endl;
ReverseTree（n10）;
InOrder（n10）;
cout << endl; ReverseTree2（n10）;
InOrder（n10）;
cout << endl;本文永久更新链接地址：http://www.linuxidc.com/Linux/2014-12/110862.htm