遞歸再一次讓哥震驚了

遞歸再一次讓哥震驚了

先說那兩個讓哥震驚的遞歸問題：

1：用遞歸實作單連結清單的倒序輸出

2：從二叉查找樹中删除節點，并保證還是二叉查找樹

同學們可以開始思考這兩個問題了，當然你可能N年前就遇到過這兩個問題，那麼不妨看看，看你是否真的了解了遞歸。實作這兩個問題的代碼當然很簡單，就在下面。

百度百科中遞歸的名片：遞歸做為一種算法在程式設計語言中廣泛應用.是指函數/過程/子程式在運作過程中直接或間接調用自身而産生的重入現象.遞歸是計算機科學的一個重要概念,遞歸的方法是程式設計中有效的方法,采用遞歸編寫程式能使程式變得簡潔和清晰。

剛開始學習的遞歸的時候，覺得他好強大，實作某些功能不用遞歸可能要幾十行代碼，用遞歸可能幾行就搞定了，而且代碼清晰簡潔。一直以為遞歸也就是自己調用自己，有一個出口條件，讓他停止遞歸，退出函數，其實的特點并非就這些。

遞歸還有一個非常重要的特點：先進後出，跟棧類似，先遞進去的後遞出來。由于遞歸一直在自己調用自己，有時候我們很難清楚的看出，他的傳回值到底是哪個，隻要你了解了先進後出這個特點，你就會明白，第一次調用時，作為傳回值的那個變量的值就是遞歸函數的傳回值。先進後出嗎，他是第一個進來，也就是最後出去的那個，當然就是遞歸的傳回值啦。

第一個讓哥震驚的問題：用遞歸實作單連結清單的倒序輸出。

<a></a>

這裡充分運用了遞歸的先進後出的特點。

先來C++版的吧，好久沒寫了，都生疏了：

View Code

在來C#版：

<a href="http://www.cnblogs.com/hlxs/archive/2011/12/22/2297484.html#">+ View Code</a>

 現在我們重點來看看，删除節點的算法：

<code>//删除指定節點下的節點</code>

<code>      </code><code>public</code> <code>TreeNode Delete(</code><code>int</code> <code>element, TreeNode node)</code>

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

<code>          </code><code>if</code> <code>(node ==</code><code>null</code><code>)</code>

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

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

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

<code>          </code><code>if</code> <code>(element &lt; node.Element)</code>

<code>              </code><code>node.Left = Delete(element, node.Left);</code>

<code>          </code><code>else</code> <code>if</code> <code>(element &gt; node.Element)</code>

<code>              </code><code>node.Right = Delete(element, node.Right);</code>

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

<code>              </code><code>if</code> <code>(node.Left !=</code><code>null</code> <code>&amp;&amp; node.Right !=</code><code>null</code><code>)</code>

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

<code>                  </code><code>TreeNode tmpNode = FindMin(node.Right);</code><code>//查找目前節點有子樹的最小節點</code>

<code>                  </code><code>node.Element = tmpNode.Element;</code><code>//将右子樹的最小節點取代目前要删除的節點</code>

<code>                  </code><code>node.Right = Delete(node.Element, node.Right);</code><code>//這裡是亮點，删除目前節點右子樹的最小節點</code>

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

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

<code>                  </code><code>if</code> <code>(node.Left ==</code><code>null</code><code>)</code>

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

<code>                      </code><code>node = node.Right;</code>

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

<code>                  </code><code>else</code> <code>if</code> <code>(node.Right ==</code><code>null</code><code>)</code>

<code>                      </code><code>node = node.Left;</code>

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

<code>                      </code><code>node =</code><code>null</code><code>;</code>

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

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

 這裡的重點是怎麼處理，被删除的那個節點有左右兩棵子樹，其他的都很好處理，處理方式是：

1：找到要删除節點的右子樹的最小節點，用FindMin這個方法就可以搞定；

2：将右子樹的最小節點取代目前删除的節點，因為右子樹的最小節點比目前節點的左子樹中的所有節點都大，比右子樹的節點都小，它就是符合條件的那個節點來代替目前要删除的節點

3：由于右子樹的最小節點取代了目前節點，是以要在右子樹中删除這個最小節點，現在又轉換成同一個問題，在一棵二叉查找樹中删除一個節點，于是就遞歸咯。

我當時就是沒有想到這裡還可以用遞歸，寫了一堆自己現在都不是很懂的代碼。

第一個問題讓我震驚是以前沒有了解遞歸的先進後出的思想，第二個是因為我沒有掌握問題轉換的思想，看似兩個不同的問題，其實是同一個問題，當然解法也是一樣的，既然把兩個解法一樣的問題放在一起，用遞歸就再好不過了，他同時把你們搞定

本文轉自啊漢部落格園部落格，原文連結：http://www.cnblogs.com/hlxs/archive/2011/12/22/2297484.html