c - ANSI C 中的树数据结构

Question

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

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

(*) 我的意思是树的最一般定义（不是二叉树）。

Answer 1

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

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

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

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

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

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

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

从这种方法得出的有趣观察结果是，可以将生成的数据结构视为二叉树，即任意树可以用等效的二叉树表示。

Answer 2

您在实现元素结构方面做得很好，但尝试使用二叉树或 B-Tree 来避免动态分配/释放。

您还将提供一组函数来插入/删除/初始化/搜索/排序/枚举树。

你可以想出一个名字，比如 AddToMyBTree（指向树头的指针，新元素）

如果您愿意，您可以提供比通常操作更多的功能。

我想我误解了你的问题：如果你想枚举你肯定会使用递归的树元素，你还需要用空对象终止子元素列表或添加额外的元素和子元素。

ProcessNode(element* pElement)
{
    element* pChild = pElement.pChildElements;

    // process the element here


    // then begin to process the child elements.
    while (pChild)
    {
        ProcessNode(pChild);
        pChild++;
    }
}

请记住，您可以将指针传递给处理元素的函数，以便该枚举器可以通用您的树。