የተሰጠው የሁለትዮሽ ዛፍ የተሟላ መሆኑን ወይም አለመሆኑን ያረጋግጡ


የችግር ደረጃ ጠንካራ
ውስጥ በተደጋጋሚ ተጠየቀ የመርጨት አሜሪካን ኤክስፕረስ የመረጃ ቋቶች ኦክሲጀን የኪስ ቦርሳ Spotify
ሁለትዮሽ ዛፍ ተራ ዛፍ

የችግሩ መግለጫ

ችግሩ “የተሰጠው የሁለትዮሽ ዛፍ የተሟላ መሆን አለመሆኑን ያረጋግጡ” የሚለው የሁለትዮሽ ዛፍ ሥር ይሰጥዎታል ፣ ዛፉ የተሟላ መሆኑን ወይም አለመሆኑን ይናገራል። የተሟላ የሁለትዮሽ ዛፍ ከመጨረሻው ደረጃ በስተቀር ሁሉንም ደረጃዎቹን ሞልቶታል እና በመጨረሻው ደረጃ ላይ ያሉት አንጓዎች በተቻለ መጠን ይቀራሉ ፡፡

ምሳሌዎች

ግቤት

የተሰጠው የሁለትዮሽ ዛፍ የተሟላ መሆኑን ወይም አለመሆኑን ያረጋግጡ

true

ግቤት

የተሰጠው የሁለትዮሽ ዛፍ የተሟላ መሆኑን ወይም አለመሆኑን ያረጋግጡ

false

ቀረበ

A ተጠናቅቋል ሁለትዮሽ ዛፍ ነው ሁለትዮሽ ዛፍ ከመጨረሻው ደረጃ እና ከመጨረሻው ደረጃ አንጓዎች በስተቀር ሁሉም ደረጃዎች የሚሞሉበት በተቻለ መጠን ይቀራሉ ፡፡

የሁለትዮሽ ዛፍ መሟላቱን ወይም አለመሆኑን ለመፈተሽ ፣ መጠቀም እንችላለን ደረጃ ማዘዋወር የዛፉ ፡፡

  1. የተሟላ መስቀለኛ መንገድ የግራ እና የቀኝ ልጅ ያለው መስቀለኛ ያልሆነ ዋጋ እንደሌለው ይግለጹ ፡፡
  2. ለሙሉ ዛፍ ፣ በደረጃ ማዘዋወር ወቅት ያልተሟላ መስቀለኛ መንገድ ካየን ፣ ከዚያ ከዚህ መስቀለኛ ክፍል በኋላ ያሉት ሁሉም አንጓዎች የቅጠል ኖዶች መሆን አለባቸው ፣ ካልሆነ ግን ዛፉ አልተጠናቀቀም ፡፡
  3. እንዲሁም ከቀኝ ልጅ ጋር ባዶ ያልሆነ እና ግራ ልጅ እንደ ከንቱ መስቀለኛ መንገድ ካለ ፣ ዛፉ አልተጠናቀቀም።

አልጎሪዝም

  1. ሥሩ ከንቱ ከሆነ ወደ እውነት ይመለሱ ፡፡
  2. ወረፋ ይፍጠሩ እና የስር መስቀለኛ መንገዱን ወደ እሱ ይግፉት። የውሸት ያልሆነ የተገኘ የቦሌን ተለዋዋጭ ያስጀምሩ ፡፡
  3. ወረፋው ድገም ደረጃ 4 ባዶ ባይሆንም።
  4. አንድ መስቀለኛ መንገድ ከወረፋው ላይ ያስወግዱ ፣ የአሁኑ መስቀለኛ ይሁን። የአሁኑ መስቀለኛ መንገድ ግራ ልጅ ባዶ ካልሆነ ፣ ካልተገኘ አረጋግጥ ኖን ኮምፕሌቱ እውነት ከሆነ ፣ አዎ ሐሰት ከተመለሰ ፣ ሌላኛው ደግሞ ግራውን ልጅ ወደ ወረፋው ይግፉት ፣ የግራ ልጅ ከንቱ ከሆነ ፣ የተገኘውን ኖን አጠናቆ እንደ እውነት ምልክት ያድርጉበት። በተመሳሳይ ፣ ትክክለኛው ልጅ ዋጋ ቢስ ከሆነ ፣ አልተገኘምNonComplete እውነት መሆኑን ያረጋግጡ ፣ አዎ ሐሰት ከተመለሰ ፣ ሌላኛው ልጅ ወደ ወረፋ እንዲገፋው ፣ የቀኝ ልጅ ከንቱ ምልክት ከተገኘ nonComplete እንደ እውነት ነው።
  5. ደረጃ 5 ከደረስን ወደ እውነት ተመለስ ፡፡

ኮድ

የተሰጠው የሁለትዮሽ ዛፍ የተሟላ መሆን አለመሆኑን ለማጣራት የጃቫ ኮድ

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

ውስብስብነት ትንተና

የጊዜ ውስብስብነት

ኦ (ኤን) ፣ የሁለትዮሽ ዛፍ ደረጃ መሻገሪያ ብቻ እንዳደረግን ፡፡ ደረጃው በዛፉ አንጓዎች በኩል ያልፋል። ስለዚህ አልጎሪዝም በመስመራዊ የጊዜ ውስብስብነት ውስጥ ይሠራል።

የቦታ ውስብስብነት

ኦ (ኤን) ፣ የደረጃ ቅደም ተከተል መተላለፍ አልጎሪዝም መስመራዊ የቦታ ውስብስብነት እንዲኖረው የሚያደርግ ወረፋ መጠቀምን ይጠይቃል።