内容:
??? 若用二叉链表作为二叉树的存储表示，设计算法求二叉树中度为1的结点的个数。
步骤：
1.算法分析：
? ? ? ?所谓的二叉树的度，就是指结点所拥有的子树的个数，所以二叉树中度的取值可为0，1，2。当然，题目中度为1的点就是指该结点只有一个左孩子或者只有一个右孩子。而二叉链表的存储就是设计一个结点，该结点至少包括数据域、左孩子域和右孩子域。该结构可用如下图表示：
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?图1 二叉链表的存储结构
? ??
? ? ? ?其中，data域存放某结点的数据信息；lchild和rchild分别存放指向左孩子和右孩子的指针，当左孩子或者右孩子不存在时，相应指针域值为空（用符号Λ或NULL表示），当然还有三叉链表存储等，这里不做赘述。
? ? ? 那么，根据上述二叉链表的存储特性以及度的定义，我们怎么设计算法求其度为1的结点数呢？其实也没那么复杂，说到底其实就是找只有一个子树的结点，所以至少需要遍历整个二叉树，才能找出其数目，另外还必须设置一个计数器来记下度为1的结点，不符合要求的则不计入。所以至少要遍历且设计一个计数器。关于遍历，我们最熟悉不就是在二叉树的前中后序遍历里面学的递归算法了吗？
? ? ? ?所以现在的问题就是如何设计递归，不过在此之前，我们需要考虑一下结点的度不相同时我们应该怎么办。下面的这个树包含了度的全部情况：
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?图2 度的示意图
? ? ? ?所以，在递归前我们首先需要判断当前结点的左右孩子的情况，若其有左右孩子，则直接先以左孩子的结点为根节点，继续判断，进入第一种情况的递归。知道某一结点的孩子为NULL或者有一个孩子，则向上返回。而接下来的两种情况无非就是只有左孩子或者只有右孩子。当其只有左孩子时，先将度为1的情况+1，再将该结点的作为根节点，调用函数Num(BiTree ptr)，继续向下判断执行。同理，当只有右孩子时亦是如此。直到所有结点均被遍历时，函数调用结束，输出此时的值，即为二叉链表的度为1的值。
? ? ? ?至此，算法分析的过程结束，我们可以设计一个Num(BiTree ptr)函数，只要判断出某节点存在左孩子或者右孩子时，就可以调用这个函数。这个判断的过程使用if…else完成，需要注意的是，当某一个结点只有一个孩子时，调用函数前先将结构+1，其原因上文已解释。
? ? ? ? 综上，我们可以利用二叉树结构上的递归特性，用递归的方法可总结为下面三种情况：
? ? ? ? (1)若某结点有左子树和右子树，则以此结点为根的二叉树中度为1的结点个数=左子树的度为1的结点个数+右子树中度为1的结点数。
? ? ? ? (2)若该结点只有一棵子树，则以此结点为根的二叉树中度为1的结点个数=1+其唯一子树中度为1的结点个数。
? ? ? ? ?(3)若该结点没有子树，则此结点为根的二叉树中度为1的结点个数=0.
? ? ? ?可以看到，递归算法在这里的使用很巧妙，只用了少量的语句就完成了大量复杂而且冗余的工作，但是缺点也很明显，就是不容易理解算法，因为内部经常会设计到调用自身，对于才看到代码的人来说，理解还需要一定的过程。
2.算法运行流程图：
?3.总结
? ? ?通过这道题，让我更加熟悉了对于递归算法的使用和理解，其实所谓递归就是再不断的调用自己，只不过在这个过程中，我们需要注意并且清楚以下几点：??
? ? ? ?第一：明确你这个函数想要干什么。先不管函数里面的代码什么，而是要先明白，你这个函数的功能是什么，要完成什么样的一件事。
? ? ? ?第二：寻找递归结束条件。我们需要找出当参数为啥时，递归结束，之后直接把结果返回，请注意，这个时候我们必须能根据这个参数的值，能够直接知道函数的结果是什么。
? ? ? ?第三：找出函数的等价关系式。我们要不断缩小参数的范围，缩小之后，我们可以通过一些辅助的变量或者操作，使原函数的结果不变。
? ? ? ?只有知道了以上几点，才基本上能理解递归算法的应用。感觉递归算法还是非常巧妙的，无论是之前的汉诺塔问题，还是三种遍历方式，都只是用短短的几行语句就完成了大量复杂的工作。
4.算法源代码：
//算法如下：
typedef struct Node
{ //二叉树的二叉链表结点的结构
DataType data;
struct Node *LChild;
struct Node *Rchild;
} BiTNode,*BiTree;
int Num(BiTree ptr)
{ BiTNode *temp;
if(ptr->LChild!=NULL&&ptr->Rchild!=NULL) //该二叉树均有左右孩子
return Num(ptr->LChild)+Num(ptr->Rchild);
else if(ptr->LChild==NULL&&ptr->Rchild!=NULL) //该二叉树只有右孩子
return 1+Num(ptr->Rchild);
else if(ptr->LChild!=NULL&&ptr->Rchild==NULL) //该二叉树只有左孩子
return 1+Num(ptr->LChild);
return 0;
}