面试题：C语言指针数组在复杂数据结构中的应用

Question

假设有一个复杂的数据结构，该结构由多个结构体组成，结构体之间存在指针关联形成一个树形结构。每个结构体中包含一个指针数组，用于指向其孩子节点（孩子节点数量不定）。要求设计一个通用的遍历算法，能够以深度优先搜索（DFS）的方式遍历整个树形结构，并对每个节点进行特定的操作（例如，打印节点的某些属性）。请用C语言实现该算法，并详细说明如何利用指针数组实现树形结构的构建与遍历，同时分析该算法的时间复杂度和空间复杂度。

Answer 1

1. 树形结构构建与遍历实现

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

// 定义结构体
typedef struct TreeNode {
    int data; // 节点数据，以整型为例，可替换为实际属性
    struct TreeNode **children; // 指针数组指向孩子节点
    int childCount; // 孩子节点数量
} TreeNode;

// 创建新节点
TreeNode* createNode(int data) {
    TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
    newNode->data = data;
    newNode->children = NULL;
    newNode->childCount = 0;
    return newNode;
}

// 添加孩子节点
void addChild(TreeNode* parent, TreeNode* child) {
    parent->children = (TreeNode**)realloc(parent->children, (parent->childCount + 1) * sizeof(TreeNode*));
    parent->children[parent->childCount++] = child;
}

// 深度优先搜索遍历
void DFS(TreeNode* root) {
    if (root == NULL) return;
    // 打印节点属性，这里以打印数据为例
    printf("%d ", root->data);
    for (int i = 0; i < root->childCount; i++) {
        DFS(root->children[i]);
    }
}

// 释放内存
void freeTree(TreeNode* root) {
    if (root == NULL) return;
    for (int i = 0; i < root->childCount; i++) {
        freeTree(root->children[i]);
    }
    free(root->children);
    free(root);
}

2. 如何利用指针数组实现树形结构的构建与遍历

• 构建：通过createNode函数创建单个节点，使用addChild函数为父节点动态分配内存并添加孩子节点指针到指针数组children中，同时更新childCount记录孩子节点数量。
• 遍历：在DFS函数中，首先访问当前节点（这里进行打印操作），然后通过循环遍历指针数组children，递归调用DFS对每个孩子节点进行深度优先搜索。

3. 时间复杂度分析

假设树中节点数为 n，每个节点访问一次，并且每个节点对其孩子节点的遍历操作与孩子节点数量相关。因为每个节点访问和对其孩子节点的操作次数线性相关，所以时间复杂度为 O(n)。

4. 空间复杂度分析

• 最坏情况下，递归调用栈的深度等于树的高度。对于一般的树，高度最大为 n（即树退化为链表的情况），所以空间复杂度为 O(n)。
• 如果树是平衡树，高度为 log(n)，空间复杂度为 O(log(n))。这里按最坏情况考虑，空间复杂度为 O(n)，主要由递归调用栈占用的空间决定。

5. 测试代码

int main() {
    TreeNode* root = createNode(1);
    TreeNode* node2 = createNode(2);
    TreeNode* node3 = createNode(3);
    TreeNode* node4 = createNode(4);
    TreeNode* node5 = createNode(5);

    addChild(root, node2);
    addChild(root, node3);
    addChild(node2, node4);
    addChild(node2, node5);

    printf("深度优先搜索遍历结果: ");
    DFS(root);
    printf("\n");

    freeTree(root);
    return 0;
}