遞歸再一次讓哥震驚了
遞歸再一次讓哥震驚了
先說那兩個讓哥震驚的遞歸問題：
1：用遞歸實現(xiàn)單鏈表的倒序輸出
2：從二叉查找樹中刪除節(jié)點，并保證還是二叉查找樹
同學們可以開始思考這兩個問題了，當然你可能N年前就遇到過這兩個問題，那么不妨看看，看你是否真的理解了遞歸。實現(xiàn)這兩個問題的代碼當然很簡單，就在下面。
百度百科中遞歸的名片：遞歸做為一種算法在程序設(shè)計語言中廣泛應用.是指函數(shù)/過程/子程序在運行過程中直接或間接調(diào)用自身而產(chǎn)生的重入現(xiàn)象.遞歸是計算機科學的一個重要概念,遞歸的方法是程序設(shè)計中有效的方法,采用遞歸編寫程序能使程序變得簡潔和清晰。
剛開始學習的遞歸的時候，覺得他好強大，實現(xiàn)某些功能不用遞歸可能要幾十行代碼，用遞歸可能幾行就搞定了，而且代碼清晰簡潔。一直以為遞歸也就是自己調(diào)用自己，有一個出口條件，讓他停止遞歸，退出函數(shù)，其實的特點并非就這些。
遞歸還有一個非常重要的特點：先進后出，跟棧類似，先遞進去的后遞出來。由于遞歸一直在自己調(diào)用自己，有時候我們很難清楚的看出，他的返回值到底是哪個，只要你理解了先進后出這個特點，你就會明白，第一次調(diào)用時，作為返回值的那個變量的值就是遞歸函數(shù)的返回值。先進后出嗎，他是第一個進來，也就是最后出去的那個，當然就是遞歸的返回值啦。
第一個讓哥震驚的問題：用遞歸實現(xiàn)單鏈表的倒序輸出。
我前段時間寫過一篇博客《四種方式實現(xiàn)--從尾到頭輸出鏈表》，其中一種方法就是用遞歸實現(xiàn)的，當時看見那位高人用遞歸實現(xiàn)了這個功能，哥被震住了，他怎么可以這么聰明，他的博客真的是學算法的好地方：http://zhedahht.blog.163.com/blog/#m=0。代碼如下，這是我那篇博客的源碼：
//用遞歸實現(xiàn)
//很誠實的說盜用了別人的思想，真的太妙了，完全能看出你是否真的體會了遞歸的原理
//正如那位哥們所說，遞歸就是一個進棧出棧的過程，鏈表前面的元素先進棧，在棧底，后面的元素后進棧，在棧頂，先出棧，哈哈。。。
void recursion(node* head)
{
if(NULL==head)
{
return;
}
if(head->next!=NULL)
{
recursion(head->next);
}
//如果把這句放在第二個if前面，那就是從頭到尾輸出鏈表，曾經(jīng)的你或許是用while或者用for循環(huán)輸出鏈表，現(xiàn)在你又多了一種方式
cout<<head->data<<"\t";
}
這里充分運用了遞歸的先進后出的特點。
最近在博客園中看的一些博客，發(fā)現(xiàn)有幾篇文章跟樹聯(lián)系得比較緊，前天晚上，我于是把數(shù)據(jù)結(jié)構(gòu)與算法中樹的那一章溫習了一下，哥被二叉查找樹刪除節(jié)點的算法給震住了，因為我以前也寫過一篇關(guān)于二插查找樹的博客《算法學習--二叉查找樹》，在這篇博客中，刪除節(jié)點的那個算法寫得很長，以至于叫我自己現(xiàn)在去看都不是很理解，今天會讓大家看到看到簡潔清晰的代碼，遞歸寫的嗎，哈哈哈！
先來C++版的吧，好久沒寫了，都生疏了：
View Code
#include "string.h"
#include <iostream>
using namespace std;
typedef struct TreeNode1
{
public:
int element;
TreeNode1 *left;
TreeNode1 *right;
TreeNode1(int element):element(element),left(NULL),right(NULL){}
} TreeNode;
class AdtTree
{
public :
TreeNode *root;//根節(jié)點
AdtTree()
{
root=NULL;
}
//查找指定節(jié)點下的最小節(jié)點
TreeNode* FindMin(TreeNode *t)
{
if(t==NULL)
{
return NULL;
}else if(t->left==NULL)
{
return t;
}else
{
return FindMin(t->left);
}
}
//查找最小節(jié)點
TreeNode* FindMin()
{
return FindMin(root);
}
//查找指定節(jié)點下的節(jié)點
TreeNode* Find(int element,TreeNode *t)
{
if(t==NULL)
{
return NULL;
}
if(element<t->element)
{
return Find(element,t->left);
}else if(element>t->element)
{
return Find(element,t->right);
}else
{
return t;
}
}
//查找節(jié)點
TreeNode* Find(int element)
{
return Find(element,root);
}
//在指定節(jié)點下天驕節(jié)點
TreeNode* Add(int element,TreeNode *t)
{
if(t==NULL)
{
return NULL;
}
if(element<t->element)
{
if(t->left==NULL)
{
return t->left=new TreeNode(element);
}
return Add(element,t->left);
}else if(element>t->element)
{
if(t->right==NULL)
{
return t->right=new TreeNode(element);
}
return Add(element,t->right);
}
return t;
}
//天驕節(jié)點
TreeNode* Add(int element)
{
if(root==NULL)
{
return root=new TreeNode(element);
}else{
return Add(element,root);
}
}
//刪除指定節(jié)點下節(jié)點
TreeNode* Delete(int element,TreeNode *t)
{
if(t==NULL)
{
return NULL;
}else if(element<t->element)
{
t->left= Delete(element,t->left);
}else if(element>t->element)
{
t->right= Delete(element,t->right);
}else
{
if(t->left!=NULL && t->right!=NULL)
{
TreeNode* tmpNode=FindMin(t->right);
t->element=tmpNode->element;
t->right=Delete(t->element,t->right);
}else
{
TreeNode* tmpNode=t;
if(t->left==NULL)
{
t=t->right;
}else if(t->right==NULL)
{
t=t->left;
}
delete tmpNode;
}
}
return t;
}
//刪除節(jié)點
TreeNode* Delete(int element)
{
return Delete(element,root);
}
};
在來C#版：
namespace Utils
{
public class TreeNode
{
public int Element
{
get;
set;
}
public TreeNode Left
{
get;
set;
}
public TreeNode Right
{
set;
get;
}
public TreeNode(int element)
{
this.Element = element;
}
}
/// <summary>
/// 二插查找樹
/// </summary>
public class AdtTree
{
public AdtTree() { }
public AdtTree(TreeNode node)
{
this.root = node;
}
//根節(jié)點
private TreeNode root;
//添加節(jié)點（沒有檢查根節(jié)點是否為空，所以設(shè)為private）
private void AddNode(int element, TreeNode node)
{
if (node == null)
{
return;
}
if (element < node.Element)
{
if (node.Left == null)
{
node.Left = new TreeNode(element);
}
else
{
AddNode(element, node.Left);
}
}
else if (element > node.Element)
{
if (node.Right == null)
{
node.Right = new TreeNode(element);
}
else
{
AddNode(element, node.Right);
}
}
}
//添加節(jié)點
public void Add(int element, TreeNode node)
{
if (this.root == null)
{
this.root = new TreeNode(element);
}
else
{
AddNode(element, node);
}
}
public void Add(int element)
{
Add(element, this.root);
}
//查找指定節(jié)點下的最小節(jié)點
public TreeNode FindMin(TreeNode node)
{
if (node == null)
{
return null;
}
if (node.Left == null)
{
return node;
}
else
{
return FindMin(node.Left);
}
}
//查找最小節(jié)點
public TreeNode FindMin()
{
return FindMin(this.root);
}
//刪除指定節(jié)點下的節(jié)點
public TreeNode Delete(int element, TreeNode node)
{
if (node == null)
{
return null;
}
if (element < node.Element)
{
node.Left = Delete(element, node.Left);
}
else if (element > node.Element)
{
node.Right = Delete(element, node.Right);
}
else
{
if (node.Left != null && node.Right != null)
{
TreeNode tmpNode = FindMin(node.Right);
node.Element = tmpNode.Element;
node.Right = Delete(node.Element, node.Right);//這里是亮點 }
else
{
if (node.Left == null)
{
node = node.Right;
}
else if (node.Right == null)
{
node = node.Left;
}
else {
node = null;
}
}
}
return node;
}
//刪除節(jié)點
public TreeNode Delete(int element)
{
//如果只有一個節(jié)點，即根節(jié)點，將根節(jié)點制空
if (root != null && root.Element == element && root.Left == null && root.Right == null)
{
root = null;
return new TreeNode(element);
}
return Delete(element,this.root);
}
}
}
現(xiàn)在我們重點來看看，刪除節(jié)點的算法：
//刪除指定節(jié)點下的節(jié)點
public TreeNode Delete(int element, TreeNode node)
{
if (node == null)
{
return null;
}
if (element < node.Element)
{
node.Left = Delete(element, node.Left);
}
else if (element > node.Element)
{
node.Right = Delete(element, node.Right);
}
else
{
if (node.Left != null && node.Right != null)
{
TreeNode tmpNode = FindMin(node.Right);//查找當前節(jié)點有子樹的最小節(jié)點
node.Element = tmpNode.Element;//將右子樹的最小節(jié)點取代當前要刪除的節(jié)點
node.Right = Delete(node.Element, node.Right);//這里是亮點，刪除當前節(jié)點右子樹的最小節(jié)點
}
else
{
if (node.Left == null)
{
node = node.Right;
}
else if (node.Right == null)
{
node = node.Left;
}
else {
node = null;
}
}
}
return node;
}
這里的重點是怎么處理，被刪除的那個節(jié)點有左右兩棵子樹，其他的都很好處理，處理方式是：
1：找到要刪除節(jié)點的右子樹的最小節(jié)點，用FindMin這個方法就可以搞定；
2：將右子樹的最小節(jié)點取代當前刪除的節(jié)點，因為右子樹的最小節(jié)點比當前節(jié)點的左子樹中的所有節(jié)點都大，比右子樹的節(jié)點都小，它就是符合條件的那個節(jié)點來代替當前要刪除的節(jié)點
3：由于右子樹的最小節(jié)點取代了當前節(jié)點，所以要在右子樹中刪除這個最小節(jié)點，現(xiàn)在又轉(zhuǎn)換成同一個問題，在一棵二叉查找樹中刪除一個節(jié)點，于是就遞歸咯。
我當時就是沒有想到這里還可以用遞歸，寫了一堆自己現(xiàn)在都不是很懂的代碼。
第一個問題讓我震驚是以前沒有理解遞歸的先進后出的思想，第二個是因為我沒有掌握問題轉(zhuǎn)換的思想，看似兩個不同的問題，其實是同一個問題，當然解法也是一樣的，既然把兩個解法一樣的問題放在一起，用遞歸就再好不過了，他同時把你們搞定
作者：陳太漢
浙公網(wǎng)安備 33010602011771號