用C语言实现以二叉链表作为二叉树的存储结构,编写用层次顺序遍历二叉树的方法,统计树中度为1 的结点个数
时间: 2024-04-30 22:19:03 浏览: 108
以下是用C语言实现二叉链表存储结构的代码:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
// 创建新结点
TreeNode* createNode(int val) {
TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
node->val = val;
node->left = NULL;
node->right = NULL;
return node;
}
// 层次遍历二叉树
void levelOrderTraversal(TreeNode* root) {
if (root == NULL) return;
TreeNode* queue[1000];
int front = 0, rear = 0;
queue[rear++] = root;
while (front < rear) {
TreeNode* node = queue[front++];
printf("%d ", node->val);
if (node->left != NULL) queue[rear++] = node->left;
if (node->right != NULL) queue[rear++] = node->right;
}
}
// 统计度为1的结点个数
int countDegreeOneNodes(TreeNode* root) {
if (root == NULL) return 0;
int count = 0;
if ((root->left == NULL && root->right != NULL) || (root->left != NULL && root->right == NULL)) {
count++;
}
return count + countDegreeOneNodes(root->left) + countDegreeOneNodes(root->right);
}
int main() {
TreeNode* root = createNode(1);
root->left = createNode(2);
root->right = createNode(3);
root->left->left = createNode(4);
root->left->right = createNode(5);
root->right->left = createNode(6);
root->right->right = createNode(7);
printf("层次遍历二叉树:");
levelOrderTraversal(root);
printf("\n");
printf("度为1的结点个数:%d\n", countDegreeOneNodes(root));
return 0;
}
```
代码中的`TreeNode`结构体表示二叉树的结点,包含一个`val`字段表示结点值,以及左右子结点的指针。`createNode`方法用于创建新结点。`levelOrderTraversal`方法实现了二叉树的层次遍历,使用了一个队列来辅助。`countDegreeOneNodes`方法用于统计二叉树中度为1的结点个数,递归实现。在`main`函数中,我们创建了一个二叉树并测试了以上方法。
阅读全文