Берілген екілік ағаш түйінінің ата-бабаларын рекурсиясыз басып шығарыңыз


Күрделілік дәрежесі орта
Жиі кіреді Акколит Amazon Фуркиттер
үйме ағаш Ағаштарды кесу

Екілік ағаш және нақты түйін немесе кілт берілген. Берілгеннің ата-бабаларын басып шығарыңыз екілік ағаш рекурсиясыз түйін.

Берілген екілік ағаш түйінінің ата-бабаларын рекурсиясыз басып шығарыңыз

мысал

Кіріс:

кілт = 7

Берілген екілік ағаш түйінінің ата-бабаларын рекурсиясыз басып шығарыңыз

Шығару: 3 1

Кіріс:

кілт = 4

Берілген екілік ағаш түйінінің ата-бабаларын рекурсиясыз басып шығарыңыз

Шығару: 2 1

Берілген екілік ағаш түйінінің ата-бабаларына арналған алгоритм

  1. Деректерді ұстауға арналған бүтін айнымалы және сол және оң жақ түйін типіндегі екі объектіден тұратын Түйін класын жасаңыз. Оның ішінде бүтін мәнді қабылдайтын параметрленген конструкторды құрыңыз және оны класс түйінінің бүтін айнымалысында сақтаңыз.
  2. Осыдан кейін ағаштың түбірлік түйінін және параметр ретінде кілтті қабылдайтын берілген кілттің ата-бабаларын басып шығару функциясын жасаңыз.
  3. Түбір нөлге тең екендігін тексеріңіз, қайтарыңыз. Басқасы типті түйіннің стек деректер құрылымын жасайды.
  4. Берілген екіліктерден өтуді бастаңыз ағаш.
  5. Түбір нөлге тең емес, ал түбірдің мәліметтері берілген кілтке тең емес болса, түбірді стекке итеріп, түбірді сол жақта жаңартыңыз.
  6. Егер түбір нөлге тең болмаса, түбірдің мәліметтері берілген кілтке тең болса, циклды бұзыңыз.
  7. Басқа жағдайда, егер стектің жоғарғы жағындағы түйіннің оң жағы нөлге тең болса, стектің жоғарғы жағындағы түйінді жаңартып, стектің жоғарғы жағын ашыңыз. Стек бос емес, ал стектің жоғарғы жағындағы түйіннің оң жағы түбірге тең болған кезде, стектің жоғарғы жағындағы түйіндегі түбірді жаңартып, жоғарғы бөлігін ашыңыз Стек.
  8. Егер стек бос болса, түбірді нөл ретінде жаңартыңыз, әйтпесе түбірді стектің жоғарғы жағындағы түйіннің оң жағынан жаңартыңыз.
  9. Стек бос болмаса да, түйіннің деректерін стектің жоғарғы жағында басып шығарып, стектің жоғарғы жағын ашыңыз.

Берілген екілік ағаш түйінінің ата-бабаларына арналған C ++ бағдарламасы

#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

Берілген екілік ағаш түйінінің ата-бабаларына арналған Java бағдарламасы

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

Күрделілікті талдау

Уақыттың күрделілігі: O (n), мұндағы n - енгізілген түйіндер саны.

Ғарыштың күрделілігі: O (n), өйткені біз n түйіндері үшін кеңістікті пайдаландық.

Әдебиеттер тізімі