用c语言编程实现二叉树的如下基本操作: 1. 按先序序列构造一棵二叉链表表示的二叉树T; 2. 对这棵二叉树进行遍历:先序、中序、后序以及层次遍历序列,分别输出结点的遍历序列; 3. 求二叉树的深度。 4.求叶子结点的个数。 要求设计一漂亮、实用的功能菜单,每个功能用一函数表示。
时间: 2024-02-09 20:08:38 浏览: 81
好的,那我们开始吧。首先,我们需要定义二叉树的结构体,包含左右子树指针和节点值:
```c
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
```
接下来,我们可以按照先序序列构造一棵二叉树。可以使用递归的方式,每次递归先输入当前节点的值,再递归构造左右子树:
```c
TreeNode* buildTree() {
int val;
scanf("%d", &val);
if (val == -1) { // -1 表示该节点为空
return NULL;
}
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = val;
root->left = buildTree();
root->right = buildTree();
return root;
}
```
接下来,我们可以对二叉树进行遍历。每次访问一个节点,可以选择输出节点值或把节点值存储在一个数组中:
```c
void preorderTraversal(TreeNode* root, int* res, int* idx) {
if (root == NULL) {
return;
}
res[(*idx)++] = root->val;
preorderTraversal(root->left, res, idx);
preorderTraversal(root->right, res, idx);
}
void inorderTraversal(TreeNode* root, int* res, int* idx) {
if (root == NULL) {
return;
}
inorderTraversal(root->left, res, idx);
res[(*idx)++] = root->val;
inorderTraversal(root->right, res, idx);
}
void postorderTraversal(TreeNode* root, int* res, int* idx) {
if (root == NULL) {
return;
}
postorderTraversal(root->left, res, idx);
postorderTraversal(root->right, res, idx);
res[(*idx)++] = root->val;
}
void levelTraversal(TreeNode* root, int* res, int* idx) {
if (root == NULL) {
return;
}
TreeNode* queue[1000];
int front = 0, rear = 0;
queue[rear++] = root;
while (front != rear) {
TreeNode* cur = queue[front++];
res[(*idx)++] = cur->val;
if (cur->left != NULL) {
queue[rear++] = cur->left;
}
if (cur->right != NULL) {
queue[rear++] = cur->right;
}
}
}
```
接下来,我们可以求二叉树的深度。可以使用递归的方式,每次递归返回左右子树深度的最大值加1:
```c
int maxDepth(TreeNode* root) {
if (root == NULL) {
return 0;
}
int leftDepth = maxDepth(root->left);
int rightDepth = maxDepth(root->right);
return fmax(leftDepth, rightDepth) + 1;
}
```
最后,我们可以求二叉树的叶子节点个数。同样可以使用递归的方式,每次递归返回左右子树叶子节点个数之和:
```c
int leafCount(TreeNode* root) {
if (root == NULL) {
return 0;
}
if (root->left == NULL && root->right == NULL) {
return 1;
}
int leftCount = leafCount(root->left);
int rightCount = leafCount(root->right);
return leftCount + rightCount;
}
```
最后,我们可以编写一个漂亮、实用的功能菜单,每个功能用一函数表示:
```c
void menu() {
printf("1. 构造二叉树\n");
printf("2. 先序遍历二叉树\n");
printf("3. 中序遍历二叉树\n");
printf("4. 后序遍历二叉树\n");
printf("5. 层次遍历二叉树\n");
printf("6. 求二叉树深度\n");
printf("7. 求二叉树叶子节点个数\n");
printf("8. 退出\n");
}
TreeNode* root = NULL;
void createTree() {
printf("请输入二叉树的先序遍历序列(-1表示空节点):\n");
root = buildTree();
}
void traverse(int choice) {
int res[1000];
int idx = 0;
switch (choice) {
case 2:
printf("先序遍历结果为:");
preorderTraversal(root, res, &idx);
break;
case 3:
printf("中序遍历结果为:");
inorderTraversal(root, res, &idx);
break;
case 4:
printf("后序遍历结果为:");
postorderTraversal(root, res, &idx);
break;
case 5:
printf("层次遍历结果为:");
levelTraversal(root, res, &idx);
break;
}
for (int i = 0; i < idx; i++) {
printf("%d ", res[i]);
}
printf("\n");
}
void depth() {
int depth = maxDepth(root);
printf("二叉树深度为:%d\n", depth);
}
void leaf() {
int count = leafCount(root);
printf("二叉树叶子节点个数为:%d\n", count);
}
int main() {
int choice = 0;
while (choice != 8) {
menu();
printf("请输入你的选择:");
scanf("%d", &choice);
switch (choice) {
case 1:
createTree();
break;
case 2:
case 3:
case 4:
case 5:
traverse(choice);
break;
case 6:
depth();
break;
case 7:
leaf();
break;
case 8:
printf("再见!\n");
break;
default:
printf("输入错误,请重新输入!\n");
break;
}
}
return 0;
}
```
这样就完成了二叉树的基本操作,希望能对你有所帮助!
阅读全文