ပေးထားသော Binary Tree သည်ပြီးပြည့်စုံသည်မဟုတ်ကိုစစ်ဆေးပါ


ခက်ခဲအဆင့် ခိုင်မာသော
မကြာခဏမေးတယ် alation American Express Databricks အောက်စီဂျင်ပိုက်ဆံအိတ် Spotify
ဒွိသစ်ပင် ဆံပင်ကြိုး သစ်ပင်

ပြProbleနာဖော်ပြချက်

ပြaနာ“ ပေးထားသော Binary Tree ပြည့်စုံခြင်းရှိမရှိစစ်ဆေးပါ” သည် binary tree ၏အမြစ်ကိုသင့်အားပေးသည်ဟုဖော်ပြသည်။ ၎င်းသည်သစ်ပင်ပြည့်စုံခြင်းရှိမရှိစစ်ဆေးပါ။ ပြည့်စုံသော Binary Tree တွင်၎င်း၏နောက်ဆုံးအဆင့် မှလွဲ၍ ၎င်း၏အဆင့်အားလုံးနှင့်ပြည့်စုံပြီးနောက်ဆုံးအဆင့်ရှိ node များတတ်နိုင်သမျှကျန်ရှိနေသည်။

ဥပမာ

input

ပေးထားသော Binary Tree သည်ပြီးပြည့်စုံသည်မဟုတ်ကိုစစ်ဆေးပါ

true

input

ပေးထားသော Binary Tree သည်ပြီးပြည့်စုံသည်မဟုတ်ကိုစစ်ဆေးပါ

false

ချဉ်းကပ်နည်း

A Binary သစ်ပင်ဖြည့်စွက် တစ်ဦးဖြစ်ပါတယ် ဒွိသစ်ပင် အားလုံးအဆင့်ဆင့်နောက်ဆုံးအဆင့်နှင့်နောက်ဆုံးအဆင့် node များမှလွဲ။ ဖြည့်နေကြတယ်တတ်နိုင်သမျှကျန်ကြွင်းသောဖြစ်ကြသည်။

binary သစ်ပင်သည်ပြီးပြည့်စုံသည်မဟုတ်ကိုစစ်ဆေးရန်ကျွန်ုပ်တို့သုံးနိုင်သည် အဆင့်ကိုအမိန့်ဖြတ်သန်း သစ်ပင်၏။

  1. node တစ်ခုလုံးကို left နှင့် right နှစ်ခုလုံးကို null အဖြစ်မသတ်မှတ်ပါ။
  2. ပြီးပြည့်စုံသောသစ်ပင်တစ်ခုအတွက်ကျွန်ုပ်တို့သည်အဆင့်အစဉ်လိုက်ဖြတ်သန်းနေစဉ်အတွင်းမပြည့်စုံသော node ကိုတွေ့မြင်ပါကဤ node ပြီးနောက်အချည်းနှီးသော node များသည်အရွက် node များဖြစ်ရမည်။
  3. လက်ျာကလေးရှိသည့် null မဟုတ်သော၊ လက်ဝဲကလေးအား null ကဲ့သို့သော node တစ်ခုရှိလျှင်သစ်ပင်သည်မပြည့်စုံပါ။

algorithm

  1. root သည် null ဖြစ်ပါက true ပြန်လာပါ။
  2. Queue တစ်ခုကိုဖန်တီးပြီး၎င်းကို root node ကိုတွန်းပါ။ foundNonComplete ကို boolean variable တစ်ခုအဖြစ်မှားယွင်းသတ်မှတ်ပါ။
  3. အဆိုပါတန်းစီအချည်းနှီးသောထပ်အဆင့် 4 မဟုတ်နေစဉ်။
  4. Queue မှ node တစ်ခုကိုဖယ်ရှားပါ၊ ၎င်းသည်လက်ရှိ node ဖြစ်ပါစေ။ လက်ရှိ node ၏ဘယ်ဘက်ကလေးသည် null မဟုတ်ပါက foundNonComplete အမှန်ဟုတ်မဟုတ်စစ်ဆေးပါ၊ ဟုတ်ကဲ့ false ကိုပြန်သွားပါကကျန်ကလေးကိုတန်းထဲသို့တွန်းပို့ပါ၊ left ကလေးကို null ဖြစ်လျှင် foundNonComplete ကိုအမှန်ခြစ်ထားပါ။ အလားတူစွာမှန်ကန်သောကလေးသည် null မဟုတ်ပါက foundNonComplete အမှန်ဟုတ်မဟုတ်စစ်ဆေးပါ၊ ဟုတ်ကဲ့ return false ဟုတ်မှန်လျှင်မှန်ကန်သောကလေးက null mark ဖြစ်လျှင် foundNonComplete အမှန်ဖြစ်ပါကစစ်မှန်သောကလေးကိုတွန်းပါ။
  5. အဆင့် ၅ သို့ရောက်လျှင်မှန်ကိုပြန်သွားပါ။

ကုဒ်

ပေးထားသော Binary Tree သည်ပြီးပြည့်စုံသည်မဟုတ်ကိုစစ်ဆေးရန် Java Code

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

ပေးထားသော Binary Tree သည်ပြီးပြည့်စုံသည်မဟုတ်ကိုစစ်ဆေးရန် C ++ Code

#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

ရှုပ်ထွေးဆန်းစစ်ခြင်း

အချိန်ရှုပ်ထွေး

အို (N)၊ ကျနော်တို့သာ binary သစ်ပင်အဆင့်ကိုအမိန့်ဖြတ်သန်းပြုမိပါပြီအဖြစ်။ Tree level node များမှတဆင့် level order traversal သည်ဖြတ်သန်းသွားသည်။ ထို့ကြောင့် algorithm ကို linear အချိန်ရှုပ်ထွေးမှုအတွက်ပြေး။

အာကာသရှုပ်ထွေးမှု

အို (N)၊ အဆိုပါအဆင့်ကိုအမိန့်ဖြတ်သန်း linear အာကာသရှုပ်ထွေးရှိသည်ဖို့ algorithm ကိုစေသည်တန်းစီ၏အသုံးပြုမှုကိုလိုအပ်သည်။