Jak ustalić, czy drzewo binarne jest kompletne?

Question

Kompletne drzewo binarne jest zdefiniowane jako drzewo binarne, w którym każdy poziom, z wyjątkiem być może najgłębszej, jest całkowicie wypełniony. Na najgłębszym poziomie wszystkie węzły muszą być jak najdalej od lewej.

Wydaje mi się, że prosty algorytm rekurencyjny będzie w stanie stwierdzić, czy dane drzewo binarne jest kompletne, ale nie potrafię tego rozgryźć.

Answer 1

podobne do:

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

Masz:

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 
      } 

Gdzie idealny (t) zwraca -1 gdy liście nie są na tej samej głębokości, lub każdy węzeł ma tylko jeden dziecko; w przeciwnym razie zwraca wysokość.

Edytuj: jest to dla "complete" = "Idealne drzewo binarne jest pełnym drzewem binarnym, w którym wszystkie liście mają tę samą głębokość lub ten sam poziom: 1 (Jest to niejednoznacznie zwane również pełnym drzewem binarnym)." (Wikipedia).

Oto rekursywna kontrola dla: "Kompletne drzewo binarne jest drzewem binarnym, w którym każdy poziom, z wyjątkiem być może ostatnim, jest całkowicie wypełniony, a wszystkie węzły są jak najdalej.". Zwraca (-1, fałsz), jeśli drzewo nie jest kompletne, w przeciwnym razie (wysokość, pełne), jeśli jest, z pełnym == prawdą, to jest idealne.

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

Można połączyć trzy informacje z poddrzew:

• czy poddrzewo jest kompletna

• Maksymalna wysokość

• Minimalna wysokość (równa do maksymalnej wysokość lub maksymalna wysokość - 1)

Answer 3

Można stwierdzić, czy dane drzewo binarne jest pełnowymiarowym drzewem binarnym - lepiej znanym jako binarna kupa, zapewniając, że każdy węzeł z odpowiednim dzieckiem ma również lewe dziecko. Zobacz poniżej:

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

Może istnieć jeden możliwy algorytm, który moim zdaniem rozwiąże ten problem. Rozważmy drzewo:

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

• Zatrudniamy Szerokość pierwszego przechodzenie.

• Dla każdego skolejkowany elementu w kolejce musimy zrobić trzy kontrole w kolejności:

  1. Jeśli istnieje pojedynczy dziecko lub dziecko nie kończą; w przeciwnym razie sprawdź 2.
  2. Jeśli istnieją dzieci, ustaw globalną flagę = true.
     1. Ustaw flagi dla każdego węzła w kolejce jako true: flag [b] = flag [c] = true.
     2. Sprawdź, czy dla każdego wpisu pozostawiono n prawe dziecko n, a następnie ustaw flagi lub zresetuj je do wartości false.
     3. (Dequeue) jeśli (queue_empty())
        porównać wszystkie flagi węzłów [] ... jeśli wszystkie true global_flag = true else global_flag = false.
     4. Jeśli global_flag = true przejdź do przejść do następnego poziomu w szerokości pierwszy przejścia jeszcze zakończyć

Zaleta: Całe drzewo nie może zostać wykonany ruch
podwieszone: utrzymanie pozycji flag

Answer 5

Możesz to zrobić rekurencyjnie, porównując wysokości dzieci w każdym węźle. Może być co najwyżej jeden węzeł, w którym lewe dziecko ma wysokość dokładnie o jeden większą niż właściwe dziecko; wszystkie pozostałe węzły muszą być idealnie zrównoważone.

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

Najprostszy procedura jest:

1. głębokość Znajdują drzewa (prostego algorytmu).
2. Policz liczbę węzłów w drzewie (przechodząc i zwiększając licznik o jeden podczas odwiedzania dowolnego węzła).
3. Dla pełnego drzewa binarnego poziomu d liczba węzłów równa się pow (2, d + 1) -1.

Jeśli warunek spełni drzewo, jest to pełne drzewo binarne, w przeciwnym razie nie.

To prosty algorytm i przekształcenie go w działający kod nie powinien stanowić problemu, jeśli jesteś wystarczająco dobrym programistą.

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

Poniższy kod po prostu traktuje wszystkie możliwe przypadki. Wysokość drzewa jest uzyskiwana po drodze, aby uniknąć kolejnej rekursji.

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

Możesz również rozwiązać ten problem, korzystając z przejścia do kolejnego poziomu. Procedura jest następująca:

1. Store element danych z węzłów występujących w wektorze
2. Jeśli węzeł jest NULL, a następnie przechowywać specjalny numer (INT_MIN)
3. Śledzić ostatni nie- węzeł zerowy odwiedzony - lastentry
4. Teraz przemierzaj wektor do zera. Jeśli kiedykolwiek napotkasz INT_MIN, to drzewo nie jest kompletne. Inaczej jest to pełne drzewo binarne.

Oto kod C++:

Mój węzeł drzewa jest:

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

referencyjny: Sprawdź na poniższy link do szczegółowego wyjaśnienia http://www.geeksforgeeks.org/check-if-a-given-binary-tree-is-complete-tree-or-not/

Answer 12

Dzięki za @Jonathan Graehl pseudo kod. Zaimplementowałem to w Javie. Przetestowałem to na iteracyjnej wersji. To działa jak urok!

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

Oto kod C do sprawdzania, czy drzewo binarne jest kompletna:

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

Jak to działa jest:

• Jeśli głębokość lewym poddrzewie jest taka sama jak głębokość prawego poddrzewo, zwraca głębię w górę dzierżawy.

• jeśli głębokość lewego poddrzewa jest większa niż głębokość prawego poddrzewa, zwraca głębokość prawego poddrzewa w górę hirarchii i włącza flagę.

• Jeśli wykryje, że głębokość lewego poddrzewa i prawego poddrzewa i flagi jest już ustawiona, zwraca -1 w górę hierarchii.

• W końcu, jeśli funkcja zwraca -1, nie jest to pełne poddrzewo, w przeciwnym razie zwrócona wartość jest minimalną głębokością drzewa.