用c语言实现以二叉链表作为二叉树的存储结构,编写用层次顺序遍历二叉树的方法,统计树中度为1 的结点个数。
时间: 2024-05-01 08:19:19 浏览: 99
以下是用C语言实现二叉树的代码:
```c
// 定义二叉树结点结构体
typedef struct BiTNode{
char data;
struct BiTNode *lchild;
struct BiTNode *rchild;
}BiTNode, *BiTree;
// 层次遍历二叉树
void levelOrder(BiTree tree){
if(tree == NULL) return;
Queue queue;
initQueue(&queue);
enqueue(&queue, tree);
while(!isEmpty(&queue)){
BiTNode *node = dequeue(&queue);
printf("%c ", node->data);
if(node->lchild != NULL){
enqueue(&queue, node->lchild);
}
if(node->rchild != NULL){
enqueue(&queue, node->rchild);
}
}
}
// 统计度为1的结点个数
int countDegree1(BiTree tree){
if(tree == NULL) return 0;
int count = 0;
if(tree->lchild == NULL && tree->rchild != NULL
|| tree->lchild != NULL && tree->rchild == NULL){
count = 1;
}
return count + countDegree1(tree->lchild) + countDegree1(tree->rchild);
}
```
其中,`levelOrder`函数实现了二叉树的层次遍历,采用了队列结构;`countDegree1`函数实现了统计度为1的结点个数,采用了递归方式。
阅读全文