Эки дарактын кайталанып кетүүчү инерардык өтүшү


Кыйынчылык деңгээли орто
Binary Tree Tree Traversal

"Эки дарактын кайталануучу инеректордук өтүшү" маселесинде бизге а экилик дарак. Биз аны жөнөкөй эмес жол менен өтүшүбүз керек "Кайталоо", рекурсиясыз.

мисал

                 2

              /     \

            1         3

          /   \

        4       5                

4 1 5 2 3
           1 
 
         /    \

       2        3

     /            \

    4               6

                      \

                        7

4 2 1 3 6 7

Algorithm

  1. Өзгөрүлмө инициализациялоо “CurNode” экилик дарактын тамыры катары
  2. Бош стекти баштоо, түйүндөрдү камтыган алар басып өткөндөй
  3. Стек бош болбогонго чейин же төмөнкүнү аткарыңыз curNode болуп калган жок НӨЛ:
    • жатканда curNode is жок НӨЛ:
      1. түртүү curNode үймөккө
      2. Учурдагы түйүндү катары өзгөртүп, эң сол жактагы балага бара бериңиз curNode = curNode-> сол
    • Азыр, стектин үстүңкү түйүнү учурдагы субтриттин сол жактагы түйүнү, ошондуктан стекдеги жогорку түйүндүн маанисин басып чыгарабыз
    • дайындоо curNode сыяктуу эле, стекдеги жогорку түйүндүн туура баласы катары curNode = stack.top () -> right 
    • Учурдагы түйүндү катары өзгөртүп, эң сол жактагы балага бара бериңиз curNode = curNode-> сол бул эң сол түйүндүн оң субтриетин иштетүү
    • Стекти ачып, элементти ачыңыз

түшүндүрүү

Программада стек кошулган эң акыркы элемент пайда болот деген идеяны колдонот, Жогоруда түшүндүрүлгөн алгоритмде, эгер биз учурдагы түйүн болсо (башында бул дарак) сол баласы бар болсо, андан кийин дагы сол балдары калмайынча, сол баласын үймөктө түртүп жатабыз.

Эгерде учурдагы түйүндүн сол баласы жок болуп калса, анда стектин үстүңкү түйүнү "Акыркы сол жактагы түйүн" кошумчалады. Демек, өтүү калган тартипте биринчи орунда турушу керек. Ошентип, биз басып чыгаруу / буйрук тизмесине кошуу жана стекден чыгып, аны башталат. Бир жолу жасалып бүткөндөн кийин, азыр Left-curNode-Right (inorder ырааттуулугу), Left жана Node бөлүгү өтүп жатат. Ошентип, түйүндүн оң субтрагы процессте!

Интуитивдүү түрдө, биз ушул эле процессти учурдагы түйүндүн оң жактагы дарагына колдонууну каалагандыктан, аны төмөнкүчө жалпылай алабыз: curNode = curNode-> оң.

Эки дарактын кайталанып кетүүчү инерардык өтүшү

ишке ашыруу

Эки даракты кайталап жүрүүчү Inorder Traversal программасынын C ++ программасы

#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). Дарак кыйшайып кетиши мүмкүн болгон эң жаман учурду эске алганда, космостогу татаалдык экилик дарактын түйүндөрүнүн санына барабар болот.