最近复习一下数据结构，又加深了一些问题的理解。
递归大家都很熟悉了，但是什么时候能用递归？什么时候不能用递归呢？大家在学习汉诺塔、二叉树和树的时候经常用到递归，但是为什么这些时候能用递归，而其他时候不能用到递归呢？ 递归的使用就是知道递归的次数是可知的并且是恒定的（这里的次数并不是递归的深度，举个例子吧，遍历二叉树的根节点后，你明确的知道要遍历左子树和右子树，那么这里的次数就是2,2是已知的并且不会随节点的变化而变化），在二叉树中，仅仅有左子树和右子树两种情况，所以能用递归。
可能有人又会问了，我也见过数的遍历中用到递归的啊，这个每个节点的孩子数目是不一定的啊，这又怎么解释呢？我可以说，这种情况的递归肯定是在树以二叉链表的形式存储时使用的。
好吧，这时，我列出二叉树遍历的通用递归模式：
void XXTraverse(BiTree T) //遍历二叉树的递归算法
{
if (T!=NULL){
①
XXTraverse(T->lchild);
②
XXTraverse(T->rchild);
③
}
}
①、 ②、 ③是根据前序、中序还是后序来确定的。
在一般的题目中，并不是这么简单，但是思路就是这样的，可能在某些地方加一些稍微的修改。我在这里举几个例子：
1.求二叉树根到叶子节点的路径。
当然了，这通过一次二叉树的遍历就可以知道了，下面我就通过上面的通用递归模式来解决。我要用一个栈来存路径，当一个节点的左子树和右子树都为空的时候输出路径,否则才进行遍历左子树和右子树。最后注意的是，当经过一个节点的路径都已经遍历过时，对其进行出栈，这一点很重要。
void AllPath(Bitree T, Stack &S)//输出二叉树上从根到所有叶子结点的路径
{
if(T！=null)
{
Push(S,T->data);
if(!T->Left&&!T->Right)//如果左指针和右指针同时为空，才说明该节点为叶子节点
PrintStack(S);//将栈中元素从栈底到栈顶输出
else
{
AllPath(T->Left,S);
AllPath(T->Right,S);
}
Pop(S);
}
}
2.求二叉树的深度
int treedepth(BiTree T)
{ if(T==null)
return 0;
else
{ int leftdepth= treedepth(T->leftchild);
int rightdepth=treedepth(T->rightchild);
}
return max(leftdepth,rightdepth)+1;
}
3.统计二叉树叶子数目
int countleaf(Bitree T)
{ int count=0;
if(T!=null) {
if((!T->lchild)&&(!T->rchild)) count++;
countleaf(T->leftchild);
countleaf(T->rightchild);
}
}