روش تکراری برای یافتن ارتفاع درخت دوتایی


سطح دشواری متوسط
اغلب در همبستگی خشت آمازون متعصبان فورکایت پیاده روی اسنپدل یاترا
درخت باینری صف درخت

بیان مسأله

مسئله "روش تکراری برای یافتن ارتفاع درخت دودویی" بیان می کند که به شما یک a داده می شود درخت دودویی، ارتفاع درخت را با استفاده از روش تکرار پیدا کنید.

مثال ها

ورودی
روش تکراری برای یافتن ارتفاع درخت دوتایی

3

ورودی
روش تکراری برای یافتن ارتفاع درخت دوتایی

4

الگوریتمی برای روش تکراری برای یافتن ارتفاع درخت دوتایی

ارتفاع یک درخت نیز برابر است با تعداد سطوح توی درخت. بنابراین برای پیدا کردن ارتفاع با استفاده از تکرار ، a را انجام دهید پیمایش سفارش سطح از درخت و تعداد سطوح موجود در آن را بشمارید.

  1. ایجاد یک صف و ریشه را به آن فشار دهید. مقدار اولیه را برابر 0 قرار دهید.
  2. در حالی که صف خالی نیست مراحل 3 و 4 را تکرار کنید.
  3. در این لحظه صف شامل یک سطح از درخت است. ارتفاع را با 1 افزایش دهید. اندازه متغیر را به عنوان اندازه صف شروع کنید.
  4. یک حلقه را از 1 به اندازه اجرا کنید و در هر تکرار یک عنصر را از صف خارج کرده و فرزندان خود را به سمت صف فشار دهید. این مرحله یک سطح را از صف حذف کرده و سطح بعدی را به سمت آن سوق می دهد.
  5. ارتفاع بازگشت

توضیح

درختی که در مثال اول نشان داده شده را در نظر بگیرید ،

مرحله 1:

ریشه را به صف فشار دهید و ارتفاع را برابر 0 کنید ، یعنی
صف = 2 ، ارتفاع = 0

مرحله 2:

مرحله 3 و 4 را تکرار کنید در حالی که صف خالی نیست.

مرحله 3 و 4:

تکرار 1:
صف شامل اولین سطح درخت است.
افزایش قد ، بنابراین قد = 1.
تمام عناصر صف را بردارید و فرزندان آنها را به صف اضافه کنید.
صف = 7 -> 11

تکرار 2:
صف شامل سطح دوم درخت است.
افزایش قد ، بنابراین قد = 2.
تمام عناصر صف را بردارید و فرزندان آنها را به صف اضافه کنید.
صف = 5 -> 9 -> 3

تکرار 3:
صف شامل سطح سوم درخت است.
افزایش قد ، بنابراین قد = 3.
تمام عناصر صف را بردارید و فرزندان آنها را به صف اضافه کنید.
صف = صفر

با خالی شدن صف ، ما در اینجا متوقف می شویم.

مرحله 5:

ارتفاع را برگردانید ، بنابراین ارتفاع درخت 3 است.

رمز

کد جاوا برای روش تکراری برای یافتن ارتفاع درخت باینری

import java.util.LinkedList;
import java.util.Queue;

class IterativeMethodToFindHeightOfBinaryTree {
    // class representing node of a binary tree
    static class Node {
        int data;
        Node left, right;

        public Node(int data) {
            this.data = data;
        }
    }

    private static int height(Node root) {
        if (root == null) {
            return 0;
        }

        // create a queue and push root to it
        Queue<Node> q = new LinkedList<>();
        q.add(root);
        // initialise height as 0
        int height = 0;

        // do a level order traversal
        // while queue is not empty
        while (!q.isEmpty()) {
            // increment height
            height++;
            // initialise size as size of queue
            int size = q.size();
            // Remove current level from queue and push next level
            for (int i = 0; i < size; i++) {
                // remove an element from queue
                Node curr = q.poll();
                // push current element's children to the queue
                if (curr.left != null)
                    q.add(curr.left);
                if (curr.right != null)
                    q.add(curr.right);
            }
        }
        
        // return height
        return height;
    }

    public static void main(String[] args) {
        // Example Tree 1
        Node root1 = new Node(2);
        root1.left = new Node(7);
        root1.right = new Node(11);
        root1.left.left = new Node(5);
        root1.right.left = new Node(9);
        root1.right.right = new Node(3);

        System.out.println(height(root1));

        // Example Tree 2
        Node root2 = new Node(1);
        root2.left = new Node(2);
        root2.right = new Node(3);
        root2.left.left = new Node(4);
        root2.left.right = new Node(5);
        root2.right.right = new Node(6);
        root2.left.left.left = new Node(7);
        root2.left.left.right = new Node(8);
        root2.right.right.left = new Node(9);
        root2.right.right.right = new Node(10);

        System.out.println(height(root2));
    }
}
3
4

C ++ کد روش تکراری برای یافتن ارتفاع درخت دوتایی

#include <bits/stdc++.h>
using namespace std;

// class representing node of a binary tree
class Node {
    public:
    int data;
    Node *left;     
    Node *right;
    
    Node(int d) {
        data = d;
        left = right = NULL;
    }
};

// function to create a new node with data d
Node* newNode(int d) {
    Node *node = new Node(d);
    return node;
}

int height(Node *root) {
    if (root == NULL) {
        return 0;
    }
    
    // create a queue and push root to it
    queue<Node*> q;
    q.push(root);
    // initialise height as 0
    int height = 0;
    
    // do a level order traversal
    // while queue is not empty
    while (!q.empty()) {
        // increment height
        height++;
        // initialise size as size of queue
        int size = q.size();
        // Remove current level from queue and push next level
        for (int i = 0; i < size; i++) {
            // remove an element from queue
            Node *curr = q.front();
            // push current element's children to the queue
            q.pop();
            if (curr->left != NULL)
                q.push(curr->left);
            if (curr->right != NULL)
                q.push(curr->right);
        }
    }
    
    // return height
    return height;
}

int main() {
    // Example Tree 1
    Node *root1 = newNode(2);
    root1->left = newNode(7);
    root1->right = newNode(11);
    root1->left->left = newNode(5);
    root1->right->left = newNode(9);
    root1->right->right = newNode(3);

    cout<<height(root1)<<endl;

    // Example Tree 2
    Node *root2 = newNode(1);
    root2->left = newNode(2);
    root2->right = newNode(3);
    root2->left->left = newNode(4);
    root2->left->right = newNode(5);
    root2->right->right = newNode(6);
    root2->left->left->left = newNode(7);
    root2->left->left->right = newNode(8);
    root2->right->right->left = newNode(9);
    root2->right->right->right = newNode(10);

    cout<<height(root2)<<endl;
    
    return 0;
}
3
4

تحلیل پیچیدگی

پیچیدگی زمان

O (N)، جایی که n تعداد گره های موجود در درخت باینری است. از آنجا که ما از یک صف استفاده کرده ایم و بر روی تمام گره های درخت باینری عبور کرده ایم. بنابراین واضح است که پیچیدگی زمان خطی است.

پیچیدگی فضا

بر)، که n تعداد گره های موجود در درخت باینری است. همانطور که قبلاً گفته شد که ما از یک صف برای یافتن ارتفاع استفاده کرده ایم ، عناصر را در آن صف ذخیره کرده ایم. بنابراین پیچیدگی فضا نیز خطی است.

منابع