c语言编程实现二叉树的基本运算(包括查找、插入、删除节点等)以及”二叉树与树的相互转换 点击复制后,将打开C知道体验页”,并提供可供程序(包括基本运算)测试的界面
时间: 2024-05-10 16:14:52 浏览: 89
数据结构二叉树查找方式
5星 · 资源好评率100%
以下是实现二叉树基本运算(查找、插入、删除节点)的C语言代码,同时包括了二叉树与树的相互转换:
```c
#include <stdio.h>
#include <stdlib.h>
/* 二叉树节点结构体 */
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
/* 插入节点 */
struct TreeNode* insert(struct TreeNode* root, int val) {
if (root == NULL) {
root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
root->val = val;
root->left = NULL;
root->right = NULL;
} else if (val < root->val) {
root->left = insert(root->left, val);
} else if (val > root->val) {
root->right = insert(root->right, val);
}
return root;
}
/* 查找节点 */
struct TreeNode* search(struct TreeNode* root, int val) {
if (root == NULL || root->val == val) {
return root;
} else if (val < root->val) {
return search(root->left, val);
} else {
return search(root->right, val);
}
}
/* 删除节点 */
struct TreeNode* delete(struct TreeNode* root, int val) {
if (root == NULL) {
return root;
} else if (val < root->val) {
root->left = delete(root->left, val);
} else if (val > root->val) {
root->right = delete(root->right, val);
} else {
/* 找到要删除的节点 */
if (root->left == NULL) {
/* 只有右子树或没有子树 */
struct TreeNode* temp = root->right;
free(root);
return temp;
} else if (root->right == NULL) {
/* 只有左子树 */
struct TreeNode* temp = root->left;
free(root);
return temp;
} else {
/* 左右子树都存在 */
struct TreeNode* temp = root->right;
while (temp->left != NULL) {
temp = temp->left;
}
root->val = temp->val;
root->right = delete(root->right, temp->val);
}
}
return root;
}
/* 打印二叉树 */
void printTree(struct TreeNode* root, int level) {
if (root != NULL) {
printTree(root->right, level + 1);
for (int i = 0; i < level; i++) {
printf(" ");
}
printf("%d\n", root->val);
printTree(root->left, level + 1);
}
}
/* 节点结构体 */
struct Node {
int val;
struct Node* children;
struct Node* sibling;
};
/* 将二叉树转换为树 */
struct Node* convertToTree(struct TreeNode* root) {
if (root == NULL) {
return NULL;
}
struct Node* node = (struct Node*)malloc(sizeof(struct Node));
node->val = root->val;
node->children = convertToTree(root->left);
node->sibling = convertToTree(root->right);
return node;
}
/* 将树转换为二叉树 */
struct TreeNode* convertToBinaryTree(struct Node* root) {
if (root == NULL) {
return NULL;
}
struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
node->val = root->val;
node->left = convertToBinaryTree(root->children);
node->right = convertToBinaryTree(root->sibling);
return node;
}
int main() {
struct TreeNode* root = NULL;
int choice = 0;
int val = 0;
while (1) {
printf("1. 插入节点\n");
printf("2. 查找节点\n");
printf("3. 删除节点\n");
printf("4. 打印二叉树\n");
printf("5. 将二叉树转换为树\n");
printf("6. 将树转换为二叉树\n");
printf("7. 退出程序\n");
printf("请输入选项:");
scanf("%d", &choice);
switch (choice) {
case 1:
printf("请输入要插入的节点值:");
scanf("%d", &val);
root = insert(root, val);
break;
case 2:
printf("请输入要查找的节点值:");
scanf("%d", &val);
if (search(root, val) != NULL) {
printf("节点存在\n");
} else {
printf("节点不存在\n");
}
break;
case 3:
printf("请输入要删除的节点值:");
scanf("%d", &val);
root = delete(root, val);
break;
case 4:
printTree(root, 0);
break;
case 5:
struct Node* tree = convertToTree(root);
printf("树的结构:\n");
printf("%d\n", tree->val);
printf(" %d\n", tree->children->val);
printf(" %d\n", tree->children->children->val);
printf(" %d\n", tree->children->sibling->val);
printf(" %d\n", tree->children->sibling->children->val);
break;
case 6:
struct TreeNode* binaryTree = convertToBinaryTree(root);
printf("二叉树结构:\n");
printTree(binaryTree, 0);
break;
case 7:
exit(0);
default:
printf("输入有误,请重新输入\n");
break;
}
}
return 0;
}
```
程序的测试界面比较简单,用户可以通过选择菜单选项来进行二叉树的基本操作,同时也可以转换为树或者树转换为二叉树。界面上会根据用户的操作实时输出二叉树的结构。
阅读全文