假设二叉树采用二叉链表存储结构，设计一个算法求其指定的某一层k(k＞1)的叶子结点个数，要求： 根据设计思想，采用C或C++语言描述算法，关键之处给出注释。 算法的设计如下： 解法一： #define MaxSize 100 //设置队列的最大容量 int LeafKLevel(BTNode *root, int k){ BTNode* q[MaxSize]; //声明队列，end1为头指针，end2为尾指针 int end1, end2, sum=0; //队列最多容纳MaxSize一1个元素 end1=end2=0; //头指针指向队头元素，尾指针指向队尾的后一个元素 int deep=0; //初始化深度 BTNode *lastNode; //lastNode用来记录当前层的最后一个结点 BTNode *newlastNode; //newlastNode用来记录下一层的最后一个结点 lastNode=root; //lastNode初始化为根结点 newlastNode=NULL; //newlastNode初始化为空 q[end2++]=root; //根结点入队 while(end1 !=end2){ //层次遍历，若队列不空则循环 BTNode *t=q[end1++]; //拿出队列中的头一个元素 if(k=deep){ //找到特定层，统计叶子结点个数 while(end1 !=end2){ t=q[end1++]; if(t-＞lchild==NULL&&t-＞rchild==NULL) ++sum; } break; } else{ //没到特定层，层次遍历 if(t-＞lchild !=NULL){ //若非叶子结点把左结点入队 q[end2++]=t-＞lchild; newlastNode=t-＞lchild; } //并设下一层的最后一个结点为该结点的左结点 if(t-＞rchild !=NULL){ //处理叶结点 q[end2++]=t-＞rchiid; newlastNode=t-＞rchild; } if(t==lastNode){ //若该结点为本层最后一个结点，更新lastNode lastNode=newlastNode; deep+=1; //层数加1 } } } return sum; //返回叶子结点个数 } 解法二： int n; int LeafKLevel(BiTree root, int k){ n=0; Preorder(root, 0, k); return 0; } int PreOrder(BiTree root, int deep, int k){ if(deep＜k){ if(root-＞lchild !=NULL) //若左子树不空，对左子树递归遍历 PreOrder(root-＞lchild, deep+1); if(root-＞rchild !=NULL) //若右子树不空，对右子树递归遍历 PreOrder(root-＞rchild, deep+1); } else if(deep==k && root-＞lchild==NULL && root-＞rchild==NULL) ++n; }