Это полное двоичное дерево?

Question

Вот бинарное дерево, о котором идет речь. Листья a, b, c, d и края помечены 0 или 1.

    .
   / \
  a   .
     / \
    b   .
       / \
      c   d

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

Если у узла есть дочерний узел, который является листом, не считается ли он дочерним узлом?

Answer 1

Вы путаете идеальное двоичное дерево с полным двоичным деревом. Идеальное двоичное дерево - это полное двоичное дерево со всеми конечными узлами на одном уровне. Так что да, картинка представляет собой полное двоичное дерево.

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

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

Answer 2

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