递归再一次让哥震惊了
先说那两个让哥震惊的递归问题：
1：用递归实现单链表的倒序输出
2：从二叉查找树中删除节点，并保证还是二叉查找树
?
同学们可以开始思考这两个问题了，当然你可能N年前就遇到过这两个问题，那么不妨看看，看你是否真的理解了递归。实现这两个问题的代码当然很简单，就在下面。
?
百度百科中递归的名片：递归做为一种算法在程序设计语言中广泛应用.是指函数/过程/子程序在运行过程中直接或间接调用自身而产生的重入现象.递归是计算机科学的一个重要概念,递归的方法是程序设计中有效的方法,采用递归编写程序能使程序变得简洁和清晰。
?
刚开始学习的递归的时候，觉得他好强大，实现某些功能不用递归可能要几十行代码，用递归可能几行就搞定了，而且代码清晰简洁。一直以为递归也就是自己调用自己，有一个出口条件，让他停止递归，退出函数，其实的特点并非就这些。
?
递归还有一个非常重要的特点：先进后出，跟栈类似，先递进去的后递出来。由于递归一直在自己调用自己，有时候我们很难清楚的看出，他的返回值到底是哪个，只要你理解了先进后出这个特点，你就会明白，第一次调用时，作为返回值的那个变量的值就是递归函数的返回值。先进后出吗，他是第一个进来，也就是最后出去的那个，当然就是递归的返回值啦。
?
第一个让哥震惊的问题：用递归实现单链表的倒序输出。
我前段时间写过一篇博客《四种方式实现--从尾到头输出链表》，其中一种方法就是用递归实现的，当时看见那位高人用递归实现了这个功能，哥被震住了，他怎么可以这么聪明，他的博客真的是学算法的好地方：http://zhedahht.blog.163.com/blog/#m=0。代码如下，这是我那篇博客的源码：
?
View Code
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;//根节点 AdtTree() { root=NULL; } //查找指定节点下的最小节点 TreeNode* FindMin(TreeNode *t) { if(t==NULL) { return NULL; }else if(t->left==NULL) { return t; }else { return FindMin(t->left); } } //查找最小节点 TreeNode* FindMin() { return FindMin(root); } //查找指定节点下的节点 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; } } //查找节点 TreeNode* Find(int element) { return Find(element,root); } //在指定节点下天骄节点 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; } //天骄节点 TreeNode* Add(int element) { if(root==NULL) { return root=new TreeNode(element); }else{ return Add(element,root); } } //删除指定节点下节点 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; } //删除节点 TreeNode* Delete(int element) { return Delete(element,root); } }; ?
?
在来C#版：
View Code?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; ????????} ????????//根节点 ????????private TreeNode root; ??????????//添加节点（没有检查根节点是否为空，所以设为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); ????????????????} ????????????} ????????} ??????????//添加节点 ????????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); ????????} ??????????//查找指定节点下的最小节点 ????????public TreeNode FindMin(TreeNode node) ????????{ ????????????if (node == null) ????????????{ ????????????????return null; ????????????} ????????????if (node.Left == null) ????????????{ ????????????????return node; ????????????} ????????????else????????????{ ????????????????return FindMin(node.Left); ????????????} ????????} ??????????//查找最小节点 ????????public TreeNode FindMin() ????????{ ????????????return FindMin(this.root); ????????} ??????????//删除指定节点下的节点 ????????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);//<SPAN style="COLOR: #ff6600"><STRONG>这里是亮点 </STRONG></SPAN>??????????????? } ????????????????else????????????????{ ????????????????????if (node.Left == null) ????????????????????{ ????????????????????????node = node.Right; ????????????????????} ????????????????????else if (node.Right == null) ????????????????????{ ????????????????????????node = node.Left; ????????????????????} ????????????????????else { ????????????????????????node = null; ????????????????????} ????????????????} ????????????} ??????????????return node; ????????} ??????????//删除节点 ????????public TreeNode Delete(int element) ????????{ ????????????//如果只有一个节点，即根节点，将根节点制空 ????????????if (root != null && root.Element == element && root.Left == null && root.Right == null) ????????????{ ?????????????????root = null; ?????????????????return new TreeNode(element); ????????????} ????????????return Delete(element,this.root); ????????} ????} }?
?现在我们重点来看看，删除节点的算法：
?//删除指定节点下的节点 ??????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; ??????}?这里的重点是怎么处理，被删除的那个节点有左右两棵子树，其他的都很好处理，处理方式是：
1：找到要删除节点的右子树的最小节点，用FindMin这个方法就可以搞定；
2：将右子树的最小节点取代当前删除的节点，因为右子树的最小节点比当前节点的左子树中的所有节点都大，比右子树的节点都小，它就是符合条件的那个节点来代替当前要删除的节点
3：由于右子树的最小节点取代了当前节点，所以要在右子树中删除这个最小节点，现在又转换成同一个问题，在一棵二叉查找树中删除一个节点，于是就递归咯。
我当时就是没有想到这里还可以用递归，写了一堆自己现在都不是很懂的代码。
第一个问题让我震惊是以前没有理解递归的先进后出的思想，第二个是因为我没有掌握问题转换的思想，看似两个不同的问题，其实是同一个问题，当然解法也是一样的，既然把两个解法一样的问题放在一起，用递归就再好不过了，他同时把你们搞定
1 楼 大海lb 2011-12-23 递归不仅仅是类似栈，而是用递归的时候，他的确是用的一个递归栈存储数据的，所以很多特性就自然而然的了。所以用递归操作的时候，他本身却还需要额外的空间去存储，那就是栈。