בנה עץ בינארי שלם מייצוג הרשימה המקושרת שלו


רמת קושי בינוני
נשאל לעתים קרובות אמזון בעברית
עץ בינארי תור עֵץ

בהתחשב בייצוג הרשימה המקושרת של בינארי שלם עץ. הרשימה המקושרת היא בסדר גודל של חציית סדר ברמה של העץ. כתוב אלגוריתם לבניית העץ הבינארי השלם ממנו רשימה מקושרת יִצוּג.

דוגמה

קֶלֶט
1 -> 2 -> 3 -> 4 -> 5
תְפוּקָה
מעבר לפי הסדר
4 2 5 1 3

בנה עץ בינארי שלם מייצוג הרשימה המקושרת שלו

אלגוריתם לבניית עץ בינארי שלם

עץ בינארי שלם הוא עץ בינארי שמילא את כל הרמות לחלוטין למעט הרמה האחרונה וכל הצמתים ברמה האחרונה שמאליים ככל האפשר. כמו כן, כאשר עץ שלם מיוצג באמצעות מערך לצומת באינדקס i במערך יש את הילד השמאלי שלו באינדקס (2 * i + 1) והילד הימני באינדקס (2 * i + 2). אנו יכולים לדמיין את אותו הדבר בייצוג הרשימה המקושרת.
כך שילדי הצומת באינדקס 0 נמצאים באינדקס 1 ו -2, ילדים בצומת באינדקס 1 נמצאים באינדקס 3 ו -4, וכן הלאה.

הרעיון להמיר את ייצוג הרשימה המקושרת לעץ הוא שהצומת הראשון של הרשימה המקושרת הוא תמיד שורש העץ. אז אנו דוחפים את השורש בתור, אנו עושים BFS על העץ ועוברים בו זמנית ברשימה המקושרת כדי להמיר אותו לעץ. עבור כל צומת בעץ, אנו חוצים שני צמתים ברשימה המקושרת, אחד עבור הילד השמאלי ואחד עבור הילד הימני.

  1. צור תור, אמור ש.
  2. דחף את ראש הרשימה המקושרת לתור.
  3. אמנם לא מגיעים לסוף הרשימה המקושרת, חזור על שלב 4.
  4. הסר צומת מהתור, תן לזה להיות ההורה. חוצה את הרשימה, הצומת הראשון הוא הילד השמאלי של ההורה, והצומת השני הוא הילד הימני של ההורה. כמו כן, צירף את הילד השמאלי והימני לתור.

קוד JAVA לבניית עץ בינארי שלם

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

קוד C ++ לבניית עץ בינארי שלם

#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

ניתוח מורכבות

מורכבות זמן = O (n)
מורכבות שטח = O (n)
כאשר n הוא מספר האלמנטים ברשימה המקושרת.

הפניה1  הפניה 2