Екілік ағаштың қайталанбалы инерарлы траверсалы


Күрделілік дәрежесі орта
Екілік ағаш Ағаштарды кесу

«Екілік ағаштың қайталанатын инераторлық траекториясы» есебінде бізге а екілік ағаш. Біз оны беймәлім қалыпта өтуіміз керек «Қайталанбалы», рекурсиясыз.

мысал

                 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 болмады ЖОҚ:
    • уақыт curNode is емес ЖОҚ:
      1. Басыңыз curNode үйіндіге
      2. Ағымдағы түйінді өзгерту арқылы сол жақтағы балаға қарай жүріңіз curNode = curNode-> сол жақта
    • Енді стектегі жоғарғы түйін - қазіргі ішкі ағаштың сол жақтағы түйіні, сондықтан стектің жоғарғы түйінінің мәнін басып шығарамыз
    • Берілсін curNode стектегі жоғарғы түйіннің дұрыс баласы ретінде curNode = stack.top () -> оң жақ 
    • Ағымдағы түйінді өзгерту арқылы сол жақтағы балаға қарай жүріңіз curNode = curNode-> сол жақта осы сол жақ түйіннің оң жақ субтретін өңдеу үшін
    • Стек ішінен элементті шығарыңыз

Түсіндіру

Бағдарлама стекке ең соңғы қосылған элементті шығарады деген идеяны қолданады, жоғарыда түсіндірілген алгоритмде біз жай түйін (егер ол бастапқыда ағаш) егер сол баласы болса, сол жақта қалған балалары қалмағанша, біз оның сол баласын үйіндіге итере береміз.

Ағымдағы түйіннің сол жақ пернесі болмайтындай жағдай туындаған кезде, стектің жоғарғы түйіні «Жақындағы ең сол жақ түйін» қосылды. Сонымен, ол жүрудің қалған тәртібінде бірінші орында тұруы керек. Сонымен, біз оны басып шығаруды бастаймыз / тапсырыс тізіміне қосамыз және оны стектен шығарамыз. Жасалғаннан кейін біз қазір нақты екенімізді анықтаймыз Солға-бұрауТүйін-Оңға (инерциялық рет), Солға және Node бөлігі өтіп жатыр. Сонымен, түйіннің оң ішкі ағашы процесте!

Біз интуитивті түрде, дәл сол процесті ағымдағы түйіннің оң жақ ағашына қолданғымыз келетіндіктен, оны келесідей қорыта аламыз: 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 

Екілік ағашты итеративті инерарлы траверстің Java бағдарламасы

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). Ағаш қисық бола алатын ең нашар жағдайды ескере отырып, кеңістіктің күрделілігі екілік ағаштағы түйіндер санына тең болады.