c 存储树的数据结构

在C语言中，存储树的数据结构主要有双亲表示法、孩子表示法和孩子兄弟表示法，以下是对这三种方法的详细解释：

1、双亲表示法

定义：假设以一组连续空间存储树的结点，同时在每个结点中附设一个指示器指示其双亲结点到链表中的位置。

结点结构：通常包含数据域和指针域，指针域存储该结点的双亲所在数组中的下标。

代码实现：

“`c

#define MAX_TREE_SIZE 100

typedef int ElemType;

typedef struct PTNode {

ElemType data;

int parent;

} PTNode, *PTree;

优缺点：优点是找双亲结点的时间复杂度为O(1)，向上一直找到根节点也快；缺点是由上向下找就十分慢，若要找结点的孩子或者兄弟，需要遍历整个树。
2、孩子表示法定义：把每个结点的孩子结点都用单链表连接起来形成一个线性结构，n个节点具有n个孩子链表。结点结构：孩子链表的孩子结点包含数据域和指针域，指针域指向下一个孩子结点；表头数组的表头结点包含数据域和头指针域，头指针域指向第一个孩子的指针。代码实现：
      ```c
        #define MAX_TREE_SIZE 100
        typedef int ElemType;
        typedef struct CTNode {
            int child;
            struct CTNode *next;
        } ChildPtr;
        typedef struct {
            ElemType data;
            ChildPtr firstchild;
        } CTBox;
        typedef struct {
            CTBox nodes[MAX_TREE_SIZE];
            int r, n;
        } CTree;

优缺点：查找某个结点的某个孩子或兄弟比较方便，但要知道某个结点的双亲则较困难，需要调整整颗遍历树。

3、孩子兄弟表示法

定义：在树中，每个结点的第一个孩子如果存在就是唯一的，右兄弟如果存在也是唯一的，因此设置两个指针，分别指向该结点的第一个孩子和此结点的右兄弟。

结点结构：包含数据域、指向第一个孩子的指针域和指向右兄弟结点的指针域。

代码实现：

“`c

#define MAX_TREE_SIZE 100

typedef int ElemType;

typedef struct CSNode {

ElemType data;

struct CSNode *firstchild, *rightsib;

} CSNode, *CSTree;

优缺点：查找某个结点的某个孩子很方便，但要知道某个结点的双亲则较困难，需要调整整颗遍历树。
以下是两个关于C存储树的数据结构的常见问题及解答：
1、问：双亲表示法中如何快速找到某个结点的所有孩子？答：双亲表示法本身并不直接支持快速找到某个结点的所有孩子，如果需要找到某个结点的所有孩子，可以通过遍历整个树来实现，可以从根结点开始，递归地遍历每个结点，并检查其孩子指针域是否指向当前结点，如果是，则将该结点添加到当前结点的孩子列表中，这种方法的时间复杂度较高，因此在实际应用中可能不太实用，如果确实需要频繁地查找某个结点的所有孩子，可能需要考虑使用其他存储结构，如孩子表示法或孩子兄弟表示法。
2、问：孩子兄弟表示法中如何删除一个结点及其所有子树？答：在孩子兄弟表示法中删除一个结点及其所有子树是一个相对复杂的操作，因为它涉及到更新多个指针以确保树的结构仍然有效，具体步骤如下：
   首先找到要删除的结点及其所有子树的根结点（即该结点本身）。
   然后递归地删除该子树中的所有左孩子和右兄弟，这可以通过递归地调用删除函数来实现，每次递归都处理当前结点的一个孩子或右兄弟。
   在删除每个结点时，需要将其从内存中释放，并更新其父结点的相应指针域（如果有的话）以确保树的结构仍然有效。
   最后处理完所有子树后，再删除根结点本身（如果它不是整个树的根的话），并更新其父结点的相应指针域（如果有的话）。
   这个过程需要仔细处理指针以避免内存泄漏和悬挂指针等问题，在实际应用中，建议使用智能指针或其他内存管理工具来帮助管理动态分配的内存。