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

Question

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

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

Answer 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 
      } 

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

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

Рекурсивная проверка: «Полное двоичное дерево - это двоичное дерево, в котором каждый уровень, за исключением, возможно, последнего, полностью заполнен, а все узлы как можно дальше.». Он возвращает (-1, false), если дерево не является полным, иначе (высота, полная), если оно есть, с полным значением 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) 
       } 

Answer 2

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

• ли поддерево полный

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

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

Answer 3

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

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 4

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

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

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

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

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

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

Answer 5

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

Answer 6

//Author : Sagar T.U, PESIT 
//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)); 

} 

Answer 7

Простейшая процедура:

1. Поиск глубина дерева (простой алгоритм).
2. Подсчитайте количество узлов в дереве (путем перемещения и увеличения счетчика на один при посещении любого узла).
3. Для полного двоичного дерева уровня d Число узлов равно pow (2, d + 1) -1.

Если условие удовлетворяет дереву, это полное двоичное дерево, иначе нет.

Это простой алгоритм и превращение его в рабочий код не должно быть проблемой, если вы достаточно хороши.

Answer 8

int height (node* tree, int *max, int *min) { 

    int lh = 0 , rh = 0 ; 
    if (tree == NULL) 
    return 0; 
    lh = height (tree->left,max,min) ; 
    rh = height (tree->right,max,min) ; 
    *max = ((lh>rh) ? lh : rh) + 1 ; 
    *min = ((lh>rh) ? rh : lh) + 1 ; 
    return *max ; 
} 

void isCompleteUtil (node* tree, int height, int* finish, int *complete) { 
    int lh, rh ; 
    if (tree == NULL) 
    return ; 
    if (height == 2) { 
    if (*finish) { 
     if (!*complete) 
     return; 
     if (tree->left || tree->right) 
     *complete = 0 ; 
     return ; 
    } 
    if (tree->left == NULL && tree->right != NULL) { 
     *complete = 0 ; 
     *finish = 1 ; 
    } 
    else if (tree->left == NULL && tree->right == NULL) 
     *finish = 1 ; 
    return ; 
    } 
    isCompleteUtil (tree->left, height-1, finish, complete) ; 
    isCompleteUtil (tree->right, height-1, finish, complete) ; 
} 

int isComplete (node* tree) { 
    int max, min, finish=0, complete = 1 ; 
    height (tree, &max, &min) ; 
    if ((max-min) >= 2) 
    return 0 ; 
    isCompleteUtil (tree, max, &finish, &complete) ; 
    return complete ; 
} 

Answer 9

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

enum CompleteType 
{ 
    kNotComplete = 0, 
    kComplete = 1, // Complete but not full 
    kFull = 2, 
    kEmpty = 3 
}; 

CompleteType isTreeComplete(Node* node, int* height) 
{ 
    if (node == NULL) 
    { 
     *height = 0; 
     return kEmpty; 
    } 

    int leftHeight, rightHeight; 

    CompleteType leftCompleteType = isTreeComplete(node->left, &leftHeight); 
    CompleteType rightCompleteType = isTreeComplete(node->right, &rightHeight); 

    *height = max(leftHeight, rightHeight) + 1; 

    // Straight forwardly treat all possible cases 
    if (leftCompleteType == kComplete && 
     rightCompleteType == kEmpty && 
     leftHeight == rightHeight + 1) 
     return kComplete; 

    if (leftCompleteType == Full) 
    { 
     if (rightCompleteType == kEmpty && leftHeight == rightHeight + 1) 
      return kComplete; 
     if (leftHeight == rightHeight) 
     { 
      if (rightCompleteType == kComplete) 
       return kComplete; 
      if (rightCompleteType == kFull) 
       return kFull; 
     } 
    } 

    if (leftCompleteType == kEmpty && rightCompleteType == kEmpty) 
     return kFull; 

    return kNotComplete; 
} 

bool isTreeComplete(Node* node) 
{ 
    int height; 
    return (isTreeComplete(node, &height) != kNotComplete); 
} 

Answer 10

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

1. Магазин элемент данные из узлов, встречающихся в векторе
2. Если узел равен NULL, а затем сохранить специальный номер (INT_MIN)
3. Следите за последние не- null node visited - lastentry
4. Теперь перемещайте вектор до конца. Если вы когда-либо сталкиваетесь с INT_MIN, то дерево не завершено. Иначе это полное двоичное дерево.

Вот с ++ код:

Мое дерево узел:

struct node{ 
    int data; 
    node *left, *right; 
}; 

void checkcomplete(){//checks whether a tree is complete or not by performing level order traversal 
    node *curr = root; 
    queue<node *> Q; 
    vector<int> arr; 
    int lastentry = 0; 
    Q.push(curr); 
    int currlevel = 1, nextlevel = 0; 
    while(currlevel){ 
     node *temp = Q.front(); 
     Q.pop(); 
     currlevel--; 
     if(temp){ 
      arr.push_back(temp->data); 
      lastentry = arr.size(); 
      Q.push(temp->left); 
      Q.push(temp->right); 
      nextlevel += 2; 
     }else 
      arr.push_back(INT_MIN); 
     if(!currlevel){ 
      currlevel = nextlevel; 
      nextlevel = 0; 
     } 
    } 
    int flag = 0; 
    for(int i = 0; i<lastentry && !flag; i++){ 
     if(arr[i] == INT_MIN){ 
      cout<<"Not a complete binary tree"<<endl; 
      flag = 1; 
     } 
    } 
    if(!flag) 
     cout<<"Complete binary tree\n"; 
} 

Answer 11

private static boolean isCompleteBinaryTree(TreeNode root) { 

if (root == null) { 
    return false; 
} else { 
    boolean completeFlag = false; 
    List<TreeNode> list = new ArrayList<TreeNode>(); 
    list.add(root); 
    while (!list.isEmpty()) { 
     TreeNode element = list.remove(0); 
     if (element.left != null) { 
      if (completeFlag) { 
       return false; 
      } 
     list.add(element.left); 
     } else { 
      completeFlag = true; 
     } 
     if (element.right != null) { 
      if (completeFlag) { 
       return false; 
      } 
     list.add(element.right); 
     } else { 
      completeFlag = true; 
     } 
    } 
     return true; 
    } 
} 

Ссылка: Проверьте ссылку для детального объяснения http://www.geeksforgeeks.org/check-if-a-given-binary-tree-is-complete-tree-or-not/

Answer 12

Спасибо за @ Псевдокод Джонатана Граэля. Я реализовал его на Java. Я протестировал его против итеративной версии. Отлично работает!

public static boolean isCompleteBinaryTreeRec(TreeNode root){ 
//  Pair notComplete = new Pair(-1, false); 
//  return !isCompleteBinaryTreeSubRec(root).equalsTo(notComplete); 
    return isCompleteBinaryTreeSubRec(root).height != -1; 
} 

public static boolean isPerfectBinaryTreeRec(TreeNode root){ 
    return isCompleteBinaryTreeSubRec(root).isFull; 
} 

public static Pair isCompleteBinaryTreeSubRec(TreeNode root){ 
    if(root == null){ 
     return new Pair(0, true); 
    } 

    Pair left = isCompleteBinaryTreeSubRec(root.left); 
    Pair right = isCompleteBinaryTreeSubRec(root.right); 

    if(left.isFull && left.height==right.height){ 
     return new Pair(1+left.height, right.isFull); 
    } 

    if(right.isFull && left.height==right.height+1){ 
     return new Pair(1+left.height, false); 
    } 

    return new Pair(-1, false); 
} 

private static class Pair{ 
    int height;   
    boolean isFull;  

    public Pair(int height, boolean isFull) { 
     this.height = height; 
     this.isFull = isFull; 
    } 

    public boolean equalsTo(Pair obj){ 
     return this.height==obj.height && this.isFull==obj.isFull; 
    } 
} 

Answer 13

Вот код C для проверки, если бинарное дерево является полным:

struct node 
{ 
    int data; 
    struct node * left; 
    struct node * right; 
}; 
int flag; 
int isComplete(struct node *root, int depth) 
{ 
    int ld, rd; 
    if (root==NULL) return depth; 
    else 
    { 
     ld = isComplete(root->left,depth+1); 
     rd = isComplete(root->right, depth+1); 
     if (ld==-1 || rd==-1) return -1; 
     else if (ld==rd) return ld; 
     else if (ld==rd-1 && flag==0) 
     { 
      flag=1; 
      return rd; 
     } 
     else return -1; 
    } 
} 

Путь это работает:

• Если глубина левого поддерева такой же, как глубина правого поддерева, он возвращает глубину вверх по иерархии.

• если глубина левого поддерева больше, чем глубина правого поддерева, она возвращает глубину правого поддерева вверх по иерархии и включает флаг.

• Если он обнаружил, что глубина левого поддерева и правого поддерева и флаг уже установлены, он возвращает -1 вверх по иерархии.

• В конце, если функция возвращает -1, это не полное поддерево, иначе возвращаемое значение будет минимальной глубиной дерева.