用C语言写一个二叉树的基本操作代码,包括前中后遍历,层次遍历,子叶数,结点数
时间: 2023-06-12 12:05:25 浏览: 51
下面是基本操作代码的实现:
```c
#include <stdio.h>
#include <stdlib.h>
//节点结构体
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
//创建节点
TreeNode* create_node(int val) {
TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
node->val = val;
node->left = NULL;
node->right = NULL;
return node;
}
//插入节点
void insert_node(TreeNode **root, int val) {
if (*root == NULL) {
*root = create_node(val);
return;
}
if (val < (*root)->val) {
insert_node(&((*root)->left), val);
} else {
insert_node(&((*root)->right), val);
}
}
//前序遍历
void preorder_traversal(TreeNode* root) {
if (root == NULL) {
return;
}
printf("%d ", root->val);
preorder_traversal(root->left);
preorder_traversal(root->right);
}
//中序遍历
void inorder_traversal(TreeNode* root) {
if (root == NULL) {
return;
}
inorder_traversal(root->left);
printf("%d ", root->val);
inorder_traversal(root->right);
}
//后序遍历
void postorder_traversal(TreeNode* root) {
if (root == NULL) {
return;
}
postorder_traversal(root->left);
postorder_traversal(root->right);
printf("%d ", root->val);
}
//层次遍历
void level_traversal(TreeNode* root) {
if (root == NULL) {
return;
}
TreeNode* queue[1000];
int head = 0, tail = 0;
queue[tail++] = root;
while (head < tail) {
TreeNode* node = queue[head++];
printf("%d ", node->val);
if (node->left != NULL) {
queue[tail++] = node->left;
}
if (node->right != NULL) {
queue[tail++] = node->right;
}
}
}
//求子叶数
int leaf_count(TreeNode* root) {
if (root == NULL) {
return 0;
}
if (root->left == NULL && root->right == NULL) {
return 1;
}
return leaf_count(root->left) + leaf_count(root->right);
}
//求节点数
int node_count(TreeNode* root) {
if (root == NULL) {
return 0;
}
return 1 + node_count(root->left) + node_count(root->right);
}
int main() {
TreeNode* root = NULL;
insert_node(&root, 5);
insert_node(&root, 3);
insert_node(&root, 7);
insert_node(&root, 2);
insert_node(&root, 4);
insert_node(&root, 6);
insert_node(&root, 8);
printf("前序遍历:");
preorder_traversal(root);
printf("\n");
printf("中序遍历:");
inorder_traversal(root);
printf("\n");
printf("后序遍历:");
postorder_traversal(root);
printf("\n");
printf("层次遍历:");
level_traversal(root);
printf("\n");
printf("子叶数:%d\n", leaf_count(root));
printf("节点数:%d\n", node_count(root));
return 0;
}
```
以上代码实现了二叉树的基本操作,包括前中后遍历,层次遍历,子叶数,结点数。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)