Гузариши такрории пасандоз бо истифодаи ду стеллаж


Сатҳи душворӣ осон
Аксар вақт пурсида мешавад Adobe Amazon Factset Фуркайтҳо Пардохт
тӯда Дарахт

Изҳороти мушкилот

Масъалаи "Траверсати такрории пасандоз бо истифода аз ду стек" мегӯяд, ки ба шумо дарахти дуӣ бо гиреҳҳо дода мешавад. Бо истифода аз ду стек барномаеро барои гузариши постерии такроршаванда нависед.

Гузариши такрории пасандоз бо истифодаи ду стеллаж

мисол

вуруди

Гузариши такрории пасандоз бо истифодаи ду стеллаж

 

4 5 2 6 7 3 1

вуруди

 

4 2 3 1

Алгоритм

  1. Барои гиреҳ сохтори иборат аз аз ан ҳамаҷониба тағирёбанда барои нигоҳ доштани маълумот ва нишондиҳандаҳои ду гиреҳӣ аз чап ва рост.
  2. Пас аз он, функсияро барои эҷоди гиреҳи нав эҷод кунед, ки арзиши бутунро ҳамчун параметр қабул мекунад. Дар дохили он гиреҳ эҷод кунед. Арзиши бутуни ҳамчун параметр гузаштаро дар тағирёбандаи додаҳояш нигоҳ доред ва гиреҳи нишоннамои рост ва чапро бо сифр навсозӣ кунед. Гиреҳи навтаъсисро баргардонед.
  3. Ба ин монанд, барои такрор функсия эҷод кунед пас аз фармоиш ки нишондиҳандаро ба гиреҳи решаи дарахти дуӣ қабул мекунад. Тафтиш кунед, ки гиреҳи реша ба null баробар аст, баргардед.
  4. Ду созед яхдон маълумоти сохторҳои навъи Node * барои кумак дар гардиш.
  5. Гиреҳи решаро ба стака ворид кунед / дохил кунед 1. Гиреҳи нави дигаре эҷод кунед.
  6. Дар ҳоле ки стек 1 холӣ нест, яъне андозаи стек 1 ба 0 баробар нест. Гиреҳро дар болои стек 1 дар гиреҳи нав нигоҳ доред ва онро аз стек хориҷ кунед / хориҷ кунед. Гиреҳи хориҷшударо ба стек ворид кунед / дохил кунед 2. Санҷед, ки оё чапи гиреҳи кунунӣ мавҷуд аст, онро ба стек ворид кунед / дохил кунед. Ба ин монанд, санҷед, ки оё рости гиреҳ мавҷуд аст, онро ба стек 1 пахш кунед.
  7. Ҳангоме ки стек 1 холӣ нест, бори дигар гузаред, гиреҳро дар болои стек 1 дар стеки 2 нигоҳ доред ва онро аз стеки 1 кашед.
  8. Дар ниҳоят гиреҳи дуввумро чоп кунед.

рамз

Барномаи C ++ барои гузариши такрории пасандоз бо истифодаи ду стек

#include <bits/stdc++.h> 
using namespace std; 
  
struct Node{ 
    int data; 
    Node *left, *right; 
}; 
  
Node* newNode(int data){ 
    Node* node = new Node; 
    node->data = data; 
    node->left = node->right = NULL; 
    return node; 
} 

void postOrderIterative(Node* root){ 
    if(root == NULL){ 
        return; 
    }
  
    stack<Node *> s1, s2; 
  
    s1.push(root); 
    Node* node; 
  
    while(!s1.empty()){ 
        node = s1.top(); 
        s1.pop(); 
        s2.push(node); 
  
        if(node->left){ 
            s1.push(node->left);
        }
        if(node->right){ 
            s1.push(node->right);
        }
    } 
  
    while(!s2.empty()){ 
        node = s2.top(); 
        s2.pop(); 
        cout << node->data << " "; 
    } 
} 
  
int main(){ 
    Node* root = NULL; 
    root = newNode(1); 
    root->left = newNode(2); 
    root->right = newNode(3); 
    root->left->left = newNode(4); 
    root->left->right = newNode(5); 
    root->right->left = newNode(6); 
    root->right->right = newNode(7); 
  
    postOrderIterative(root); 
  
    return 0; 
}
4 5 2 6 7 3 1

Барномаи Java барои гузариши такрории пасандоз бо истифодаи ду стек

import java.util.*; 

class IterativePostorder{ 
  
    static class node{ 
        int data; 
        node left, right; 
  
        public node(int data){ 
            this.data = data; 
        } 
    } 
  
    static Stack<node> s1, s2; 
  
    static void postOrderIterative(node root){ 
        s1 = new Stack<>(); 
        s2 = new Stack<>(); 
  
        if(root == null){ 
            return; 
        }
  
        s1.push(root); 
  
        while(!s1.isEmpty()){ 
            node temp = s1.pop(); 
            s2.push(temp); 
  
            if(temp.left != null){ 
                s1.push(temp.left);
            }
            
            if(temp.right != null){ 
                s1.push(temp.right);
            }
        } 
  
        while(!s2.isEmpty()){ 
            node temp = s2.pop(); 
            System.out.print(temp.data + " "); 
        } 
    } 
  
    public static void main(String[] args){ 
        
        node root = null; 
        root = new node(1); 
        root.left = new node(2); 
        root.right = new node(3); 
        root.left.left = new node(4); 
        root.left.right = new node(5); 
        root.right.left = new node(6); 
        root.right.right = new node(7); 
  
        postOrderIterative(root); 
    } 
}
4 5 2 6 7 3 1

Таҳлили мураккабӣ

Мураккабии вақт

Эй (н) ки дар он n шумораи гиреҳҳо ҷойгир карда шудааст.

Мураккабии фазо

Эй (н) зеро мо барои n гиреҳ фазо истифода кардем.