Разница между "полным двоичным деревом","строгим двоичным деревом", "полным двоичным деревом"?

идеальный:

       x
     /   \
    /     \
   x       x
  / \     / \
 x   x   x   x
/ \ / \ / \ / \
x x x x x x x x

Complete:

       x
     /   \
    /     \
   x       x
  / \     / \
 x   x   x   x
/ \ /
x x x

строго:

       x
     /   \
    /     \
   x       x
  / \ 
 x   x 
    / \
    x x 

существует разница между строгим и полным двоичным деревом.

1) ПОЛНОЕ ДВОИЧНОЕ ДЕРЕВО: двоичное дерево высотой h, содержащее ровно (2^h)-1 элементов, называется полным бинарное дерево. (Ref: Pg 427,структуры данных, алгоритмы и приложения в C++ [Ун], второе издание, С. Сахни).

или

в полном двоичном дереве каждый узел имеет ровно 0 или 2 дочерних элемента и все листья узлы находятся на одном уровне.

Например: ниже приводится полное двоичное дерево:

          18
       /      \   
     15       30    
    /  \     /   \   
  40    50  100  40 

2) СТРОГОЕ ДВОИЧНОЕ ДЕРЕВО: каждый узел имеет ровно 0 или 2 детей.

например: ниже приводится строгое двоичное дерево:

         18
       /     \   
     15       30    
    /  \          
  40    50

Я думаю, что нет путаницы в определении полного двоичного дерева, но для полноты сообщения я хотел бы рассказать, что такое полное двоичное дерево есть.

3) ПОЛНОЕ ДВОИЧНОЕ ДЕРЕВО: двоичное дерево является полным двоичным деревом, если все уровни полностью заполнены, за исключением, возможно, последнего уровня, и последний уровень имеет все ключи как можно левее.

Например: ниже приводится полное двоичное дерево:

           18
       /       \  
     15         30  
    /  \        /  \
  40    50    100   40
 /  \   /
8   7  9 

Примечание: следующее также является полным двоичным деревом:

         18
       /     \   
     15       30    
    /  \     /   \   
  40    50  100  40 

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

хотя этот пост имеет принятый ответ и является хорошим, я все еще был в замешательстве и хотел бы добавить еще несколько разъяснений относительно разницы между этими терминами.

(1) ПОЛНОЕ ДВОИЧНОЕ ДЕРЕВО - полное двоичное дерево-это двоичное дерево, в котором каждый узел, кроме листьев, имеет два дочерних элемента.Это тоже называется строго бинарное дерево.

приведенные выше два являются примерами полного или строго двоичного дерева.

(2) ПОЛНОЕ ДВОИЧНОЕ ДЕРЕВО - теперь определение полного двоичного дерева довольно неоднозначно, оно гласит : - полное двоичное дерево-это двоичное дерево, в котором каждый уровень,кроме, возможно, последнего, полностью заполнен, и все узлы как можно дальше слева. It может иметь от 1 до 2h узлов, как можно дальше влево, на последнем уровне h

обратите внимание на строки курсивом.

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

ПОЧТИ ПОЛНОЕ ДВОИЧНОЕ ДЕРЕВО - когда исключение в определении полного двоичного дерева выполняется, то оно называется почти полным двоичным деревом или почти полным двоичным деревом . Это просто тип полного двоичного дерева, но для того, чтобы сделать его более однозначным, необходимо отдельное определение.

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

заключая из ответов выше, вот точная разница между полными / строго, полными и совершенными бинарными деревьями

1. полное / строго двоичное дерево : - каждый узел, кроме конечных узлов, имеет двух детей

2. полное бинарное дерево : - каждый уровень, кроме последнего уровня, полностью заполнен,и все узлы остаются оправданными.

3. идеальное бинарное дерево :- каждый узел, кроме конечных узлов, имеет два дочерних элемента, и каждый уровень (последний уровень тоже) полностью заполнен.

рассмотрим двоичное дерево, узлы которого рисуются в виде дерева. Теперь начинать нумерацию узлов сверху вниз и слева направо. Полное дерево имеет следующие свойства:

Если N имеет дочерние узлы, то все узлы, пронумерованные менее n, имеют два дочерних узла.

Если у n есть один дочерний элемент, он должен быть левым дочерним элементом, а все узлы меньше n имеют два дочерних элемента. Кроме того, ни один узел с номером больше n не имеет потомков.

Если n не имеет потомков, то узел не пронумерован больше чем у n есть дети.

полное двоичное дерево может быть использовано для представления кучи. Он может быть легко представлен в непрерывной памяти без пробелов (т. е. все элементы массива используются за исключением любого пространства, которое может существовать в конце).

полное двоичное дерево-это полное двоичное дерево, но обратное невозможно, и если глубина двоичного файла равна n, то нет. узлов в полном двоичном дереве равно ( 2^n-1 ). Это не обязательно в двоичном дереве, что у него есть два дочерних, но в полном двоичном это каждый узел не имеют или два дочерних.

чтобы начать с основ, очень важно понять само бинарное дерево, чтобы понять различные его типы.

дерево является двоичным деревом тогда и только тогда, когда: -

- он имеет корневой узел, который может не иметь дочерних узлов (0 childnodes, NULL tree)

–корневой узел может иметь 1 или 2 дочерних узла . Каждый такой узел образует абинарное дерево сам

–количество дочерних узлов может быть 0 ,1 ,2.......не более 2-х

- существует уникальный путь от корня до любого узла

пример :

        X
      /    \
     X      X
          /   \
         X     X

приходя к вашим запрошенным терминологиям:

двоичное дерево является полным двоичным деревом (высоты h, мы берем корневой узел как 0 ) тогда и только тогда, когда: -

уровень от 0 до h-1 представляет собой полное двоичное дерево высотой h-1

- один или несколько узлов уровня h-1 могут иметь 0 или 1 дочерний узел

если j, k-узлы на уровне h-1, то j имеет больше дочерних узлов, чем k, если и только если j находится слева от k, т. е. последний уровень (h) может отсутствовать в листовых узлах, однако присутствующие должны быть сдвинуты влево

пример :

                          X
                     /          \
                   /              \
                 /                  \
                X                    X
             /     \              /     \
           X       X             X       X
         /   \   /   \         /   \    /  \ 
        X    X   X   X        X    X    X   X 

двоичное дерево является строго двоичным деревом тогда и только тогда, когда: -

каждый узел имеет ровно два дочерних узла или узлов

пример :

         X
       /   \
      X     X 
          /   \
         X      X
        / \    / \ 
       X   X  X   X 

двоичное дерево является полным двоичным деревом тогда и только тогда, когда: -

каждый не листовой узел имеет ровно два ребенка узлы

все конечные узлы находятся на одном уровне

пример :

                          X
                     /          \
                   /              \
                 /                  \
                X                    X
             /     \              /     \
           X       X             X       X
         /   \   /   \         /   \    /  \ 
        X    X   X   X        X    X    X   X 
      /  \  / \ / \ / \      / \  / \  / \ / \ 
     X   X X  X X X X X     X  X  X X  X X X X 

вы также должны знать, что совершенное бинарное дерево?

бинарное дерево является идеальным бинарным деревом тогда и только тогда, когда: -

– это полное бинарное дерево

- все конечные узлы находятся на одном уровне

пример :

                          X
                     /          \
                   /              \
                 /                  \
                X                    X
             /     \              /     \
           X       X             X       X
         /   \   /   \         /   \    /  \ 
        X    X   X   X        X    X    X   X 
      /  \  / \ / \ / \      / \  / \  / \ / \ 
     X   X X  X X X X X     X  X  X X  X X X X 

Ну, я сожалею, что не могу размещать изображения, поскольку у меня нет репутации 10. Надеюсь, это поможет вам и другие!

в моем ограниченном опыте работы с бинарным деревом, я думаю:

1. Строго Двоичное Дерево: каждый узел, кроме конечных узлов, имеет два дочерних или только корневой узел.
2. Полное Двоичное Дерево: двоичное дерево H строго (или точно) содержащее 2^H -1 узлов, ясно, что каждый уровень имеет наибольшее количество узлов.
3. Полное Двоичное Дерево: это двоичное дерево, в котором каждый уровень, за исключением, возможно, последнего, полностью заполнен, и все узлы находятся как можно дальше слева.

Полное Двоичное Дерево - это двоичное дерево, в котором каждый узел имеет либо 0, либо двумя детьми. Другими словами, каждый узел дерева, кроме листьев, имеет ровно два потомка.

A полное бинарное дерево - это двоичное дерево, в котором каждый уровень дерева будет полностью заполнен, за исключением последнего уровня. Кроме того, на последнем уровне узлы должны быть прикреплены, начиная с самой левой позиции. полное двоичное дерево должно удовлетворять следующим требованиям условия:

• если a, b-два узла на уровне выше последнего уровня, то a имеет больше потомков, чем b, если и только если a находится слева от b.
• от корневого узла уровень выше последнего уровня представляет собой полное двоичное дерево высотой h-1.
• один или несколько узлов на последнем уровне могут иметь 0 или 1 детей.