时间戳

首页 > 解决方案 > 如何实现具有多个根的树数据结构

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

问题描述

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

我的任务需要什么：

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

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

显示具有多个根的树的图像

标签： data-structurestree

解决方案

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

您不需要多个根的数据结构。您需要一个数据结构，其中节点是多功能的，可以代表一本书、一章、一节等，而无需复制代码。OOP 非常适合（继承）。

这个想法是定义一个类，它具有所有对象共有的所有共同特征。例如，一本书、一章、一节……都有一个名字，他们都可以有“孩子”。树的迭代可以作为这个类的一个方法来实现。

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

这是执行此操作的众多方法之一。我在这里使用 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();

推荐阅读