C语言按照先序遍历的方式创建一个二叉链表; 计算并输出二叉树的结点个数、叶子结点个数以及二叉树的深度。
时间: 2024-12-10 21:27:46 浏览: 8
在C语言中,我们首先需要定义一个二叉链表节点结构,然后按照先序遍历(根节点 -> 左子树 -> 右子树)创建链表。这里是一个简单的示例:
```c
// 定义二叉链表节点结构
typedef struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
// 先序遍历函数 (递归)
void preorderTraversal(TreeNode* root) {
if (root != NULL) {
printf("%d ", root->val); // 输出当前节点值
preorderTraversal(root->left); // 遍历左子树
preorderTraversal(root->right); // 遍历右子树
}
}
// 创建一个二叉链表的例子
TreeNode* createBinaryTree(int arr[], int n) {
if (n == 0) return NULL;
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = arr[0];
root->left = createBinaryTree(arr+1, n-1);
root->right = createBinaryTree(arr+n-1, n-1); // 假设数组下标从0开始,最后一个元素的索引是n-1
return root;
}
```
要计算二叉树的结点个数、叶子结点个数以及深度,我们可以添加一些辅助函数:
```c
int countNodes(TreeNode* root) {
if (root == NULL) return 0;
return 1 + countNodes(root->left) + countNodes(root->right);
}
int countLeaves(TreeNode* root) {
if (root == NULL || root->left == NULL && root->right == NULL) return 1; // 如果左右子节点都为空,则是叶子节点
else return countLeaves(root->left) + countLeaves(root->right);
}
int calculateDepth(TreeNode* root) {
if (root == NULL) return 0;
return 1 + max(calculateDepth(root->left), calculateDepth(root->right));
}
int main() {
// 创建二叉树并初始化
int arr[] = {1, 2, 3, 4, 5};
int n = sizeof(arr)/sizeof(arr[0]);
TreeNode* root = createBinaryTree(arr, n);
printf("Node count: %d\n", countNodes(root));
printf("Leaf count: %d\n", countLeaves(root));
printf("Tree depth: %d\n", calculateDepth(root));
return 0;
}
```
运行`main()`函数会输出对应的统计信息。
阅读全文