二叉树二叉链表队列数据结构

Question

如图所示，二叉树，二叉链表，如何定义结点类型，如何层次遍历输出，如何插入结点，

Answer 1

引自免费微信小程序：皆我百晓生

首先，我们来定义二叉链表节点的数据类型。这个数据类型应该包含一个表示节点值的成员变量，以及两个指向子节点的指针。

typedef struct Node {
    char name[20];  // 设备或分类名，这里假设最大长度为20个字符
    struct Node* left;  // 左子节点
    struct Node* right;  // 右子节点
} Node;

接下来是初始化二叉链表。由于题目没有提供具体的初始化函数，我们可以简单地手动创建一个二叉树结构，然后通过递归的方式插入节点。

Node* createTree(const char* names[], int numNodes) {
    if (numNodes == 0) return NULL;

    Node* root = (Node*)malloc(sizeof(Node));
    strcpy(root->name, names[0]);
    root->left = createTree(names + 1, numNodes - 2);
    root->right = createTree(names + numNodes - 1, numNodes - 2);

    return root;
}

int main() {
    const char* deviceNames[] = {"电力设备", "一次设备", "二次设备", "发电机", "继电保护装置"};
    Node* tree = createTree(deviceNames, sizeof(deviceNames) / sizeof(deviceNames[0]));
    // 输出初始二叉树
    printLevelOrder(tree);
    return 0;
}

为了实现层次遍历，我们需要一个辅助函数来按照层次顺序打印二叉树。

void printLevelOrder(Node* root) {
    if (root == NULL) return;

    Queue* queue = createQueue();  // 假设有一个名为createQueue的函数用于创建队列
    enqueue(queue, root);  // 将根节点入队

    while (!isQueueEmpty(queue)) {
        Node* node = dequeue(queue);
        printf("%s ", node->name);

        if (node->left != NULL) enqueue(queue, node->left);
        if (node->right != NULL) enqueue(queue, node->right);
    }

    destroyQueue(queue);  // 假设有一个名为destroyQueue的函数用于销毁队列
}

对于剩余的问题，我们将分别编写函数来解决。这里假设已经提供了队列的实现，包括enqueue, dequeue, isQueueEmpty 和 destroyQueue 函数。

1. 查找并输出所有最低一级设备名：

void printLeaves(Node* root) {
    if (root == NULL) return;

    Queue* queue = createQueue();
    enqueue(queue, root);

    while (!isQueueEmpty(queue)) {
        Node* node = dequeue(queue);
        if (node->left == NULL && node->right == NULL) {
            printf("%s ", node->name);
        } else {
            if (node->left != NULL) enqueue(queue, node->left);
            if (node->right != NULL) enqueue(queue, node->right);
        }
    }

    destroyQueue(queue);
}

1. 输出所有分类名：

void printBranches(Node* root) {
    if (root == NULL) return;

    Queue* queue = createQueue();
    enqueue(queue, root);

    while (!isQueueEmpty(queue)) {
        Node* node = dequeue(queue);
        if (node->left != NULL || node->right != NULL) {
            printf("%s ", node->name);
        } else {
            enqueue(queue, node->left);
            enqueue(queue, node->right);
        }
    }

    destroyQueue(queue);
}

1. 删除某一分类包含的全部设备及该分类：

void deleteCategory(Node** root, const char* category) {
    Node* current = *root;
    Node* parent = NULL;

    while (current != NULL && strcmp(current->name, category) != 0) {
        parent = current;
        if (strcmp(category, current->name) > 0) {
            current = current->left;
        } else {
            current = current->right;
        }
    }

    if (current == NULL) return;

    if (current->left == NULL && current->right == NULL) {
        if (parent == NULL) *root = NULL;
        else if (strcmp(parent->name, current->name) < 0) {
            parent->left = NULL;
        } else {
            parent->right = NULL;
        }
    } else if (current->left == NULL) {
        if (parent == NULL) *root = current->right;
        else if (strcmp(parent->name, current->name) < 0) {
            parent->left = current->right;
        } else {
            parent->right = current->right;
        }
    } else if (current->right == NULL) {
        if (parent == NULL) *root = current->left;
        else if (strcmp(parent->name, current->name) < 0) {
            parent->left = current->left;
        } else {
            parent->right = current->left;
        }
    } else {
        Node* temp = findMinNode(current->right);
        current->name = temp->name;
        deleteCategory(&current->right, temp->name);
    }

    free(current);
}

1. 插入一个分类：

Node* insertCategory(Node* root, const char* categoryName) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    strcpy(newNode->name, categoryName);
    newNode->left = newNode->right = NULL;

    if (root == NULL) return newNode;

    Node* current = root;
    Node* parent = NULL;

    while (current != NULL) {
        parent = current;
        if (strcmp(categoryName, current->name) < 0) {
            current = current->left;
        } else {
            current = current->right;
        }
    }

    if (strcmp(categoryName, parent->name) < 0) {
        parent->left = newNode;
    } else {
        parent->right = newNode;
    }

    return root;
}

1. 继续在“电力变压器”分类下插入“单相”，“三相”两种设备分类名：

Node* insertSubcategory(Node* root, const char* parentName, const char* subcategoryName) {
    Node* parent = searchNode(root, parentName);
    if (parent == NULL) return root;

    Node* newNode = (Node*)malloc(sizeof(Node));
    strcpy(newNode->name, subcategoryName);
    newNode->left = newNode->right = NULL;

    if (strcmp(subcategoryName, parent->name) < 0) {
        parent->left = newNode;
    } else {
        parent->right = newNode;
    }

    return root;
}

Node* searchNode(Node* root, const char* targetName) {
    if (root == NULL || strcmp(root->name, targetName) == 0) return root;

    if (strcmp(targetName, root->name) < 0) {
        return searchNode(root->left, targetName);
    } else {
        return searchNode(root->right, targetName);
    }
}

注意，这些代码片段可能需要与您的实际项目结构相结合，例如您可能需要自己实现队列或搜索功能。您可以根据实际情况调整这些代码片段。