内容:
若用二叉链表作为二叉树的存储表示，设计算法求二叉树中度为1的结点个数。
步骤：
1.算法分析
本题需要采用二叉链表作为二叉树的存储结构，来求解二叉树中度为1的结点个数。大体上分为两部分，第一，建立二叉树，此处采用先序的方式建立二叉树，其次需要用二叉链表来存储一棵二叉树，任意的二叉树中，每个结点最多有两个孩子，一个双亲结点，因此在一个结点中只需要包括数据域、左孩子和右孩子即可，当左孩子或右孩子不存在时，用符号#表示，声明二叉树的二叉链表结点的结构如下：
typedef struct BiTNode{
TElemType data;
struct BiTNode *lchild,*rchild;//左右孩子指针
}BiTNode,*BiTree;
其次需要求出二叉树中度为1的结点个数，二叉树在结构上的特性为递归性，因此可以采用递归的方法实现。若某结点有左子树和右子树，则以此结点为根结点的根的二叉树中度为1的结点个数=左子树的度为1的结点个数+右子树度为1的结点个数，若该结点只有一棵子树，则以此结点为根的二叉树中度为1的结点个数=1+其子树中度为1的结点个数，若该结点没有子树，则此结点为根的二叉树中度为1的结点个数=0。
2.概要设计
使用C语言，其中设置了以下函数
程序运行流程图如下：
3.测试
测试案例一：
ABC##DE##F##G##
其表示的二叉树形状为：
该二叉树中度为1的结点个数为0；
测试用例2：
ABD#G###CE##F##
其表示的二叉树形状为：
该二叉树中度为1的结点数目为2。
程序运行结果为：
测试案例一：
测试案例二：
程序运行无误。
源码如下：
#include<stdio.h>
#include<stdlib.h>
#define MAX 20
typedef char TElemType;
typedef int Status;
//定义二叉树的二叉链表结点的结构
typedef struct BiTNode{
TElemType data;
struct BiTNode *lchild,*rchild;//左右孩子指针
}BiTNode,*BiTree;
//先序建立二叉树
void CreateBiTree(BiTree *T)
{
char ch;
ch=getchar();
if(ch=='#')(*T)=NULL;//#代表空指针
else
{
(*T)=(BiTree)malloc(sizeof(BiTNode));//申请结点
(*T)->data=ch;//生成根结点
CreateBiTree(&(*T)->lchild);//构造左子树
CreateBiTree(&(*T)->rchild);//构造右子树
}
}
//求二叉树中度为1的结点个数
int Degree1(BiTree T){
if(T==NULL)
return 0;
if((T->lchild==NULL&&T->rchild!=NULL)||(T->lchild!=NULL&&T->rchild==NULL))
return Degree1(T->lchild)+Degree1(T->rchild)+1;
else
return Degree1(T->lchild)+Degree1(T->rchild);
}
int main()
{
BiTree T=NULL;
printf("\n 创建一棵二叉树：\n");
CreateBiTree(&T);//建立一棵二叉树T
printf("\n 二叉树中度为1的结点个数为：%d\n",Degree1(T));
}