如何用孩子兄弟表示法存储树

孩子兄弟表示法是一种树的存储方式，它使用了指针来表示树的各个节点之间的关系。具体来说，孩子兄弟表示法将每个节点表示为一个结构体，结构体中包含三个指针：指向该节点的第一个孩子节点的指针、指向该节点的下一个兄弟节点的指针和指向该节点的父节点的指针（可选）。这样，我们可以通过遍历每个节点的孩子和兄弟节点来遍历整棵树。

下面是一个示例代码，展示如何用孩子兄弟表示法存储一棵树：

// 树节点的结构体
struct TreeNode {
    int val;
    struct TreeNode* firstChild; // 指向第一个孩子节点的指针
    struct TreeNode* nextSibling; // 指向下一个兄弟节点的指针
    struct TreeNode* parent; // 指向父节点的指针（可选）
};

// 创建一颗树
struct TreeNode* createTree(int val) {
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node->val = val;
    node->firstChild = NULL;
    node->nextSibling = NULL;
    node->parent = NULL;
    return node;
}

// 在树中插入一个节点
void insertNode(struct TreeNode* parent, int val) {
    if (parent == NULL) return;
    struct TreeNode* node = createTree(val);
    node->parent = parent;
    if (parent->firstChild == NULL) {
        parent->firstChild = node;
    } else {
        struct TreeNode* ptr = parent->firstChild;
        while (ptr->nextSibling != NULL) {
            ptr = ptr->nextSibling;
        }
        ptr->nextSibling = node;
    }
}

// 遍历树
void traverseTree(struct TreeNode* root) {
    if (root == NULL) return;
    printf("%d ", root->val);
    traverseTree(root->firstChild);
    traverseTree(root->nextSibling);
}

// 示例用法
int main() {
    struct TreeNode* root = createTree(1);
    insertNode(root, 2);
    insertNode(root, 3);
    insertNode(root->firstChild, 4);
    insertNode(root->firstChild, 5);
    insertNode(root->firstChild->nextSibling, 6);
    insertNode(root->firstChild->nextSibling, 7);
    traverseTree(root); // 输出：1 2 4 5 3 6 7
    return 0;
}

在上面的示例代码中，我们使用了孩子兄弟表示法存储了一棵树，并通过遍历树的方式输出了树的节点。需要注意的是，由于孩子兄弟表示法只保存了每个节点的孩子和兄弟节点的指针，因此我们需要在插入节点时手动设置节点的父节点指针。