编写简单的C语言程序,实现二叉树的输入和遍历功能,包括先序、中序、后序以及层次遍历,并计算二叉树的深度和节点数目。
时间: 2024-12-23 22:12:22 浏览: 13
9_二叉树_
编写一个简单的C语言程序来实现二叉树的基本操作需要一些数据结构,如结构体表示节点,函数来插入节点、遍历和计算深度和节点数。下面是一个简化的示例:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树节点
typedef struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
// 创建新节点
TreeNode* createNode(int data) {
TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
if (!newNode)
return NULL;
newNode->val = data;
newNode->left = newNode->right = NULL;
return newNode;
}
// 先序遍历(根-左-右)
void preOrderTraversal(TreeNode* root) {
if (root != NULL) {
printf("%d ", root->val);
preOrderTraversal(root->left);
preOrderTraversal(root->right);
}
}
// 中序遍历(左-根-右)
void inOrderTraversal(TreeNode* root) {
if (root != NULL) {
inOrderTraversal(root->left);
printf("%d ", root->val);
inOrderTraversal(root->right);
}
}
// 后序遍历(左-右-根)
void postOrderTraversal(TreeNode* root) {
if (root != NULL) {
postOrderTraversal(root->left);
postOrderTraversal(root->right);
printf("%d ", root->val);
}
}
// 层次遍历(广度优先搜索)
void levelOrderTraversal(TreeNode* root) {
if (root == NULL)
return;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
TreeNode* node = q.front();
q.pop();
printf("%d ", node->val);
if (node->left)
q.push(node->left);
if (node->right)
q.push(node->right);
}
}
// 计算二叉树的深度
int calculateDepth(TreeNode* root) {
if (root == NULL)
return 0;
return 1 + MAX(calculateDepth(root->left), calculateDepth(root->right));
}
// 计算二叉树的节点数目
int countNodes(TreeNode* root) {
if (root == NULL)
return 0;
return 1 + countNodes(root->left) + countNodes(root->right);
}
int main() {
// 省略实际读取用户输入并构建二叉树的代码...
// 进行遍历和计算
printf("Preorder Traversal: ");
preOrderTraversal(root);
printf("\nInorder Traversal: ");
inOrderTraversal(root);
printf("\nPostorder Traversal: ");
postOrderTraversal(root);
printf("\nLevel Order Traversal: ");
levelOrderTraversal(root);
printf("\nDepth: %d\n", calculateDepth(root));
printf("Number of Nodes: %d\n", countNodes(root));
return 0;
}
```
这个程序首先定义了二叉树节点的结构,然后实现了创建节点、四种遍历方法以及计算深度和节点数的功能。`main`函数中需要添加构建二叉树的具体代码,这里未给出。
阅读全文