c语言,设计一个算法,求二叉树第k层的结点个数。完整代码 非递归
时间: 2023-06-10 22:02:33 浏览: 86
思路:利用层序遍历的方式,记录每一层的节点数,直到第k层停止遍历,返回第k层节点数即可。
完整代码如下:
```
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100
typedef struct TreeNode{
int data;
struct TreeNode *left;
struct TreeNode *right;
}TreeNode, *Tree;
typedef struct Queue{
Tree data[MAXSIZE];
int front, rear;
}Queue;
void InitQueue(Queue *q){
q->front = q->rear = 0;
}
int IsEmpty(Queue q){
return q.front == q.rear;
}
int EnQueue(Queue *q, Tree t){
if((q->rear + 1) % MAXSIZE == q->front) return 0;
q->data[q->rear] = t;
q->rear = (q->rear + 1) % MAXSIZE;
return 1;
}
int DeQueue(Queue *q, Tree *t){
if(q->front == q->rear) return 0;
*t = q->data[q->front];
q->front = (q->front + 1) % MAXSIZE;
return 1;
}
int GetNumK(Tree t, int k){
if(!t) return 0;
Queue q;
InitQueue(&q);
EnQueue(&q, t);
int level = 1;
int count = 0;
int num_k = 0;
while(!IsEmpty(q)){
int len = q.rear - q.front;
while(len--){
Tree node;
DeQueue(&q, &node);
count++;
if(level == k)
num_k++;
if(node->left)
EnQueue(&q, node->left);
if(node->right)
EnQueue(&q, node->right);
}
level++;
if(level > k)
break;
}
return num_k;
}
int main(){
Tree t = (Tree)malloc(sizeof(TreeNode));
t->data = 1;
t->left = (Tree)malloc(sizeof(TreeNode));
t->left->data = 2;
t->right = (Tree)malloc(sizeof(TreeNode));
t->right->data = 3;
t->left->left = (Tree)malloc(sizeof(TreeNode));
t->left->left->data = 4;
t->left->right = (Tree)malloc(sizeof(TreeNode));
t->left->right->data = 5;
t->right->left = (Tree)malloc(sizeof(TreeNode));
t->right->left->data = 6;
t->right->right = (Tree)malloc(sizeof(TreeNode));
t->right->right->data = 7;
printf("%d\n", GetNumK(t, 3)); // 输出3,第3层有3个节点
return 0;
}
```