Это то, как я должен понимать, что такое многоходовое дерево?
В настоящее время я собираюсь реализовать многоцелевое дерево в C ++, но я все еще не уверен, что именно они. Я прочитал несколько документов, но я все еще в замешательстве из-за отсутствия картинок или визуализации.
Допустим, я хочу трехстороннее дерево, согласно онлайн-заметкам в Интернете, это означает, что каждый узел может иметь не более 3-1 = 2 элементов, а каждый узел может иметь не более 3 дочерних элементов. Ниже я нарисовал несколько деревьев, в которых я не уверен, являются ли они деревьями с тремя путями, может кто-нибудь проверить, правильно ли я это понимаю? Спасибо!
Кроме того, если у меня есть двухстороннее дерево, значит ли это, что у меня также есть двоичное дерево? O.o?
Решение
Мое понимание многопотокового дерева — это число поддеревьев, которые можно пройти из одного узла.
+---+
| D |
+---+
^
|
|
+---+ +------+ +---+
| A | <-- | Root | --> | B |
+---+ +------+ +---+
|
|
V
+---+
| C |
+---+
На приведенной выше диаграмме показано многоходовое дерево, поскольку корень имеет более 1 дочернего элемента.
Обычно 2 дочерних элемента на узел (кроме листовых узлов) указывают на двоичные деревья.
Существует много разных видов бинарных деревьев.
Смотрите также B-Tree и B * Деревья.
Изменить 1:
Другой вид:
+------------------------+
| Root +
+------------------------+
| | | |
V V V V
+---+ +---+ +---+ +---+
| A | | B | | C | | D |
+---+ +---+ +---+ +---+
Другие решения