二叉树的各种操作c语言实现
时间: 2023-11-14 14:12:31 浏览: 35
下面是二叉树的基本操作的C语言实现:
结构体定义:
```
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
```
1. 创建二叉树
```
struct TreeNode* createTree(int val) {
struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
root->val = val;
root->left = NULL;
root->right = NULL;
return root;
}
void insertLeft(struct TreeNode* root, int val) {
struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
newNode->val = val;
newNode->left = NULL;
newNode->right = NULL;
root->left = newNode;
}
void insertRight(struct TreeNode* root, int val) {
struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
newNode->val = val;
newNode->left = NULL;
newNode->right = NULL;
root->right = newNode;
}
```
2. 二叉树的遍历
```
// 前序遍历
void preorderTraversal(struct TreeNode* root) {
if (root == NULL) {
return;
}
printf("%d ", root->val);
preorderTraversal(root->left);
preorderTraversal(root->right);
}
// 中序遍历
void inorderTraversal(struct TreeNode* root) {
if (root == NULL) {
return;
}
inorderTraversal(root->left);
printf("%d ", root->val);
inorderTraversal(root->right);
}
// 后序遍历
void postorderTraversal(struct TreeNode* root) {
if (root == NULL) {
return;
}
postorderTraversal(root->left);
postorderTraversal(root->right);
printf("%d ", root->val);
}
```
3. 二叉树的查找
```
struct TreeNode* search(struct TreeNode* root, int val) {
if (root == NULL) {
return NULL;
}
if (root->val == val) {
return root;
}
struct TreeNode* left = search(root->left, val);
if (left != NULL) {
return left;
}
struct TreeNode* right = search(root->right, val);
if (right != NULL) {
return right;
}
return NULL;
}
```
4. 二叉树的删除
```
struct TreeNode* deleteNode(struct TreeNode* root, int key) {
if (root == NULL) {
return NULL;
}
if (root->val == key) {
if (root->left == NULL && root->right == NULL) {
free(root);
return NULL;
}
if (root->left == NULL) {
struct TreeNode* right = root->right;
free(root);
return right;
}
if (root->right == NULL) {
struct TreeNode* left = root->left;
free(root);
return left;
}
struct TreeNode* min = root->right;
while (min->left != NULL) {
min = min->left;
}
root->val = min->val;
root->right = deleteNode(root->right, min->val);
} else if (root->val > key) {
root->left = deleteNode(root->left, key);
} else {
root->right = deleteNode(root->right, key);
}
return root;
}
```