如何实现具有多个根的树数据结构

Question

我需要实现一个树数据结构，它应该有多个根，而不仅仅是一个根。看看这个场景，假设我必须为“书籍内容”实现树数据结构。分别是“章节 > 章节 > 小节”等。主要问题是：这里有多个根，第 1 章、第 2 章、第 3 章等等。根节点肯定是从章节开始的，因为从那一层开始的内容类型和功能都是一样的。

我的任务要求：

多根树
节点在同一父级之间按水平排序
它是一棵非二叉树，意味着可以有任意数量的根节点和任意数量的子节点。

我有一个解决方案，但我认为这是一个混乱的方法。我做了一个 class 就像通常为树数据结构所做的那样。这个 class 是“SimpleTree”，它作为根节点用于单个章节。为了使多个根节点成为可能，我制作了另一个 class “TopWrapperForSimpleTree”。这个顶级包装器 class 有一个 Array 以便向其存储多个“SimpleTree”元素（基本上是多个根）。这里麻烦的部分是我必须复制“SimpleTree”的每个函数并为包装器 class 定义它。例如，“遍历函数”将遍历“SimpleTree”中的所有元素。但是现在我必须为“TopWrapperForSimpleTree”class 实现一个“遍历函数”，并且它必须循环遍历所有根，在每个根上调用遍历函数并连接结果。其他功能也是如此，例如查找节点、删除节点等。

总而言之，我需要一个可以有多个根的树数据结构。它也应该被订购。顺序很重要。

Image showing Tree with multiple roots

Answer 1

“多根树”不是树。当您将每一章视为一棵树时，那么章节的集合就是一片森林。但是您可以只添加一个根节点。 Chapters属于Book，Book就是根节点。

您不需要多个根的数据结构。您需要一个数据结构，其中节点为 multi-functional 并且可以表示一本书、一章、一节等，而无需重复代码。 OOP 非常适合（继承）。

我们的想法是定义一个 class，它具有所有 objects 所共有的所有共同特征。比如一本书、一章、一节……都有一个名字，它们都可以有“children”。树的迭代可以作为此 class.

的方法来实现

那么一本书就是这个基础的扩展 class：例如，一本书可以有一个作者属性。一个部分也可以是基础 class 的扩展，但可以有额外的属性页码。一个章节可以是一个部分的扩展，因为它也有页码，但可能另外还有一个章节号，...等

这是执行此操作的众多方法之一。我在这里使用 JavaScript，但它在其他 OOP 语言中的工作方式类似：

class Node {
    constructor(name) {
        this.name = name;
        this.children = [];
    }
    add(...children) {
        this.children.push(...children);
        return this;  // Return the instance, so method calls can be chained...
    }
    toString() {
        return this.name; 
    }
    * iter(depth=0) { 
        // A pre-order iteration through the whole tree that this node represents  
        yield [depth, this];
        for (let child of this.children) {
            yield * child.iter(depth+1);
        }
    }
    * iterWithout(depth=0) { 
        // A pre-order iteration through the whole tree that this node represents 
        // ...but excluding the node on which the original call is made: 
        for (let child of this.children) {
            yield [depth, child];
            yield * child.iterWithout(depth+1);
        }
    }
}

class Book extends Node {
    constructor(name, author) {
        super(name);
        this.author = author; // specific property for Book instance
    }
    toString() {
        return super.toString() + ", by " + this.author; 
    }
}

class Section extends Node {
    constructor(name, page) {
        super(name);
        this.page = page; // specific property for any section (also chapter)
    }
    toString() {
        return super.toString() + ", page " + this.page; 
    }
}

class Chapter extends Section {
    constructor(id, name, page) {
        super(name, page);
        this.id = id; // specific property for Chapter instance
    }
    toString() {
        return "Chapter " + this.id + ". " + super.toString(); 
    }
}

// Illustration of how it could be used:
function main() { // Demo
    let book = new Book("The Perfect Theory", "Pedro G. Ferreira").add(
        new Chapter(1, "If a Person Falls Freely", 1).add(
            new Section("The Autumn of 1907", 1),
            new Section("The Article in the Yearbook", 4),
            new Section("Isaac Newton", 6),
            new Section("Gravity", 9),
        ),
        new Chapter(2, "The Most Valuable Discovery", 12),
        new Chapter(3, "Correct Mathematics, Abominable Physics", 28),
        new Chapter(4, "Collapsing Stars", 47)
    );
    for (let [depth, item] of book.iterWithout()) {
        console.log("  ".repeat(depth) + item.toString());
    }
}

main();

如何实现具有多个根的树数据结构

How to implement a Tree data structure with multiple roots

tree

data-structures