Праверце, ці зададзена двайковае дрэва


Узровень складанасці Жорсткі
Часта пытаюцца ў Алацыя American Express Збор дадзеных Кіслародны кашалёк Spotify
Двайковае дрэва чаргу дрэва

Пастаноўка праблемы

У праблеме "Праверка, ці зададзена двайковае дрэва поўным ці не" гаворыцца, што вам дадзены корань двайковага дрэва, праверце, поўнае гэта дрэва ці не. Поўнае двайковае дрэва мае ўсе ўзроўні, за выключэннем апошняга ўзроўню, і вузлы на апошнім узроўні максімальна левыя.

Прыкладаў

уваход

Праверце, ці зададзена двайковае дрэва

true

уваход

Праверце, ці зададзена двайковае дрэва

false

Падыход

A поўнае двайковае дрэва з'яўляецца бінарнае дрэва у якім запоўнены ўсе ўзроўні, за выключэннем апошняга ўзроўню і вузлы апошняга ўзроўню як мага левей.

Каб праверыць, завершана ці не двайковае дрэва, мы можам выкарыстоўваць абход узроўневага парадку дрэва.

  1. Вызначце поўны вузел як вузел, у якім і левы, і правы даччыныя элементы не маюць нуля.
  2. Для поўнага дрэва, калі мы бачым няпоўны вузел падчас абходу парадку ўзроўню, то ўсе вузлы пасля гэтага вузла павінны быць лістовымі, інакш дрэва не будзе поўным.
  3. Акрамя таго, калі ёсць вузел з правым дачком як не нулявым і левым дачком як нулявым, дрэва не будзе поўным.

Алгарытм

  1. Калі корань нулявы, вярніце true.
  2. Стварыце чаргу і націсніце на яе каранёвы вузел. Ініцыялізаваць лагічную зменную foundNonComplete як ілжывую.
  3. Пакуль чарга не пустая, паўтарыце крок 4.
  4. Выдаліце ​​вузел з чаргі, хай ён будзе бягучым. Калі левы даччык бягучага вузла не роўны нулю, праверце, калі foundNonComplete праўдзівы, калі так, вяртайце false, у адваротным выпадку штурхайце левага даччынага элемента ў чаргу, калі левы даччыны нуль, пазначайце foundNonComplete як ісціну. Сапраўды гэтак жа, калі патрэбнае дзіця не мае null, праверце, калі foundNonComplete ісціна, калі yes вяртае false, у адваротным выпадку націсніце патрэбнае дзіця ў чаргу, калі правільнае дзіця з'яўляецца нулявым знакам foundNonComplete як true.
  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), абыход парадку ўзроўню патрабуе выкарыстання чаргі, што робіць алгарытм складанасцю лінейнай прасторы.