c - ANSI C 中的树数据结构

<分区>

如何在 ANSI C (*) 中实现树？

struct Element
{
    ...
    struct Element *pChildElements; // Use dynamic array?
};

(*) 我指的是树的最一般定义(不是二叉树)。

最佳答案

最佳实现方法(有很多)可能取决于特定的应用程序。例如，在某些应用程序中，将子节点或子指针存储在数组中可能更可取，而在其他应用程序中则完全没有必要。您真的需要对 child 进行基于索引的随机访问吗？如果是这样，请使用数组。

实现任意树的经典非数组方法是在每个节点中存储两个指针:一个指向第一个 child 的指针和一个指向下一个兄弟的指针.

struct Element
{
  ...
  struct Element *p_first_child;
  struct Element *p_next_sibling;
};

即每个节点本质上都包含一个指向其子节点的列表的指针。

例如，一个有3个子节点的节点由以下链接结构表示

    Node
     |
  (first child)
     |
     V
   Child1 --(next sibling)--> Child2 --(next sibling)--> Child3

此实现可以通过在每个节点中仅使用两个指针来存储任何树。不需要额外的阵列。由于子节点存储在列表中，因此只能以顺序方式访问它们。

从这种方法中得出的有趣观察是，生成的数据结构可以被认为是一棵二叉树，即任意树可以用等价表示二叉树。

关于c - ANSI C 中的树数据结构，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/11942841/

相关文章：

C - for 循环初始值设定项中的 while 运算符