Это то, как я должен понимать, что такое многоходовое дерево?

В настоящее время я собираюсь реализовать многоходовое дерево на С++, но я до сих пор не уверен, что именно они собой представляют. Я прочитал несколько документов, но я все еще в замешательстве из-за отсутствия изображений или визуализации.

Допустим, я хочу трехстороннее дерево, согласно онлайн-заметкам, это означает, что каждый узел может иметь не более 3-1 = 2 элемента, и каждый узел может иметь не более 3 дочерних элементов. Ниже я нарисовал несколько деревьев, которые я не уверен, являются ли они трехсторонними деревьями, может ли кто-нибудь проверить, правильно ли я это понимаю? Спасибо!

Кроме того, если у меня есть двухстороннее дерево, означает ли это, что у меня также есть двоичное дерево? О.о? введите здесь описание изображения


c++ tree multiway-tree
person Belphegor    schedule 09.04.2015    source источник
comment
Похоже, ваша диаграмма № 2 представляет собой связанный список.   -  person Thomas Matthews    schedule 10.04.2015
comment
Я оставил поля пустыми, потому что я думаю, что нам не нужно иметь m дочерних элементов или m-1 элементов на узел, верно?   -  person Belphegor    schedule 10.04.2015
comment
@ThomasMatthews, да, можно сказать, что это связанный список, но вопрос в том, является ли он также трехсторонним деревом.   -  person user253751    schedule 10.04.2015

Ответы (1)


arrow_upward
1
arrow_downward

Мое понимание многопутевого дерева — это количество поддеревьев, которые можно пройти из одного узла.

           +---+  
           | D |
           +---+  
             ^  
             |  
             |  
+---+     +------+     +---+  
| A | <-- | Root | --> | B |  
+---+     +------+     +---+
             |  
             |  
             V
           +---+  
           | C |  
           +---+

На приведенной выше диаграмме показано дерево с несколькими путями, потому что корень имеет более 1 дочернего элемента.

Обычно 2 дочерних узла на узел (кроме конечных узлов) указывают на бинарные деревья.
Существует множество различных видов бинарных деревьев.

См. также B-Tree и B*Tree.

Редактировать 1:
Другое представление:

 +------------------------+  
 |          Root          +
 +------------------------+  
  |       |       |       |  
  V       V       V       V  
+---+   +---+   +---+   +---+  
| A |   | B |   | C |   | D |  
+---+   +---+   +---+   +---+
person Thomas Matthews    schedule 10.04.2015
comment
Ясно, значит, я прав, думая, что с m-way tree мне не нужно максимально использовать все доступные места. - person Belphegor; 10.04.2015