C语言二叉树实现：插入节点、删除节点、层次输出和查找

C语言实现二叉树操作

本代码使用 C语言实现了一个简单的二叉树，并演示了插入节点、删除节点、层次输出、查找最低一级节点等操作。

代码实现：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 定义二叉链表节点
typedef struct node {
    struct node *lchild, *rchild;
    char code[10];
    char name[20];
} Node;

// 创造节点
Node* createnode(char* code, char* name) {
    Node* newnode = (Node*)malloc(sizeof(Node));
    strcpy(newnode->code, code);
    strcpy(newnode->name, name);
    newnode->lchild = NULL;
    newnode->rchild = NULL;
    return newnode;
}

// 插入结点
Node* insertNode(Node* root, char* code, char* name) {
    if (root == NULL) { // 说明原树为空
        return createnode(code, name);
    }
    if (root->lchild == NULL) {
        root->lchild = insertNode(root->lchild, code, name);
    } else {
        root->rchild = insertNode(root->rchild, code, name);
    }
    return root;
}

// 递归实现层次输出
void cenciprint(Node* root) {
    if (root == NULL) {
        return;
    }
    printf('%s\n', root->name);
    if (root->lchild != NULL) {
        printf(' ');
        cenciprint(root->lchild);
    }
    if (root->rchild != NULL) {
        cenciprint(root->rchild);
    }
}

// 递归查找最低一级缺陷名
void find(Node* root) {
    if (root == NULL) {
        return;
    }
    if (root->lchild == NULL) {
        printf('%s ', root->name);
    }
    find(root->lchild);
    find(root->rchild); 
}

// 递归输出所有节点名
void printall(Node* root) {
    if (root == NULL) {
        return;
    }
    printf('%s ', root->name);
    printall(root->lchild);
    printall(root->rchild);
}

// 递归删除节点
Node* deletenode(Node* root, char* code) {
    if (root == NULL) {
        return NULL;
    }
    if (strcmp(root->code, code) == 0) {
        Node* left = root->lchild;
        Node* right = root->rchild;
        free(root);
        if (left == NULL) {
            return right;
        }
        if (right == NULL) {
            return left;
        }
        Node* cur = left;
        while (cur->rchild != NULL) {
            cur = cur->rchild;
        }
        cur->rchild = right;
        return left;
    } else {
        root->lchild = deletenode(root->lchild, code);
        root->rchild = deletenode(root->rchild, code);
        return root;
    }
}

int main() {
    // 初始化创建二叉链表
    Node* root = createnode('SBQX01', '设备缺陷');
    root = insertNode(root, 'YLQX01', '一类缺陷', 'SBQX01');
    root = insertNode(root, 'ELQX02', '二类缺陷', 'SBQX01');
    root = insertNode(root, 'WDYC01', '发电机线圈温度异常', 'YLQX01');
    root = insertNode(root, 'DJYY01', '煤机清扫电机异音', 'ELQX02');

    // 按层次输出
    printf('按层次所属关系输出:\n');
    cenciprint(root);

    // 查找并输出所有最低一级缺陷名
    printf('所有最低一级缺陷名:\n');
    find(root);
    printf('\n');

    // 输出所有分类名
    printf('所有分类名:\n');
    printall(root);
    printf('\n');

    // 在“一类缺陷”下插入“电动阀电气故障 ”，“二类缺陷”下插入””
    root = insertNode(root, 'DDFDQGZ01', '电动阀电气故障', 'YLQX01');
    root = insertNode(root, 'JDBHZZ01', '继电保护装置', 'ELQX02');
    root = insertNode(root, 'SFJJSZD01', '送风机绝缘值低', 'ELQX02');

    // 按层次输出
    printf('插入节点后按层次所属关系输出:\n');
    cenciprint(root);

    // 删除某一分类及其包含的所有缺陷
    root = deletenode(root, 'ELQX02');

    // 按层次输出
    printf('删除二类缺陷后按层次所属关系输出:\n');
    cenciprint(root);

    return 0;
}

代码解析：

节点定义： 代码首先定义了二叉树节点的结构体 Node，包含左孩子 lchild、右孩子 rchild、代码 code 和名称 name。
创建节点： 函数 createnode() 用于创建新的节点，并初始化其成员变量。
插入节点： 函数 insertNode() 用于向二叉树中插入新节点。该函数采用递归方法，首先判断当前节点是否为空，如果是则直接创建并返回新节点。否则，递归地将新节点插入到左子树或右子树中。
层次输出： 函数 cenciprint() 使用递归方法实现二叉树的层次输出。该函数首先输出当前节点的名称，然后递归地输出其左子树和右子树。在输出左子树时，会先输出一个空格，以区分不同的层级。
查找最低一级节点： 函数 find() 使用递归方法实现查找所有最低一级节点。该函数首先判断当前节点是否为叶子节点，如果是则输出其名称。否则，递归地查找其左子树和右子树。
输出所有节点： 函数 printall() 使用递归方法实现输出所有节点。该函数首先输出当前节点的名称，然后递归地输出其左子树和右子树。
删除节点： 函数 deletenode() 使用递归方法实现删除节点。该函数首先判断当前节点是否为要删除的节点，如果是则释放该节点的内存，并将左子树和右子树连接起来。否则，递归地删除其左子树和右子树。

示例：

本代码中使用了一组数据模拟实际应用场景，演示了二叉树的基本操作。代码中首先创建了一个名为 '设备缺陷' 的根节点，然后插入了 '一类缺陷'、'二类缺陷' 等子节点，以及 '发电机线圈温度异常'、'煤机清扫电机异音' 等最低一级节点。最后，代码删除了 '二类缺陷' 节点，并输出结果。

总结：

本代码演示了使用 C语言实现二叉树的基本操作，包括插入节点、删除节点、层次输出和查找最低一级节点。代码采用递归方法实现，并附带详细注释，方便理解和学习。

代码改进：

代码可以进一步改进，例如：

添加更多操作，例如查找指定节点、修改节点值等。
使用非递归方法实现某些操作，例如层次输出、查找指定节点等。
使用更规范的代码风格，例如添加函数注释、使用更具描述性的变量名等。

注意：

本代码仅供学习参考，实际应用中可能需要根据具体需求进行修改。

两段代码的区别

两段代码的主要区别在于 插入节点函数 和 按层次输出函数 的实现方式不同。

第一段代码：

插入节点函数使用条件判断语句，每次递归判断当前节点是否为父节点，如果是则在左孩子或右孩子上插入新节点，否则继续递归左右子树。
按层次输出函数先输出当前节点的名称，再递归输出左孩子和右孩子。

第二段代码：

插入节点函数使用递归实现，每次递归判断当前节点是否为父节点，如果是则在左孩子或右孩子上插入新节点，否则继续递归左右子树。
按层次输出函数先递归输出左孩子和右孩子，再输出当前节点的名称，并在输出左孩子时先输出一个空格。

两种实现方式各有优劣：

条件判断语句实现的插入节点函数代码量相对较少，但可读性较差。
递归实现的插入节点函数代码量相对较多，但可读性较好。
先输出当前节点再递归输出的按层次输出函数代码量相对较少，但输出顺序与树的结构不完全一致。
先递归输出再输出当前节点的按层次输出函数代码量相对较多，但输出顺序与树的结构完全一致。

实际应用中，可以选择最适合的实现方式。