0

我很难理解取自Representing Rooted Trees的以下段落。它基本上展示了两种表示树的方法。G & T 对我来说有点清楚，但另一个对我来说不是很清楚，它显示了类定义。

  • G&T 选项：每个节点都有 3 个引用：项目、父节点、子节点。子节点的单一引用必须引用一个列表（因此节点可以根据需要拥有尽可能多的子节点）。

  • 另一种选择是直接链接兄弟姐妹。例如

    class SibTreeNode {
 Object item;
 SibTreeNode parent;
 SibTreeNode firstChild; // Left-most child.
 SibTreeNode nextSibling;
}

public class SibTree {
  SibTreeNode root;
  int size; // Number of nodes in the tree.
}

视频中的作者还声称（大约 18 分钟）第二种方法需要更少的内存。有人可以帮助我理解类定义以及与第一种方法相比如何需要更少的内存吗？

4

1 回答 1

1

第二个选项只是一个侵入式单链表。侵入式单链表占用更少的内存，因为您不需要从列表节点指向节点内容的指针。

使用外部列表查看 G&T 选项的布局：

class ListNode {
    SibTreeNode* object;
    ListNode* nextElement;
};

class SibTreeNode {
    Object* item;
    SibTreeNode* parent;
    ListNode* childList;
};

每个 SibTreeNode 元素有 5 个指针，而不是 4 个。

于 2013-02-21T12:33:25.147 回答