Làm thế nào để xác định liệu cây nhị phân có hoàn thành?

Question

Một cây nhị phân hoàn chỉnh được định nghĩa là cây nhị phân, trong đó mọi cấp độ, ngoại trừ có thể sâu nhất, được lấp đầy hoàn toàn. Ở mức độ sâu nhất, tất cả các nút phải càng xa càng tốt.

Tôi nghĩ rằng một thuật toán đệ quy đơn giản sẽ có thể cho biết liệu một cây nhị phân đã cho đã hoàn thành chưa, nhưng dường như tôi không thể hiểu được.

Answer 1

Tương tự như:

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

Bạn có:

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 
      } 

đâu hoàn hảo (t) trả về -1 nếu lá không phải là tất cả cùng một chiều sâu, hoặc bất kỳ nút chỉ có một đứa trẻ; ngược lại, nó trả về chiều cao.

Chỉnh sửa: đây là dành cho "hoàn thành" = "Cây nhị phân hoàn hảo là cây nhị phân đầy đủ, trong đó tất cả các lá ở cùng độ sâu hoặc cùng một cấp. 1 (Đây rõ ràng còn được gọi là cây nhị phân hoàn chỉnh.)" (Wikipedia).

Dưới đây là kiểm tra đệ quy cho: "Cây nhị phân hoàn chỉnh là cây nhị phân, trong đó mọi cấp, ngoại trừ có thể là cuối cùng, được điền đầy đủ và tất cả các nút càng xa càng tốt". Nó trả về (-1, false) nếu cây không hoàn thành, nếu không (chiều cao, đầy đủ) nếu nó là, với đầy đủ == true iff nó hoàn hảo.

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

Bạn có thể kết hợp ba mẩu thông tin từ subtrees:

• Cho dù cây con hoàn tất

• Chiều cao tối đa

• Chiều cao tối thiểu (tương đương với tối đa chiều cao hoặc chiều cao tối đa - 1)

Answer 3

Bạn có thể biết liệu cây nhị phân đã cho có phải là cây nhị phân bên trái hay không - tốt hơn được gọi là heap nhị phân bằng cách đảm bảo rằng mọi nút có con đúng cũng có con trái. Xem bên dưới

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

Có thể có một thuật toán có thể xảy ra mà tôi cảm thấy sẽ giải quyết được sự cố này. Xem xét cây:

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

• Chúng tôi sử dụng rộng traversal đầu tiên.

• Đối với mỗi phần tử enqueued trong hàng đợi chúng ta phải làm ba kiểm tra theo thứ tự:

  1. Nếu có một con duy nhất hoặc không có con chấm dứt; khác, hãy kiểm tra 2.
  2. Nếu có cả hai trẻ em, hãy đặt cờ chung = true.
     1. Đặt cờ cho mỗi nút trong hàng đợi là đúng: cờ [b] = cờ [c] = true.
     2. Kiểm tra từng mục nhập nếu chúng đã để lại đúng n n rồi đặt cờ hoặc đặt lại thành sai.
     3. (Dequeue) nếu (queue_empty())
        so sánh tất cả các cờ nút [] ... nếu tất cả global_flag = true khác global_flag = false.
     4. Nếu global_flag = true đi cho tiến hành với cấp độ tiếp theo trong bề rộng traversal đầu tiên khác chấm dứt

Ưu điểm: cây toàn bộ có thể không được đi qua
Overhead: duy trì mục cờ

Answer 5

Bạn có thể làm điều đó một cách đệ quy bằng cách so sánh chiều cao của con của mỗi nút. Có thể có tối đa một nút trong đó con trái có chiều cao chính xác lớn hơn một đứa con đúng; tất cả các nút khác phải được cân bằng hoàn hảo.

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

Thủ tục đơn giản nhất là:

1. Find độ sâu của cây (thuật toán đơn giản).
2. Đếm số lượng nút trong một cây (bằng cách duyệt ngang và tăng bộ đếm bằng cách truy cập bất kỳ nút nào).
3. Đối với cây nhị phân hoàn chỉnh cấp d số lượng nút bằng pow (2, d + 1) -1.

Nếu điều kiện thỏa mãn cây, là cây nhị phân hoàn chỉnh, nếu không thì không.

Đó là một thuật toán đơn giản và biến nó thành mã hoạt động không phải là vấn đề nếu bạn là người lập trình đủ tốt.

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

Mã sau chỉ xử lý mọi trường hợp có thể. Chiều cao cây thu được dọc theo con đường để tránh đệ quy khác.

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

Bạn cũng có thể giải quyết vấn đề này bằng cách sử dụng tính năng truyền tải thứ tự cấp. Thủ tục như sau:

1. Store phần tử dữ liệu của các nút gặp phải trong một vector
2. Nếu nút là NULL, sau đó lưu trữ một số đặc biệt (INT_MIN)
3. Theo dõi cuối cùng phi nút null đã truy cập - lastentry
4. Bây giờ hãy duyệt qua vectơ cho đến cuối cùng. Nếu bạn từng gặp INT_MIN, thì cây chưa hoàn thành. Khác nó là một cây nhị phân hoàn chỉnh.

Đây là một mã C++:

nút cây của tôi là:

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

tham khảo: Kiểm tra liên kết sau đây để giải thích chi tiết http://www.geeksforgeeks.org/check-if-a-given-binary-tree-is-complete-tree-or-not/

Answer 12

Cám ơn Mã giả của @Jonathan Graehl. Tôi đã triển khai nó trong Java. Tôi đã thử nghiệm nó chống lại phiên bản lặp đi lặp lại. Nó hoạt động như một say mê!

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

Dưới đây là một mã C để kiểm tra nếu cây nhị phân hoàn tất:

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

Cách nó hoạt động là:

• Nếu độ sâu của cây con bên trái là giống như chiều sâu của cây con phải, nó trả về độ sâu của hirearchy.

• nếu chiều sâu của cây con trái lớn hơn độ sâu của cây con bên phải, nó trả về độ sâu của cây con phải lên hirarchy và cho phép cờ.

• Nếu thấy rằng độ sâu của cây con trái và cây con phải và cờ đã được đặt, nó sẽ trả về -1 lên phân cấp.

• Cuối cùng, nếu hàm trả về -1, thì đó không phải là cây con hoàn chỉnh, nếu không giá trị trả về là độ sâu tối thiểu của cây.