Коллекции, часть 6: Деревья

Вот мы и добрались до деревьев – одного из самых важных и сложных типов коллекций.

Готовых классов коллекций-деревьев среди разных языков я не нашел (может, плохо искал), но во-первых, они присутствуют как внутренние реализации других коллекций, а во-вторых, реализацию можно написать самостоятельно.

Итак, дерево – это развитие идеи связного списка. Если в списке каждый элемент имеет только одного "потомка", то в дереве каждый элемент может иметь несколько "потомков", которые существуют параллельно друг другу. Они не связаны друг с другом, но связаны со своим "родителем". Каждый из этих потомков может быть родителем своих потомков, и т.д.

То есть структура данных, начиная с первого элемента, ветвится на несколько элементов, далее каждый из них может опять ветвиться, то есть – получается настоящее дерево, но обычно его рисуют в перевёрнутом виде: