Bağlı Siyahı Təmsilindən Tam İkili Ağac Qurun

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Amazon
İkili ağac Queue AğacBaxılıb 76

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Tam bir ikili əlaqəli siyahı təqdimatı verilmişdir ağac. Bağlı siyahı sıradadır səviyyə sifarişinin kəsişməsi ağacın. Tam ikili ağacın ağacından geri qurulması üçün bir alqoritm yazın əlaqəli siyahı nümayəndəliyi.

misal

Input
1 -> 2 -> 3 -> 4 -> 5
Buraxılış
Sifarişin pozulması
4 2 5 1 3

Bağlı Siyahı Təmsilindən Tam İkili Ağac QurunPin

Tam ikili ağacın qurulması üçün alqoritm

Tam ikili ağac, son səviyyə xaricində bütün səviyyələri tamamilə doldurmuş və son səviyyədəki bütün qovşaqlar mümkün qədər qalan ikili bir ağacdır. Tam bir ağac bir sıra vasitəsi ilə təmsil olunduqda, massivdəki i indeksindəki bir qovşaq sol uşağını (2 * i + 1), sağ uşağını isə (2 * i + 2) göstərir. Eyni şeyi əlaqəli siyahı təmsilçiliyində görüntüləyə bilərik.
Beləliklə, indeks 0-dakı düyünün uşaqları indeks 1 və 2-də, indeks 1-dəki düyünün uşaqları indeks 3 və 4-də və s.

Bağlı siyahı təqdimatını ağaca çevirmək fikri, əlaqəli siyahının ilk qovşağının həmişə ağacın kökü olmasıdır. Beləliklə kökü bir növbədə itələyirik, ağacda bir BFS edirik və eyni zamanda ağaca çevirmək üçün əlaqəli siyahıda gəzirik. Ağacdakı hər düyün üçün əlaqəli siyahıda biri sol uşaq, digəri sağ uşaq üçün iki qovşaq keçir.

  1. Bir növbə yaradın, deyin q.
  2. Bağlı siyahının başını növbəyə itələyin.
  3. Bağlı siyahının sonuna çatmasa da, 4-cü addımı təkrarlayın.
  4. Düyünü növbədən çıxarın, ana olsun. Siyahıda keçid, birinci qovşaq valideynin sol övladı, ikinci qovşaq valideynin sağ övladıdır. Həm də sol və sağ uşağı növbəyə qoyun.

Tam ikili ağac qurmaq üçün JAVA kodu

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

public class ConstructCompleteBinaryTreeFromItsLinkedListRepresentation {
    // class representing node of a linked list
    static class ListNode {
        int data;
        ListNode next;

        public ListNode(int data) {
            this.data = data;
        }
    }
    
    // class representing node of a binary tree
    static class TreeNode {
        int data;
        TreeNode left, right;

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

    // function to print inorder traversal of a tree
    private static void inorder(TreeNode root) {
        if (root != null) {
            inorder(root.left);
            System.out.print(root.data + " ");
            inorder(root.right);
        }
    }

    private static void constructCompleteBinaryTree(ListNode head) {
        if (head == null) {
            return;
        }

        // initialize root of the tree as head of linked list
        TreeNode root = new TreeNode(head.data);
        // create a queue
        Queue<TreeNode> q = new LinkedList<>();
        // push the root of the tree to the queue
        q.add(root);

        while (head != null) {
            // remove an element from the queue
            TreeNode parent = q.poll();

            // traverse in linked list
            head = head.next;
            if (head != null) {
                // this node of linked list is the left child of parent
                TreeNode leftChild = new TreeNode(head.data);
                parent.left = leftChild;
                // add left child to the queue
                q.add(leftChild);

                // traverse in linked list
                head = head.next;
                if (head != null) {
                    // this node of the linked list is the right child of parent
                    TreeNode rightChild = new TreeNode(head.data);
                    parent.right = rightChild;
                    // add right child to the queue
                    q.add(rightChild);
                }
            }
        }

        // print inorder traversal of the tree
        System.out.println("Inorder Traversal");
        inorder(root);
        System.out.println();
    }

    public static void main(String[] args) {
        // Example
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);

        constructCompleteBinaryTree(head);
    }
}
Inorder Traversal
4 2 5 1 3

Tam ikili ağacın qurulması üçün C ++ kodu

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

// class representing node of a linked list
class ListNode {
    public:
    int data;
    ListNode *next;
    
    ListNode(int d) {
        data = d;
        next = NULL;
    }
};

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

// function to print inorder traversal of a tree
void inorder(TreeNode *root) {
    if (root != NULL) {
        inorder(root->left);
        cout<<root->data<<" ";
        inorder(root->right);
    }
}

void constructCompleteBinaryTree(ListNode *head) {
    if (head == NULL) {
        return;
    }
    
    // initialize root of the tree as head of linked list
    TreeNode *root = new TreeNode(head->data);
    // create a queue
    queue<TreeNode *> q;
    // push the root of the tree to the queue
    q.push(root);
    
    while (head != NULL) {
        // remove an element from the queue
        TreeNode *parent = q.front();
        q.pop();
        
        // traverse in linked list
        head = head->next;
        if (head != NULL) {
            // this node of linked list is the left child of parent
            TreeNode *leftChild = new TreeNode(head->data);
            parent->left = leftChild;
            // add left child to the queue
            q.push(leftChild);
            
            // traverse in linked list
            head = head->next;
            if (head != NULL) {
                // this node of the linked list is the right child of parent
                TreeNode *rightChild = new TreeNode(head->data);
                parent->right = rightChild;
                // add right child to the queue
                q.push(rightChild);
            }
        }
    }
    
    // print inorder traversal of the tree
    cout<<"Inorder Traversal"<<endl;
    inorder(root);
    cout<<endl;
}

int main() {
    ListNode *head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    head->next->next->next = new ListNode(4);
    head->next->next->next->next = new ListNode(5);
    
    constructCompleteBinaryTree(head);
    
    return 0;   
}
Inorder Traversal
4 2 5 1 3

Mürəkkəblik təhlili

Zaman Mürəkkəbliyi = O (n)
Kosmik Mürəkkəblik = O (n)
burada n - əlaqəli siyahıdakı elementlərin sayı.

İstinad1  arayış2

Crack Sistemi Dizayn Müsahibələri
Translate »