数据结构-求二叉树第K层结点个数

描述

如果按照二叉树的顺序存储结构，逐个输入二叉树的结点值，（即按从上到下、从左至右的顺序，逐个输入结点值，对于空结点使用0表示），则一棵二叉树可以被一个序列唯一表示。

输入

第一行为二叉树中非空结点的个数K及要查找的层数L，1<=K<=2^10，L>=1;

第二行为按照顺序结构逐个输入的二叉查找树的n个结点值（包含空结点），n个结点值之间用空格隔开，1<=n<=2^10

输出

第一行为二叉树第L层的结点个数

第二行为空行

由于以前没做过这种类型题目（当然，更重要的原因是自己水平太菜了，队列和二叉树的思维没有很好地掌握），因此这一题光真正读懂题意就花了我不少功夫，编程过程更是费劲周折，为了找出bug花了大量时间，不过好在最后总算是完成了。

这一题我的思路如下：

创建二叉树时，将第一个结点加入队列，然后只要结点数不到n个并且队列不空（事实上此题正确输入队列必定一直不为空，为防止非法输入故判断队列），取出队首元素，并扩展队列。

计算个数时，设立全局变量num，利用递归逐层向下，累加num即可。

完整代码如下：

#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 200//最多结点个数

typedef struct btnode
{
    int data;
    struct btnode *lchild;
    struct btnode *rchild;
} btnode, *bitree;

typedef struct Queue
{
    bitree *data[MAXSIZE];
    int front;
    int rear;
} Queue;

bitree root;
Queue q;//辅助队列
int n;//非空结点个数
int k;//求第k层
int num;//第k层结点个数

void input();
void createbitree(bitree *t);
void nodenum(bitree t, int i);
void output();
void InitQueue();
void EnterQueue(bitree *t);
void GetQueue(bitree **t);
int IsEmpty();

int main()
{
    input();
    nodenum(root, 1);
    output();
    return 0;
}

void input()
{
    scanf("%d%d", &n, &k);
    createbitree(&root);
}

void createbitree(bitree *t)
{
    bitree *p;
    int data, i;
    i = 0;
    InitQueue();
    ///1.将第一项放入队列
    *t = (bitree)malloc(sizeof(btnode));
    EnterQueue(t);
    ///2.若队列不空，则取出队首元素，拓展队列
    while(i < n && !IsEmpty())
    {
        GetQueue(&p);
        scanf("%d", &data);
        if(data != 0)
        {
            i++;
        }
        *p = (bitree)malloc(sizeof(btnode));
        (*p)->data = data;
        (*p)->lchild = (*p)->rchild = NULL;
        EnterQueue(&((*p)->lchild));
        EnterQueue(&((*p)->rchild));
    }
}

void nodenum(bitree t, int i)
{
    if(t != NULL && t->data != 0)
    {
        if(i < k)
        {
            if(t->lchild != NULL)
            {
                nodenum(t->lchild, i + 1);
            }
            if(t->rchild != NULL)
            {
                nodenum(t->rchild, i + 1);
            }
        }
        else
        {
            num++;
        }
    }
}

void output()
{
    printf("%d\n", num);
}

///以下是队列相关函数
void InitQueue()
{
    q.front = q.rear = 0;
}

void EnterQueue(bitree *t)
{
    q.rear = (q.rear + 1) % MAXSIZE;
    q.data[q.rear] = t;
}

void GetQueue(bitree **t)
{
    q.front = (q.front + 1) % MAXSIZE;
    *t = q.data[q.front];
}

int IsEmpty()
{
    if(q.front == q.rear)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}

           

以上就是我的实现，这段时间的事情确实蛮多的，电路基础实验和python大作业还一筹莫展，大后天就要数据结构实验期末考试了，这一题对我而言算一个很好的练习，希望好运。