Проверите да ли је дато бинарно стабло комплетно или не


Ниво тешкоће Тежак
Често питани у Алатион америцан екпресс Датабрицкс Окиген новчаник Спотифи
Бинарно дрво Ред Дрво

Изјава о проблему

Проблем „Проверите да ли је дато бинарно стабло комплетно или не“ наводи да сте добили корен бинарног стабла, проверите да ли је стабло комплетно или не. Комплетно бинарно стабло има попуњено све нивое, осим последњег нивоа, а чворови на последњем нивоу су што је могуће левији.

Примери

Улазни

Проверите да ли је дато бинарно стабло комплетно или не

true

Улазни

Проверите да ли је дато бинарно стабло комплетно или не

false

Приступ

A комплетно Бинарно стабло је бинарно стабло у којој су попуњени сви нивои осим последњег нивоа и чворови последњег нивоа су што левији.

Да бисмо проверили да ли је бинарно стабло комплетно или не, можемо користити прелазак редоследа нивоа од дрвета.

  1. Дефинишите комплетан чвор као чвор који има и лево и десно дете као да није нулл.
  2. За цело дрво, ако током преласка редоследа нивоа видимо непотпуни чвор, тада сви чворови након овог чвора морају бити чворови листова, у супротном стабло није комплетно.
  3. Такође, ако постоји чвор са десним дететом који није нулл и левим дететом нулл, стабло није цело.

Алгоритам

  1. Ако је корен нулл, вратите труе.
  2. Направите ред и гурните основни чвор до њега. Иницијализујте логичку променљиву фоундНонЦомплете као фалсе.
  3. Иако ред није празан, поновите 4. корак.
  4. Уклоните чвор из реда, нека буде тренутни чвор. Ако лево дете тренутног чвора није нулл, проверите да ли је фоундНонЦомплете тачно, ако иес врати фалсе, иначе гурните лево дете у ред, ако је лево дете нулл, означите фоундНонЦомплете као тачно. Слично томе, ако право дете није нулл, проверите да ли је фоундНонЦомплете тачно, ако иес врати фалсе, иначе потисните право дете у ред, ако је право дете нулл ознака фоундНонЦомплете као труе.
  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

Ц ++ код за проверу да ли је дато бинарно стабло комплетно или не

#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

Анализа сложености

Сложеност времена

НА), као што смо урадили само обилазак редоследа нивоа бинарног стабла. Прелазак редоследа нивоа пролази кроз чворове стабла. Стога алгоритам ради у линеарној временској сложености.

Сложеност простора

НА), обилажење реда нивоа захтева употребу реда што чини алгоритам линеарном сложеношћу простора.