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

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

问题描述：
输入一颗二元查找树，将该树转换为它的镜像，即在转换后的二元查找树中，左子树的结点都大于右子树的结点。

算法：

测试用例：

                                  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;

本文永久更新链接地址：