Как определить, завершено ли двоичное дерево?

Чтобы дерево было завершено

высота (слева) == высота (справа) или высота (слева) == 1+height (справа)

    bool isComplete (struct Node* root){
    if(root==NULL)
    return true;                  // Recur for left and right subtree 
    bool flag=false;
    int option1=height(root->left);
    int option2=height(root->right);
    if(option1==option2||option1==option2+1)
    flag=true;
    return flag&&isComplete(root->left)&&isComplete(root->right);
    }

bool isComplete (struct Node* root){
    if(root==NULL)
    return true;                  // Recur for left and right subtree 
    bool flag=false;
    int option1=height(root->left);
    int option2=height(root->right);
    if(option1==option2||option1==option2+1)
    flag=true;
    return flag&&isComplete(root->left)&&isComplete(root->right);
    }

рассмотрите как корректный ответ, если Вы нашли полезным.

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

• Является ли поддерево полным

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

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

Аналогично:

height(t) = if (t==NULL) then 0 else 1+max(height(t.left),height(t.right))

У вас есть:

perfect(t) = if (t==NULL) then 0 else { 
                  let h=perfect(t.left)
                  if (h != -1 && h==perfect(t.right)) then 1+h else -1
             }

Где perfect (t) возвращает -1, если листья не имеют одинаковой глубины или любой узел имеет только один дочерний элемент ; в противном случае возвращается высота.

Изменить: это для "complete" = "Идеальное двоичное дерево - это полное двоичное дерево, в котором все листья находятся на одной глубине или на одном уровне. 1 ( Это также неоднозначно называют полным двоичным деревом.) "( Википедия ).

Здесь ' sa рекурсивная проверка: «Полное двоичное дерево - это двоичное дерево, в котором каждый уровень, кроме, возможно, последнего, полностью заполнен, а все узлы расположены как можно дальше слева». Он возвращает (-1, false), если дерево не завершено, в противном случае (height, full), если оно есть, с full == true, если оно идеально.

complete(t) = if (t==NULL) then (0,true) else { 
                  let (hl,fl)=complete(t.left)
                  let (hr,fr)=complete(t.right)                      
                  if (fl && hl==hr) then (1+h,fr)
                  else if (fr && hl==hr+1) then (1+h,false)
                  else (-1,false)
              }

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

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);
}

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

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

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 ())
        сравнить все флаги узлов [] ... если все true global_flag = true else global_flag = false.
     4. Если global_flag = true перейти на следующий уровень в первом обходе в ширину else terminate

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

//Helper function

int depth (struct tree * n)
{
   int ld,rd;

   if (n == NULL) return 0;

   ld=depth(n->left);
   ld=depth(n->right);

   if (ld>rd)
      return (1+ld);
   else
      return (1+rd);

}


//Core function

int isComplete (struct tree * n)
{
   int ld,rd;

   if (n == NULL) return TRUE;

   ld=depth(n->left);
   rd=depth(n->right);

   return(ld==rd && isComplete(n->left) && isComplete(n->right));

}