二元查找樹的翻轉（鏡像）的兩種思路

問題描述：
輸入一顆二元查找樹，將該樹轉換為它的鏡像，即在轉換後的二元查找樹中，左子樹的結點都大於右子樹的結點。

算法：

測試用例：

                                  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;