Как определить, является ли двоичное дерево полным?

Question

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

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

Answer 1

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

Level 0:    a  
Level 1:  b   c  
Level 2: d e f g  

• Мы используем ширину первого обхода.

• Для каждого поставленного в очередь элемента в очереди мы должны сделать три проверки по порядку:

  1. Если есть единственный ребенок или нет ребенка, прекратите обучение; иначе проверьте 2.
  2. Если существуют оба потомка, установите глобальный флаг = true.
     1. Установить флаги для каждого узла в очереди как true: flag [b] = flag [c] = true.
     2. Проверьте для каждой записи, есть ли у них n правого потомка n, затем установите флажки или сбросьте их на false.
     3. (удаление из очереди) if (queue_empty ())
        сравнить все флаги узлов [] ... если все верно global_flag = true, иначе global_flag = false.
     4. Если global_flag = true, переходите к следующему уровню в ширину. Первый обход, иначе завершается

Преимущество: все дерево не может быть пройдено
Накладные расходы: ведение записей флагов

Answer 2

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

bool IsLeftComplete(tree)
{

  if (!tree.Right.IsEmpty && tree.Left.IsEmpty)
    //tree has a right child but no left child, therefore is not a heap
    return false;    

  if (tree.Right.IsEmpty && tree.Left.IsEmpty)  
    //no sub-trees, thus is leaf node. All leaves are complete
    return true;

  //this level is left complete, check levels below
  return IsLeftComplete(tree.Left) && IsLeftComplete(tree.Right);
}

Answer 3

Вы можете объединить три фрагмента информации из поддеревьев:

• Завершено ли поддерево

• Максимальная высота

• Минимальная высота (равна максимальной высоте или максимальной высоте - 1)