C 语言完成 二叉树的基本操作 内容:使用二叉链表存储结构建立一棵二叉树,完成如下功能: 1.创建二叉树 2.先序遍历二叉树 3.中序遍历二叉树 4.后序遍历二叉树 5.求二叉树深度 6.求二叉树叶子结点个数。输入和输出
时间: 2024-05-10 10:12:00 浏览: 133
C语言可以使用二叉链表存储结构来建立一棵二叉树,并完成以下基本操作:
1. 创建二叉树:
- 首先定义一个二叉树的结构体,包含一个数据域和两个指向左右子树的指针。
- 使用递归的方式,按照先序遍历的顺序输入节点的值,当输入值为特定标识(如-1)时表示该节点为空。
- 递归地创建左子树和右子树。
2. 先序遍历二叉树:
- 先访问根节点,然后递归地先序遍历左子树,再递归地先序遍历右子树。
- 在遍历过程中可以输出节点的值。
3. 中序遍历二叉树:
- 先递归地中序遍历左子树,然后访问根节点,最后递归地中序遍历右子树。
- 在遍历过程中可以输出节点的值。
4. 后序遍历二叉树:
- 先递归地后序遍历左子树,然后递归地后序遍历右子树,最后访问根节点。
- 在遍历过程中可以输出节点的值。
5. 求二叉树深度:
- 使用递归的方式,分别求左子树和右子树的深度,取较大值加1即为整棵二叉树的深度。
6. 求二叉树叶子节点个数:
- 使用递归的方式,如果当前节点为空,则返回0;如果当前节点没有左右子树,则返回1;否则递归地求左子树和右子树的叶子节点个数之和。
以下是C语言实现上述功能的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树结构体
typedef struct TreeNode {
int data;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
// 创建二叉树
TreeNode* createBinaryTree() {
int value;
scanf("%d", &value);
if (value == -1) {
return NULL;
}
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
root->data = value;
root->left = createBinaryTree();
root->right = createBinaryTree();
return root;
}
// 先序遍历二叉树
void preOrderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
printf("%d ", root->data);
preOrderTraversal(root->left);
preOrderTraversal(root->right);
}
// 中序遍历二叉树
void inOrderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
inOrderTraversal(root->left);
printf("%d ", root->data);
inOrderTraversal(root->right);
}
// 后序遍历二叉树
void postOrderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
postOrderTraversal(root->left);
postOrderTraversal(root->right);
printf("%d ", root->data);
}
// 求二叉树深度
int getTreeDepth(TreeNode* root) {
if (root == NULL) {
return 0;
}
int leftDepth = getTreeDepth(root->left);
int rightDepth = getTreeDepth(root->right);
return (leftDepth > rightDepth ? leftDepth : rightDepth) + 1;
}
// 求二叉树叶子节点个数
int getLeafNodeCount(TreeNode* root) {
if (root == NULL) {
return 0;
}
if (root->left == NULL && root->right == NULL) {
return 1;
}
int leftCount = getLeafNodeCount(root->left);
int rightCount = getLeafNodeCount(root->right);
return leftCount + rightCount;
}
int main() {
printf("请输入二叉树的节点值(-1表示空节点):\n");
TreeNode* root = createBinaryTree();
printf("先序遍历结果:");
preOrderTraversal(root);
printf("\n");
printf("中序遍历结果:");
inOrderTraversal(root);
printf("\n");
printf("后序遍历结果:");
postOrderTraversal(root);
printf("\n");
int depth = getTreeDepth(root);
printf("二叉树深度:%d\n", depth);
int leafCount = getLeafNodeCount(root);
printf("二叉树叶子节点个数:%d\n", leafCount);
return 0;
}
```
阅读全文