C语言二叉树
时间: 2023-07-02 18:09:52 浏览: 88
二叉树是一种常用的数据结构,C语言中可以使用结构体来实现二叉树。
首先定义二叉树的结构体:
```
typedef struct TreeNode {
int data;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
```
其中,data表示该节点存储的数据,left和right分别表示左子树和右子树的指针。
接下来,我们可以实现二叉树的插入操作:
```
void insert(TreeNode** root, int data) {
if (*root == NULL) {
*root = (TreeNode*)malloc(sizeof(TreeNode));
(*root)->data = data;
(*root)->left = NULL;
(*root)->right = NULL;
} else if (data < (*root)->data) {
insert(&((*root)->left), data);
} else {
insert(&((*root)->right), data);
}
}
```
这里使用了双重指针,方便对根节点进行操作。当根节点为空时,新建一个节点;否则根据大小关系递归插入到左子树或右子树中。
接着,我们可以实现二叉树的查找操作:
```
TreeNode* search(TreeNode* root, int data) {
if (root == NULL) {
return NULL;
} else if (data == root->data) {
return root;
} else if (data < root->data) {
return search(root->left, data);
} else {
return search(root->right, data);
}
}
```
当根节点为空时,返回空指针;当根节点的数据与查找数据相等时,返回该节点;否则根据大小关系递归查找左子树或右子树。
最后,我们可以实现二叉树的遍历操作,包括先序遍历、中序遍历和后序遍历:
```
void preOrder(TreeNode* root) {
if (root != NULL) {
printf("%d ", root->data);
preOrder(root->left);
preOrder(root->right);
}
}
void inOrder(TreeNode* root) {
if (root != NULL) {
inOrder(root->left);
printf("%d ", root->data);
inOrder(root->right);
}
}
void postOrder(TreeNode* root) {
if (root != NULL) {
postOrder(root->left);
postOrder(root->right);
printf("%d ", root->data);
}
}
```
先序遍历先输出根节点,再遍历左子树和右子树;中序遍历先遍历左子树,再输出根节点,最后遍历右子树;后序遍历先遍历左子树和右子树,最后输出根节点。
完整代码如下:
```
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
int data;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
void insert(TreeNode** root, int data) {
if (*root == NULL) {
*root = (TreeNode*)malloc(sizeof(TreeNode));
(*root)->data = data;
(*root)->left = NULL;
(*root)->right = NULL;
} else if (data < (*root)->data) {
insert(&((*root)->left), data);
} else {
insert(&((*root)->right), data);
}
}
TreeNode* search(TreeNode* root, int data) {
if (root == NULL) {
return NULL;
} else if (data == root->data) {
return root;
} else if (data < root->data) {
return search(root->left, data);
} else {
return search(root->right, data);
}
}
void preOrder(TreeNode* root) {
if (root != NULL) {
printf("%d ", root->data);
preOrder(root->left);
preOrder(root->right);
}
}
void inOrder(TreeNode* root) {
if (root != NULL) {
inOrder(root->left);
printf("%d ", root->data);
inOrder(root->right);
}
}
void postOrder(TreeNode* root) {
if (root != NULL) {
postOrder(root->left);
postOrder(root->right);
printf("%d ", root->data);
}
}
int main() {
TreeNode* root = NULL;
insert(&root, 5);
insert(&root, 3);
insert(&root, 7);
insert(&root, 1);
insert(&root, 4);
insert(&root, 6);
insert(&root, 8);
TreeNode* node = search(root, 6);
if (node != NULL) {
printf("%d\n", node->data);
} else {
printf("Not found\n");
}
preOrder(root);
printf("\n");
inOrder(root);
printf("\n");
postOrder(root);
printf("\n");
return 0;
}
```