ஒரு பைனரி மரத்தின் மறுபயன்பாட்டு ஒழுங்கற்ற பயணம்  


சிரமம் நிலை நடுத்தர
பைனரி மரம் மரம் பயணம்

"ஒரு பைனரி மரத்தின் மறுபயன்பாட்டு ஒழுங்குபடுத்தல்" சிக்கலில் நமக்கு வழங்கப்படுகிறது பைனரி மரம். நாம் அதை ஒழுங்கற்ற பாணியில் பயணிக்க வேண்டும் “மீண்டும்”, மறுநிகழ்வு இல்லாமல்.

உதாரணமாக  

                 2

              /     \

            1         3

          /   \

        4       5                

4 1 5 2 3
           1 
 
         /    \

       2        3

     /            \

    4               6

                      \

                        7

4 2 1 3 6 7

அல்காரிதம்  

  1. ஒரு மாறியைத் தொடங்கவும் “கர்னோட்” பைனரி மரத்தின் வேராக
  2. வெற்று அடுக்கைத் தொடங்கவும், முனைகளைக் கொண்டிருக்கும் அவர்கள் பயணிக்கையில்
  3. அடுக்கு காலியாக இல்லாத வரை அல்லது பின்வருவனவற்றைச் செய்யுங்கள் கர்னோட் ஆகவில்லை ஏதுமில்லை:
    • போது கர்னோட் is இல்லை ஏதுமில்லை:
      1. புஷ் கர்னோட் அடுக்கில்
      2. தற்போதைய முனையை இவ்வாறு மாற்றுவதன் மூலம் இடதுபுற குழந்தைக்குச் செல்லுங்கள் curNode = curNode-> இடது
    • இப்போது, ​​அடுக்கில் உள்ள மேல் முனை தற்போதைய துணை மரத்தின் இடதுபுற முனை, எனவே அடுக்கின் மேல் முனையின் மதிப்பை அச்சிடுகிறோம்
    • ஒதுக்க கர்னோட் அடுக்கின் மேல் முனையின் சரியான குழந்தையாக curNode = stack.top () -> வலது 
    • தற்போதைய முனையை இவ்வாறு மாற்றுவதன் மூலம் இடதுபுற குழந்தைக்குச் செல்லுங்கள் curNode = curNode-> இடது இந்த இடது முனையின் வலது சப்டிரீயை செயலாக்க
    • அடுக்கிலிருந்து ஒரு உறுப்பை பாப் செய்யவும்

விளக்கம்  

நிரல் மிக சமீபத்திய உறுப்பைச் சேர்த்த யோசனையை நிரல் பயன்படுத்துகிறது, மேலே விளக்கப்பட்ட வழிமுறையில், தற்போதைய முனை (ஆரம்பத்தில் இது வேர் என்றால்) மரம்) ஒரு இடது குழந்தையைப் பெற்றிருக்கிறார், பின்னர் இடது குழந்தைகள் இல்லாத வரை அதன் இடது குழந்தையை அடுக்கில் தள்ளுகிறோம்.

மேலும் காண்க
பிஎஸ்டியில் மாற்றம் அனுமதிக்கப்படாதபோது பிஎஸ்டியில் மிகப் பெரிய உறுப்பு

தற்போதைய முனைக்கு இடது குழந்தை இல்லை என்று வழக்கு எழும்போது, ​​அடுக்கில் உள்ள மேல் முனை என்பது தெளிவாகிறது “மிக சமீபத்தில் இடதுபுற முனை” சேர்க்கப்பட்டது. எனவே, பயணத்தின் மீதமுள்ள வரிசையில் இது முதலில் வர வேண்டும். எனவே, அதை எங்கள் ஆர்டர் பட்டியலில் அச்சிட / சேர்க்கத் தொடங்கி அதை அடுக்கிலிருந்து வெளியேற்றுவோம். ஒருமுறை முடிந்ததும், இப்போது நாம் தெளிவாக இருக்கிறோம் இடது-கர்னோட்-வலது (செயலற்ற வரிசை), இடது மற்றும் கணு பகுதி பயணிக்கிறது. எனவே, முனையின் சரியான துணை மரம் செயல்பாட்டில் உள்ளது!

உள்ளுணர்வாக, தற்போதைய முனையின் வலது துணைக்கு அதே செயல்முறையைப் பயன்படுத்த விரும்புவதால், இதை நாம் பொதுமைப்படுத்தலாம்: curNode = curNode-> வலது.

ஒரு பைனரி மரத்தின் மறுபயன்பாட்டு ஒழுங்கற்ற பயணம்முள்

நடைமுறைப்படுத்தல்  

ஒரு பைனரி மரத்தின் மறுபயன்பாட்டு ஒழுங்கற்ற பயணத்தின் சி ++ திட்டம்

#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

சிக்கலான பகுப்பாய்வு  

நேர சிக்கலானது ஒரு பைனரி மரத்தின் மறுபயன்பாட்டு ஒழுங்கின்மை

நேரம் சிக்கலானது ஓ (என்), ஒவ்வொரு முனையையும் சரியாக ஒரு முறை பார்வையிடும்போது. இங்கே, N என்பது பைனரி மரத்தில் உள்ள முனைகளின் எண்ணிக்கை.

மேலும் காண்க
பிஎஸ்டியில் கே-வது மிகச்சிறிய உறுப்பைக் கண்டறியவும் (பிஎஸ்டியில் ஆர்டர் புள்ளிவிவரம்)

விண்வெளி சிக்கலானது ஒரு பைனரி மரத்தின் மறுபயன்பாட்டு ஒழுங்கின்மை

விண்வெளி சிக்கலானது ஓ (ந). மிக மோசமான நிலையை கருத்தில் கொண்டு, மரம் ஒரு வளைந்ததாக இருக்கக்கூடும், விண்வெளி சிக்கலானது பைனரி மரத்தில் உள்ள முனைகளின் எண்ணிக்கைக்கு சமமாக இருக்கும்.

1