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

問題描述：

輸入一顆二進制查找樹，将該樹轉換為它的鏡像，

即在轉換後的二進制查找樹中，左子樹的結點都大于右子樹的結點。

算法：

測試用例：

                                  10

                             /             \

                           5               11

                       /        \

                    3            7

                 /     \         /   \

               2       4     6      9

             /                       /

          1                       8

算法：

有兩種思路：

①遞歸。對樹翻轉，隻需對他的左右子樹翻轉，再交換左右子樹的位置即可。

②非遞歸。設定一個隊列queue，從根節點開始處理：人節點先入列，當隊列非空時，循環進行以下處理：從隊列中取出一節點，交換他的左右子樹的位置，将它的左右子節點入列（若存在的話）。當隊列為空時，傳回。

代碼實作：

①遞歸

<p align="left"><pre name="code" class="cpp">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;