Гузариши такрории Inorder дарахти дуӣ


Сатҳи душворӣ миёна
Дарахти дуӣ Траверсал дарахт

Дар масъалаи "Гузариши такрории иноративии дарахти дуӣ" ба мо а дарахти дуӣ. Мо бояд онро ба тарзи ғайримуқаррарӣ тай кунем "Такроршаванда", бе рекурсия.

мисол

                 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-> чап барои коркарди зердарахти рости ин гиреҳи чап
    • Элементро аз анбор берун кунед

Шарҳ

Барнома идеяро истифода мебарад, ки стака унсури охирини изофашударо мебарорад, Дар алгоритми дар боло шарҳдодашуда мо танҳо хулоса мебарорем, ки агар гиреҳи ҷорӣ (ки дар ибтидо решаи дарахт) кӯдаки чап дорад, пас мо фарзанди чапашро ба стек тела медиҳем, то вақте ки кӯдакони чап намонанд.

Вақте ки парванда чунин ба миён ояд, ки гиреҳи ҷорӣ фарзанди чап надошта бошад, маълум аст, ки гиреҳи болои стака "Гиреҳи охирини чап" илова кард. Пас, он бояд дар ҷои боқимондаи гардиш аввал бошад. Ҳамин тавр, мо ба чоп / илова кардани он ба рӯйхати фармоишҳо шурӯъ мекунем ва онро аз анбор мебарорем. Пас аз анҷом додан, мо ҳоло дар бораи он, ки дар Чап-curNode-Right (пайдарпаии inorder), чап ва Нод қисми он убур карда мешавад. Ҳамин тавр, зерсохтори рости гиреҳ ба раванд аст!

Беихтиёрона, азбаски мо мехоҳем худи ҳамон равандро ба зердарахти рости гиреҳи ҷорӣ татбиқ кунем, мо метавонем онро ба таври куллӣ ба таври куллӣ баён кунем: curNode = curNode-> рост.

Гузариши такрории Inorder дарахти дуӣ

татбиќи

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

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

Мураккабии вақт гузариши такрории иноридии дарахти дуӣ

Мураккабии вақт аст О (Н), вақте ки мо ба ҳар як гиреҳ маҳз як маротиба ташриф меорем. Дар ин ҷо, N шумораи гиреҳҳо дар дарахти дуӣ мебошад.

Мураккабии фазо гузариши такрории иноридии дарахти дуӣ

Мураккабии фазо дар он аст О (Н). Бо назардошти ҳолати бадтарин, ки дарахт метавонад каҷ бошад, мураккабии фазо ба шумораи гиреҳҳои дарахти дуӣ баробар хоҳад буд.