בדוק אם עץ בינארי נתון הושלם או לא


רמת קושי קשה
נשאל לעתים קרובות אלציה אמריקן אקספרס דאטבריקס ארנק Oxigen Spotify
עץ בינארי תור עֵץ

הצהרת בעיה

הבעיה "בדוק אם עץ בינארי נתון הוא שלם או לא" קובעת שקיבלת שורש של עץ בינארי, בדוק אם העץ שלם או לא. עץ בינארי מלא כולל את כל הרמות שלו למעט הרמה האחרונה והצמתים ברמה האחרונה הם שמאליים ככל האפשר.

דוגמאות

קֶלֶט

בדוק אם עץ בינארי נתון הושלם או לא

true

קֶלֶט

בדוק אם עץ בינארי נתון הושלם או לא

false

גישה

A עץ בינארי שלם הוא עץ בינארי בהן כל הרמות מלאות למעט הרמה האחרונה וצמתי הרמה האחרונה הם שמאליים ככל האפשר.

כדי לבדוק אם עץ בינארי הושלם או לא, נוכל להשתמש ב- חציית סדר ברמה של העץ.

  1. הגדר צומת שלם כצומת שיש בו ילד שמאלי וימין כאחד.
  2. עבור עץ שלם, אם אנו רואים צומת שאינו שלם במהלך מעבר סדר ברמה, אז כל הצמתים אחרי צומת זה צריכים להיות צמתים עלים, אחרת העץ אינו שלם.
  3. כמו כן אם יש צומת עם ילד ימני כלא ריק וילד שמאל כלא, העץ אינו שלם.

אַלגוֹרִיתְם

  1. אם השורש הוא אפס, החזירו אמת.
  2. צור תור ודחף אליו את צומת השורש. אתחל משתנה בוליאני נמצא NonComplete כשקר.
  3. בעוד שהתור אינו ריק חזור על שלב 4.
  4. הסר צומת מהתור, תן לזה להיות צומת נוכחי. אם הילד השמאלי של הצומת הנוכחי אינו אפס, בדוק אם נמצא NonComplete נכון, אם כן החזר שקר, אחרת דחף את הילד השמאלי לתור, אם הילד השמאלי הוא null, סמן את foundNonComplete כנכון. באופן דומה, אם הילד הנכון אינו ריק, בדוק אם נמצא NonComplete נכון, אם כן החזר שקר, אחרת דחף את הילד הנכון לתור, אם הילד הנכון הוא null סמן נמצא NonComplete כנכון.
  5. אם נגיע לשלב 5, חזור נכון.

קופונים

קוד Java כדי לבדוק אם עץ בינארי נתון הושלם או לא

import java.util.LinkedList;
import java.util.Queue;
class CheckWhetherAGivenBinaryTreeIsCompleteOrNot {
    // class representing the node of a binary tree
    static class Node {
        int data;
        Node left, right;

        public Node(int data) {
            this.data = data;
        }
    }

    private static boolean isComplete(Node root) {
        // if root is null, return true
        if (root == null) {
            return true;
        }

        // create a queue to do level order traversal
        Queue<Node> queue = new LinkedList<>();
        // add the root node to queue
        queue.add(root);
        // initialize foundNonComplete as false
        boolean foundNonComplete = false;

        while (!queue.isEmpty()) {
            // remove a node from queue
            Node curr = queue.poll();
            if (curr.left != null) {
                // if a non complete node was found, return false
                if (foundNonComplete) {
                    return false;
                }
                // add the left child to queue
                queue.add(curr.left);
            } else {
                // if left child is null, this is a non complete node
                foundNonComplete = true;
            }

            if (curr.right != null) {
                // if a non complete node was found, return false
                if (foundNonComplete) {
                    return false;
                }
                // add the right child to queue
                queue.add(curr.right);
            } else {
                // if right child is null, this is a non complete node
                foundNonComplete = true;
            }
        }

        // reaching here means tree is complete
        return true;
    }

    public static void main(String[] args) {
        // Example 1
        Node root1 = new Node(1);
        root1.left = new Node(2);
        root1.right = new Node(3);
        root1.left.left = new Node(4);
        root1.left.right = new Node(5);
        System.out.println(isComplete(root1));

        // Example 2
        Node root2 = new Node(9);
        root2.left = new Node(8);
        root2.right = new Node(14);
        root2.left.left = new Node(10);
        root2.right.right = new Node(2);
        System.out.println(isComplete(root2));
    }
}
true
false

קוד C ++ כדי לבדוק אם עץ בינארי נתון הושלם או לא

#include <bits/stdc++.h> 
using namespace std; 

// class representing the node of a binary tree
class Node {
    public:
    int data;
    Node *left;
    Node *right;
    
    Node(int d) {
        data = d;
        left = right = NULL;
    }
};

bool isComplete(Node *root) {
    // if root is null, return true
    if (root == NULL) {
        return true;
    }
    
    // create a queue to do level order traversal
    queue<Node*> q;
    // add the root node to queue
    q.push(root);
    // initialize foundNonComplete as false
    bool foundNonComplete = false;
    
    while (!q.empty()) {
        // remove a node from queue
        Node *curr = q.front();
        q.pop();
        if (curr->left != NULL) {
            // if a non complete node was found, return false
            if (foundNonComplete)
                return false;
            // add the left child to queue
            q.push(curr->left);
        } else {
            // if left child is null, this is a non complete node
            foundNonComplete = true;
        }
        
        if (curr->right != NULL) {
            // if a non complete node was found, return false
            if (foundNonComplete) 
                return false;
            q.push(curr->right);
        }
    }
    
    // reaching here means tree is complete
    return true;
}

int main() {
    // Example 1
    Node *root1 = new Node(1);
    root1->left = new Node(2);
    root1->right = new Node(3);
    root1->left->left = new Node(4);
    root1->left->right = new Node(5);
    if (isComplete(root1)) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }

    // Example 2
    Node *root2 = new Node(9);
    root2->left = new Node(8);
    root2->right = new Node(14);
    root2->left->left = new Node(10);
    root2->right->right = new Node(2);
    if (isComplete(root2)) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }
    
    return 0;
}
true
false

ניתוח מורכבות

מורכבות זמן

O (N) כפי שעשינו רק חציית סדר ברמה של העץ הבינארי. הסדר ברמה עובר דרך צמתי העץ. כך האלגוריתם פועל במורכבות זמן ליניארית.

מורכבות בחלל

O (N) מעבר הסדר ברמה מחייב שימוש בתור מה שהופך את האלגוריתם למורכבות שטח ליניארית.