Гузариши дарахт (пешакӣ, иноридӣ ва фармоишӣ)


Сатҳи душворӣ осон
Аксар вақт пурсида мешавад Adobe Amazon MAQ Oracle Snapdeal
Дарахти дуӣ Дарахт Траверсал дарахт

Аввалан, мо бояд дар бораи он бидонем Траверсал дар дарахти дуӣ чӣ гуна аст. Траверсал як намуди усулест, ки дар он мо ба тамоми гиреҳҳо дақиқ як маротиба бо тартиби муайян / тартиби муайяне ташриф меорем. Асосан ду намуди гардиш вуҷуд дорад Дарахти дуӣ:

Мо аллакай медонем, ки чӣ маъно дорад консепсияи BFS. Ҳоло, мо убур кардани Preorder, Inorder ва Postorder-ро мебинем ва ин гузаришҳо қисми DFS дарахти дуӣ мебошанд. Ҳамин тавр, мо ҳама намуди дарахтонро ба таври муфассал мебинем:

Гузариши дарахт (пешакӣ, иноридӣ ва фармоиш)

Гузариши пешакӣ

Дар ин гардиш, мо аввал маълумоти гиреҳи ҷориро чоп карда, пас аввал ба зери дарахти чап ва баъд аз он ба зери дарахти рост ҳаракат мекунем. Гузариши пешакии дарахти дуӣ дар боло аст 0 1 3 4 2 5 6.

Алгоритм

Algorithm: 
Preorder(root): 
Step:1 Print the data of the Node. 
Step:2 Move to the left side of the node(traverse left-subtree). 
Step:3 Move to the right side of the node(traverse right-subtree).

Гузариши Inorder

Дар ин гардиш, мо аввал ба зери дарахти чап ҳаракат карда, баъд маълумоти гиреҳро чоп мекунем. Пас аз чоп кардани маълумоти гиреҳ ба зери дарахти рост ҳаракат кунед. Гузариши инордерии дарахти дуӣ дар боло аст 1 3 4 0 2 5 6.

Алгоритм

Algorithm:  
Inorder(root): 
Step:1 Move to the left side of the node(traverse left-subtree). 
Step:2 Print the data of the Node.  
Step:3 Move to the right side of the node(traverse right-subtree).

Гузариши Postorder

Дар ин гардиш, мо аввал ба зери дарахти чап ҳаракат мекунем ва сипас ба зери дарахти рост ҳаракат мекунем. Пас аз ҳаракат маълумоти гиреҳро чоп кунед. Гузариши пас аз дарахти дуӣ дар боло аст 1 3 4 2 5 6 0.

Алгоритм

Algorithm: 
Postorder(root): 
Step:1 Move to the left side of the node(traverse left-subtree). 
Step:2 Move to the right side of the node(traverse right-subtree). 
Step:3 Print the data of the Node.

татбиќи

/*C++ Implementation of print the Preorder, Inorder, Postorder traversal of given binary tree*/ 
#include<bits/stdc++.h> 
using namespace std; 
/*Structure of Node of BT which contain pointer to left child and right child and a data for node.*/
struct Node{
    int data;
    struct Node* left;// for left child;
    struct Node* right;// for right child;
    Node(int value)// create a node using new Node;
    {
        data=value;
        left=NULL;
        right=NULL;
    }
};
/*Function which print preorder of the given tree*/ 
void Preorder_tree(Node* root)
{
    if(root==NULL)
    {
        return;
    }
    cout<<root->data<<" ";
    Preorder_tree(root->left);
    Preorder_tree(root->right);
}
/*Function which print inorder of the given tree*/ 
void Inorder_tree(Node* root)
{
    if(root==NULL)
    {
        return;
    }
    Preorder_tree(root->left);
    cout<<root->data<<" ";
    Preorder_tree(root->right);
}
/*Function which print postorder of the given tree*/ 
void Postorder_tree(Node* root)
{
    if(root==NULL)
    {
        return;
    }
    Preorder_tree(root->left);
    Preorder_tree(root->right);
    cout<<root->data<<" ";
}
int main() 
{ 
    /*construct tree*/
    Node* root= new Node(0);//root node;
    root->left= new Node(1);
    root->right= new Node(2);
    root->left->left= new Node(3);
    root->left->right= new Node(4);
    root->right->left= new Node(5);
    root->right->right= new Node(6);
    cout<<"Preorder traversal of BT: ";
    Preorder_tree(root);cout<<"\n";
    cout<<"Inorder traversal of BT: ";
    Inorder_tree(root);cout<<"\n";
    cout<<"Postorder traversal of BT: ";
    Postorder_tree(root);cout<<"\n";
    return 0; 
}
Preorder traversal of BT: 0 1 3 4 2 5 6 
Inorder traversal of BT: 1 3 4 0 2 5 6 
Postorder traversal of BT: 1 3 4 2 5 6 0

Мураккабии вақт

О (Н) ки дар он N шумораи умумии гиреҳҳо дар дарахти додашудаи дуӣ мавҷуданд.

Адабиёт