求二進制查找樹的鏡像

題目：輸入一顆二進制查找樹，将該樹轉換為它的鏡像，即在轉換後的二進制查找樹中，左子樹的結點都大于右子樹的結點。用遞歸和循環兩種方法完成樹的鏡像轉換。

例如輸入：

     8

    /  \

  6      10

 /\       /\

5  7    9   11

輸出：

      8

  10    6

 /\      /\

11  9  7  5

定義二進制查找樹的結點為：

分析：盡管我們可能一下子不能了解鏡像是什麼意思，但上面的例子給我們的直覺感覺，就是交換結點的左右子樹。我們試着在周遊例子中的二進制查找樹的同時來交換每個結點的左右子樹。周遊時首先通路頭結點8，我們交換它的左右子樹得到：

      8

  10    6

 /\      /\

9  11  5  7

我們發現兩個結點6和10的左右子樹仍然是左結點的值小于右結點的值，我們再試着交換他們的左右子樹，得到：

11  9  7   5

剛好就是要求的輸出。

上面的分析印證了我們的直覺：在周遊二進制查找樹時每通路到一個結點，交換它的左右子樹。這種思路用遞歸不難實作，将周遊二進制查找樹的代碼稍作修改就可以了。參考代碼如下：

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

<code>///////////////////////////////////////////////////////////////////////</code>

<code>// Mirror a BST (swap the left right child of each node) recursively</code>

<code>// the head of BST in initial call</code>

<code>void</code> <code>MirrorRecursively(BSTreeNode *pNode)</code>

<code>{</code>

<code>      </code><code>if</code><code>(!pNode)</code>

<code>            </code><code>return</code><code>;</code>

<code>      </code><code>// swap the right and left child sub-tree</code>

<code>      </code><code>BSTreeNode *pTemp = pNode-&gt;m_pLeft;</code>

<code>      </code><code>pNode-&gt;m_pLeft = pNode-&gt;m_pRight;</code>

<code>      </code><code>pNode-&gt;m_pRight = pTemp;</code>

<code>      </code><code>// mirror left child sub-tree if not null</code>

<code>      </code><code>if</code><code>(pNode-&gt;m_pLeft)</code>

<code>            </code><code>MirrorRecursively(pNode-&gt;m_pLeft); </code>

<code>      </code><code>// mirror right child sub-tree if not null</code>

<code>      </code><code>if</code><code>(pNode-&gt;m_pRight)</code>

<code>            </code><code>MirrorRecursively(pNode-&gt;m_pRight);</code>

<code>}</code>

 得出求一棵樹的鏡像的過程：先前序周遊這棵樹的每個結點，如果周遊到的結點有子結點，就交換它的兩個子結點。當交換完所有非葉子結點的左右結點之後，就得到了樹的鏡像。

由于遞歸的本質是編譯器生成了一個函數調用的棧，是以用循環來完成同樣任務時最 簡單的辦法就是用一個輔助棧來模拟遞歸。首先我們把樹的頭結點放入棧中。在循環中，隻要棧不為空，彈出棧的棧頂結點，交換它的左右子樹。如果它有左子樹， 把它的左子樹壓入棧中；如果它有右子樹，把它的右子樹壓入棧中。這樣在下次循環中就能交換它兒子結點的左右子樹了。參考代碼如下：

23

24

25

26

27

28

29

30

31

<code>// Mirror a BST (swap the left right child of each node) Iteratively</code>

<code>// Input: pTreeHead: the head of BST</code>

<code>void</code> <code>MirrorIteratively(BSTreeNode *pTreeHead)</code>

<code>      </code><code>if</code><code>(!pTreeHead)</code>

<code>      </code><code>std::stack&lt;BSTreeNode *&gt; stackTreeNode;</code>

<code>      </code><code>stackTreeNode.push(pTreeHead);</code>

<code>      </code><code>while</code><code>(stackTreeNode.size())</code>

<code>      </code><code>{</code>

<code>            </code><code>BSTreeNode *pNode = stackTreeNode.top();</code>

<code>            </code><code>stackTreeNode.pop();</code>

<code>            </code><code>// swap the right and left child sub-tree</code>

<code>            </code><code>BSTreeNode *pTemp = pNode-&gt;m_pLeft;</code>

<code>            </code><code>pNode-&gt;m_pLeft = pNode-&gt;m_pRight;</code>

<code>            </code><code>pNode-&gt;m_pRight = pTemp;</code>

<code>            </code><code>// push left child sub-tree into stack if not null</code>

<code>            </code><code>if</code><code>(pNode-&gt;m_pLeft)</code>

<code>                  </code><code>stackTreeNode.push(pNode-&gt;m_pLeft);</code>

<code>            </code><code>// push right child sub-tree into stack if not null</code>

<code>            </code><code>if</code><code>(pNode-&gt;m_pRight)</code>

<code>                  </code><code>stackTreeNode.push(pNode-&gt;m_pRight);</code>

<code>      </code><code>}</code>

本文轉自夏雪冬日部落格園部落格，原文連結：http://www.cnblogs.com/heyonggang/p/3406981.html，如需轉載請自行聯系原作者