Имя структуры данных, в которой каждый узел имеет [0, n] известных детей и [0, 1] неизвестных родителей?

Question

Как всегда, диаграмма объясняет это гораздо лучше, чем слова:

Узел может иметь или не иметь родителя. У узла может быть только один родитель, поэтому [0, 1] родители. Он не хранит никакой информации о родителе, поэтому узел не знает, есть ли у него родитель.

Узел может иметь или не иметь детей. У узла может быть столько детей, сколько он хочет, поэтому [0, n] детей. Он хранит информацию о том, как добраться до каждого из его дочерних узлов.

Есть ли конкретный термин для этого типа структуры данных? По сути, это связанный список с несколькими дочерними элементами.

Answer 1

Это называется лес , то есть коллекция деревьев . (В дереве есть только один узел без родителей, который называется root .)

Лес совсем не похож на связанный список; Прежде всего, потому что потенциально есть несколько узлов без родителей, это коллекция; и, во-вторых, поскольку у узла может быть несколько потомков, обход дерева совершенно отличается от обхода списка, выращивание дерева может происходить разными способами, и в целом деревья предлагают много интересных опций, а списки - нет.

P.S. Диаграмма в вопросе показывает одно дерево. В тексте вопроса не говорится, что существует только один узел без родителей, и поэтому описанная структура данных является лесом. Если гарантируется, что не более одного узла не имеет родителей, тогда структура данных является деревом.