Verilmiş bir ikili ağac düyününün atalarını rekursiya olmadan çap edin

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Akkolit Amazon Fourkites
Qalaq Ağac Ağacın keçidiBaxılıb 32

İkili bir ağac və müəyyən bir düyün və ya açar verilmişdir. Verilmiş əcdadları çap edin ikili ağac rekursiya olmadan düyün.

Verilmiş bir ikili ağac düyününün atalarını rekursiya olmadan çap edinPin

misal

Giriş:

açar = 7

Verilmiş bir ikili ağac düyününün atalarını rekursiya olmadan çap edinPin

Çıxış: 3 1

Giriş:

açar = 4

Verilmiş bir ikili ağac düyününün atalarını rekursiya olmadan çap edinPin

Çıxış: 2 1

Verilmiş ikili ağac düyününün ataları üçün alqoritm

  1. Verilənləri tutmaq üçün tam bir dəyişən və solda və sağda iki Node tipli obyekt olan bir sinif Node yaradın. İçində bir parametr olduğu üçün bir tam ədədi qəbul edən parametrləşdirilmiş konstruktor yaradın və onu sinif düyününün tam dəyişənində saxlayın.
  2. Bundan sonra, ağacın kök düyünü və açarı bir parametr kimi qəbul edən verilən düymənin əcdadlarını yazdırmaq üçün bir funksiya yaradın.
  3. Kökün null-a bərabər olub olmadığını yoxlayın, qayıdın. Başqa bir növü node bir yığın məlumat strukturu yaratmaq.
  4. Verilən ikili sürüşməyə başlayın ağac.
  5. Kök null-a bərabər deyilsə və kökün məlumatları verilmiş düyməyə bərabər deyilsə, kökü yığında itələyin və kökü kökdən solda yeniləyin.
  6. Kök null-a bərabər deyilsə və kökün məlumatları verilən düyməyə bərabərdirsə, döngəni pozun.
  7. Yığın yuxarı hissəsindəki qovşağın sağ hissəsi sıfıra bərabərdirsə, yığının üst hissəsindəki kökü yeniləyin və yığının üst hissəsini açın. Yığın boş deyil və yığının üstündəki qovşağın sağ kökünə bərabər olsa da, yığının üstündəki düyündəki kökü yeniləyin və üst hissəsini açın qalaq.
  8. Yığın boşdursa, kökü sıfır kimi yeniləyin, yığını yuxarıdakı düyünün sağ hissəsi kimi kökü yeniləyin.
  9. Yığın boş olmasa da, yığının üstündəki qovşaqdakı məlumatları çap edin və yığının üst hissəsini açın.

Verilmiş İkili Ağac Nodunun əcdadları üçün C ++ Proqramı

#include <bits/stdc++.h> 
using namespace std; 
  
struct Node{ 
    int data; 
    struct Node *left, *right; 
}; 
  
struct Node* newNode(int data){ 
    struct Node* node = (struct Node*) malloc(sizeof(struct Node)); 
    node->data = data; 
    node->left = node->right = NULL; 
    return node; 
} 
  
void printAncestors(struct Node *root, int key){ 
    if(root == NULL){ 
        return; 
    }
  
    stack<struct Node* > st; 
  
    while(1){ 
        while(root && root->data != key){ 
            st.push(root);  
            root = root->left;
        } 
  
        if(root && root->data == key){ 
            break; 
        }
  
        if(st.top()->right == NULL){ 
            root = st.top(); 
            st.pop(); 
  
            while(!st.empty() && st.top()->right == root){ 
               root = st.top(); 
               st.pop(); 
            } 
        } 
  
        root = st.empty()? NULL: st.top()->right; 
    } 
  
    while(!st.empty()){ 
        cout<<st.top()->data<<" "; 
        st.pop(); 
    } 
} 
  
int main(){ 
    
    struct Node* 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); 
    
    int key = 7;
    
    printAncestors(root, key); 
  
    return 0; 
}
3 1

Verilmiş bir İkili Ağac Düyününün Ataları üçün Java Proqramı

import java.util.Stack; 
  
class findAncestors{ 
    
    static class Node{ 
        int data; 
        Node left,right; 
          
        Node(int data){ 
            this.data = data; 
        } 
    } 
      
    static void printAncestors(Node root,int key){ 
        if(root == null){ 
            return; 
        }
          
        Stack<Node> st = new Stack<>(); 
          
        while(true){ 
              
            while(root != null && root.data != key){ 
                st.push(root);   
                root = root.left;
            } 
              
            if(root != null && root.data == key){ 
                break; 
            }
              
            if(st.peek().right == null){ 
                root =st.peek(); 
                st.pop(); 
                  
                while( st.empty() == false && st.peek().right == root){ 
                    root = st.peek(); 
                    st.pop(); 
                } 
            } 
              
            root = st.empty() ? null : st.peek().right; 
        } 
          
        while(!st.empty()){ 
            System.out.print(st.peek().data+" "); 
            st.pop(); 
        } 
    } 
      
    public static void main(String[] args){ 
         
        Node 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); 
        
        int key = 7;
        
        printAncestors(root, key); 
    } 
  
}
3 1

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi: O (n), burada n daxil edilmiş qovşaq sayıdır.

Kosmik Mürəkkəblik: O (n), çünki n qovşaq üçün yer istifadə etdik.

References

Translate »