تحقق مما إذا كانت شجرة ثنائية معينة كاملة أم لا


مستوى الصعوبة الثابت
كثيرا ما يطلب في Alation أمريكان إكسبريس Databricks محفظة Oxigen سبوتيفي
شجرة ثنائية طابور شجرة

المشكلة بيان

تشير مشكلة "التحقق مما إذا كانت شجرة ثنائية معينة كاملة أم لا" إلى أنك قد أعطيت جذر شجرة ثنائية ، تحقق مما إذا كانت الشجرة كاملة أم لا. تم ملء جميع مستويات الشجرة الثنائية الكاملة باستثناء المستوى الأخير والعقد في المستوى الأخير متروكة قدر الإمكان.

أمثلة

إدخال

تحقق مما إذا كانت شجرة ثنائية معينة كاملة أم لا

true

إدخال

تحقق مما إذا كانت شجرة ثنائية معينة كاملة أم لا

false

الرسالة

A شجرة ثنائية كاملة هو شجرة ثنائية حيث يتم ملء جميع المستويات باستثناء المستوى الأخير وعقد المستوى الأخير قدر الإمكان.

للتحقق مما إذا كانت الشجرة الثنائية كاملة أم لا ، يمكننا استخدام اجتياز ترتيب المستوى من الشجرة.

  1. قم بتعريف عقدة كاملة على أنها العقدة التي تحتوي على كل من الطفل الأيمن والأيسر على أنها ليست فارغة.
  2. للحصول على شجرة كاملة ، إذا رأينا عقدة غير كاملة أثناء اجتياز ترتيب المستوى ، فيجب أن تكون جميع العقد بعد هذه العقدة عبارة عن عقد ورقية ، وإلا لم تكتمل الشجرة.
  3. وأيضًا إذا كانت هناك عقدة بها الطفل الأيمن ليس فارغًا وكان الطفل الأيسر فارغًا ، فلن تكون الشجرة كاملة.

خوارزمية

  1. إذا كان الجذر فارغًا ، فنعود صحيحًا.
  2. قم بإنشاء قائمة انتظار وادفع عقدة الجذر إليها. تم العثور على تهيئة متغير منطقي غير كامل على أنه خطأ.
  3. بينما قائمة الانتظار ليست فارغة كرر الخطوة 4.
  4. قم بإزالة عقدة من قائمة الانتظار ، فليكن العقدة الحالية. إذا لم يكن الطفل الأيسر للعقدة الحالية فارغًا ، فتحقق مما إذا كان foundNonComplete صحيحًا ، وإذا كانت الإجابة بنعم ، فقم بإرجاع خطأ ، وإلا ادفع الطفل الأيسر إلى قائمة الانتظار ، وإذا كان الطفل الأيسر فارغًا ، فضع علامة على foundNonComplete على أنه صحيح. وبالمثل ، إذا لم يكن الطفل الصحيح فارغًا ، فتحقق مما إذا تم العثور على "غير كامل" صحيحًا ، وإذا كانت الإجابة "نعم" ، فقم بإرجاع خطأ ، وإلا ادفع الطفل المناسب إلى قائمة الانتظار ، إذا كان الطفل الصحيح عبارة عن علامة فارغة تم العثور عليها
  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) يتطلب اجتياز ترتيب المستوى استخدام قائمة الانتظار التي تجعل الخوارزمية لها تعقيد مساحة خطي.