ორობითი ხის განმეორებითი შეკვეთა


Რთული ტური საშუალო
ორობითი ხე ხის გადაკვეთა

”ორობითი ხის განმეორებითი შეკვეთა” პრობლემაში მოცემულია ა ორობითი ხე. ჩვენ უნდა გადავიაროთ ის არაორდინალური გზით "იტერაციულად"რეკურსის გარეშე.

მაგალითი

                 2

              /     \

            1         3

          /   \

        4       5                

4 1 5 2 3
           1 
 
         /    \

       2        3

     /            \

    4               6

                      \

                        7

4 2 1 3 6 7

ალგორითმი

  1. ცვლადის ინიციალიზაცია "CurNode" როგორც ორობითი ხის ფესვი
  2. ინიცირება ცარიელი დასტისთვის, კვანძების შემცველი როგორც მათ განიხილავენ
  3. გააკეთეთ შემდეგი სანამ სტეკი არ არის ცარიელი ან curNode არ გამხდარა NULL:
    • მიუხედავად იმისა, curNode is არ NULL:
      1. დააყენებს curNode დასტაში
      2. გააგრძელეთ ყველაზე მარცხენა ბავშვისკენ მიმდინარე კვანძის შეცვლა, როგორც curNode = curNode-> მარცხენა
    • ახლა, დასტის ზედა კვანძი არის ამჟამინდელი ქვედა ხის ყველაზე მარცხენა კვანძი, ამიტომ ჩვენ დავბეჭდით დასტის ზედა კვანძის მნიშვნელობას
    • დაავალოს curNode როგორც დასტის ზედა კვანძის მარჯვენა ბავშვი, როგორც curNode = stack.top () -> მარჯვნივ 
    • გააგრძელეთ ყველაზე მარცხენა ბავშვისკენ მიმდინარე კვანძის შეცვლა, როგორც curNode = curNode-> მარცხენა ამ მარცხენა კვანძის მარჯვენა ქვეტარის დამუშავება
    • გამოაყოლეთ ელემენტი დასტიდან

განმარტება

პროგრამა იყენებს იდეას, რომ დასტა გამოდის ყველაზე ბოლოს დამატებული ელემენტით. ზემოთ აღწერილ ალგორითმში ჩვენ უბრალოდ ვასკვნით, რომ თუ მიმდინარე კვანძი (რომელიც თავდაპირველად წარმოადგენს ხე) აქვს მარცხენა შვილი, შემდეგ ჩვენ ვაგრძელებთ მის მარცხენა ბავშვის დასტისკენ მიტანას, სანამ აღარ დარჩებიან ბავშვები.

როდესაც საქმე ჩნდება ისეთი, რომ მიმდინარე კვანძს არ ჰყავს დარჩენილი ბავშვი, ცხადია, რომ დასტის ზედა კვანძი არის "ყველაზე ბოლოს მარცხენა კვანძი" დაამატა. ასე რომ, იგი პირველ რიგში უნდა იყოს გადაკვეთის დარჩენილი თანმიმდევრობით. ამრიგად, ჩვენ ვიწყებთ მის დაბეჭდვას / დამატებას შეკვეთების სიაში და გამოვდივართ დასტისგან. ერთხელ გაკეთებული, ჩვენ ახლა უკვე ნათლად ვიცით ის ფაქტი, რომ მარცხენა cur- კვანძი-მარჯვნივ (რიგის თანმიმდევრობა), მარცხნივ და Node ნაწილი გადაიკვეთა. ამრიგად, კვანძის მარჯვენა ქვეტყე შედის პროცესში!

ინტუიციურად, რადგან გვინდა იგივე პროცესი მივმართოთ ამჟამინდელი კვანძის მარჯვენა ქვეჯგუფზე, მისი განზოგადება შეგვიძლია: curNode = curNode-> მარჯვნივ.

ორობითი ხის განმეორებითი შეკვეთა

განხორციელება

C ++ ორობითი ხის განმეორებითი არაორდინალური გადაკვეთის პროგრამა

#include <bits/stdc++.h>

using namespace std;

struct treeNode
{
    int value;
    treeNode *left , *right;
    treeNode(int x)
    {
        value = x;
        left = NULL;
        right = NULL;
    }
};



void iterativeInorder(treeNode* root)
{
    stack <treeNode*> ;
    treeNode* curNode = root;elements

    while(curNode != NULL || !elements.empty())
    {
        while(curNode != NULL)
        {
            elements.push(curNode);
            curNode = curNode->left;
        }


        cout << elements.top()->value << " ";
        curNode = elements.top()->right;
        elements.pop();
    }
}


int main()
{
    treeNode* root = new treeNode(2);
    root->left = new treeNode(1);
    root->right = new treeNode(3);
    root->left->left = new treeNode(4);
    root->left->right = new treeNode(5);

    iterativeInorder(root);
    cout << endl;
    return 0;
}
4 1 5 2 3 

ორობითი ხის განმეორებითი არაორდინალური გადაკვეთის ჯავის პროგრამა

import java.util.Stack; 
  
class treeNode 
{ 
    int value; 
    treeNode left, right; 
  
    public treeNode(int x) 
    { 
        value= x; 
        left = right = null; 
    } 
} 
  
class Tree 
{ 
    treeNode root; 
    void iterativeInorder() 
    { 
        
        Stack<treeNode> elements = new Stack<treeNode>(); 
        treeNode curNode = root; 
  
        while (curNode != null || !elements.empty()) 
        { 
            while (curNode != null) 
            { 
                elements.push(curNode); 
                curNode = curNode.left; 
            } 
 
            curNode = elements.peek().right;
            System.out.print(elements.peek().value + " ");
            elements.pop();
        } 
    } 
  
    public static void main(String args[]) 
    { 
        Tree tree = new Tree(); 
        tree.root = new treeNode(2); 
        tree.root.left = new treeNode(1); 
        tree.root.left.left = new treeNode(4); 
        tree.root.left.right = new treeNode(5); 
        tree.root.right = new treeNode(3); 
        tree.iterativeInorder(); 
    } 
}
4 1 5 2 3

სირთულის ანალიზი

დროის სირთულე ორობითი ხის განმეორებითი შეკვეთა

დროის სირთულეა O (N), რადგან თითოეულ კვანძს ზუსტად ერთხელ ვსტუმრობთ. აქ, N არის ორობითი ხის კვანძების რაოდენობა.

სივრცის სირთულე ორობითი ხის განმეორებითი შეკვეთა

სივრცის სირთულეა O (N) ყველაზე ცუდი შემთხვევის გათვალისწინებით, როდესაც ხე შეიძლება იყოს დახრილი, სივრცის სირთულე ტოლი იქნება ორობითი ხის კვანძების რაოდენობის.