C语言的链二叉树,需要建立树,入树,左插入,右插入,销毁树,销毁左树,销毁右树,输出树
时间: 2023-07-15 13:13:09 浏览: 49
以下是C语言实现链式二叉树的相关操作代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树结构体
typedef struct BinTreeNode {
int data; // 数据域
struct BinTreeNode *leftChild; // 左子树指针
struct BinTreeNode *rightChild; // 右子树指针
} BinTreeNode, *BinTree;
// 创建树
void createBinTree(BinTree *T) {
int data;
scanf("%d", &data); // 输入数据
if (data == -1) {
*T = NULL; // 如果输入为-1,表示该节点为空
} else {
*T = (BinTree) malloc(sizeof(BinTreeNode)); // 分配内存
(*T)->data = data; // 将输入的数据赋值给该节点
createBinTree(&((*T)->leftChild)); // 递归创建左子树
createBinTree(&((*T)->rightChild)); // 递归创建右子树
}
}
// 入树
void insertBinTree(BinTree *T, int data) {
if (*T == NULL) { // 如果树为空,直接插入
*T = (BinTree) malloc(sizeof(BinTreeNode)); // 分配内存
(*T)->data = data; // 赋值数据
(*T)->leftChild = NULL; // 左子树为空
(*T)->rightChild = NULL; // 右子树为空
} else {
if (data < (*T)->data) { // 如果插入数据小于当前节点的数据
insertBinTree(&((*T)->leftChild), data); // 递归插入左子树
} else { // 如果插入数据大于等于当前节点的数据
insertBinTree(&((*T)->rightChild), data); // 递归插入右子树
}
}
}
// 左插入
void insertLeft(BinTree *T, int parentData, int data) {
if (*T == NULL) {
return; // 如果树为空,直接返回
}
if ((*T)->data == parentData) { // 如果找到父节点
BinTree newNode = (BinTree) malloc(sizeof(BinTreeNode)); // 分配内存
newNode->data = data; // 赋值数据
newNode->leftChild = (*T)->leftChild; // 新节点的左子树指针指向原来父节点的左子树
newNode->rightChild = NULL; // 新节点的右子树为空
(*T)->leftChild = newNode; // 父节点的左子树指针指向新节点
} else {
insertLeft(&((*T)->leftChild), parentData, data); // 递归查找父节点
insertLeft(&((*T)->rightChild), parentData, data); // 递归查找父节点
}
}
// 右插入
void insertRight(BinTree *T, int parentData, int data) {
if (*T == NULL) {
return; // 如果树为空,直接返回
}
if ((*T)->data == parentData) { // 如果找到父节点
BinTree newNode = (BinTree) malloc(sizeof(BinTreeNode)); // 分配内存
newNode->data = data; // 赋值数据
newNode->leftChild = NULL; // 新节点的左子树为空
newNode->rightChild = (*T)->rightChild; // 新节点的右子树指针指向原来父节点的右子树
(*T)->rightChild = newNode; // 父节点的右子树指针指向新节点
} else {
insertRight(&((*T)->leftChild), parentData, data); // 递归查找父节点
insertRight(&((*T)->rightChild), parentData, data); // 递归查找父节点
}
}
// 销毁树
void destroyBinTree(BinTree *T) {
if (*T == NULL) {
return; // 如果树为空,直接返回
}
destroyBinTree(&((*T)->leftChild)); // 递归销毁左子树
destroyBinTree(&((*T)->rightChild)); // 递归销毁右子树
free(*T); // 释放内存
*T = NULL; // 将指针置为空
}
// 销毁左树
void destroyLeft(BinTree *T) {
if (*T == NULL) {
return; // 如果树为空,直接返回
}
destroyBinTree(&((*T)->leftChild)); // 递归销毁左子树
(*T)->leftChild = NULL; // 将左子树指针置为空
}
// 销毁右树
void destroyRight(BinTree *T) {
if (*T == NULL) {
return; // 如果树为空,直接返回
}
destroyBinTree(&((*T)->rightChild)); // 递归销毁右子树
(*T)->rightChild = NULL; // 将右子树指针置为空
}
// 输出树(中序遍历)
void printBinTree(BinTree T) {
if (T == NULL) {
return; // 如果树为空,直接返回
}
printBinTree(T->leftChild); // 递归输出左子树
printf("%d ", T->data); // 输出当前节点的数据
printBinTree(T->rightChild); // 递归输出右子树
}
int main() {
BinTree T = NULL;
// 测试创建树
printf("请输入二叉树的元素,-1表示该节点为空:\n");
createBinTree(&T);
printf("创建的二叉树为:\n");
printBinTree(T);
printf("\n");
// 测试入树
int data;
printf("请输入要插入的数据:\n");
scanf("%d", &data);
insertBinTree(&T, data);
printf("插入后的二叉树为:\n");
printBinTree(T);
printf("\n");
// 测试左插入
int parentData;
printf("请输入要插入的父节点的数据和要插入的数据,用空格隔开:\n");
scanf("%d %d", &parentData, &data);
insertLeft(&T, parentData, data);
printf("左插入后的二叉树为:\n");
printBinTree(T);
printf("\n");
// 测试右插入
printf("请输入要插入的父节点的数据和要插入的数据,用空格隔开:\n");
scanf("%d %d", &parentData, &data);
insertRight(&T, parentData, data);
printf("右插入后的二叉树为:\n");
printBinTree(T);
printf("\n");
// 测试销毁树
destroyBinTree(&T);
printf("销毁二叉树后的结果为:\n");
printBinTree(T);
return 0;
}
```