Tree Traversal (Preorder, Inorder & Postorder)  


Кыйынчылык деңгээли жеңил
Көп суралган Adobe Amazon MAQ Oracle Snapdeal
Binary Tree дарак Tree Traversal

Биринчиден, биз жөнүндө билишибиз керек экилик дарактын ичинде Traversal деген эмне. Траверсал - бул биз бардык түйүндөргө бир жолу конкреттүү тартипте / тартипте баруучу методдун түрү. Негизинен эки түрлүү өтүү бар Binary Tree:

Деген эмне экендигин биз буга чейин эле билебиз BFS түшүнүгү. Азыр биз Preorder, Inorder жана Postorder өтүүлөрүн көрөбүз жана бул өтүүлөр экилик дарактын DFS бөлүгү болуп саналат. Ошентип, биз бардык дарактын түрүн толук көрөбүз:

Tree Traversal (Preorder, Inorder & Postorder)

Алдын ала буйрук  

Бул өтүүдө, биз алгач учурдагы түйүндүн маалыматтарын басып чыгарып, андан кийин биринчи сол терекке, андан кийин оң терекке жылдырабыз. Жогорудагы экилик дарактын алдын-ала өтүүсү 0 1 3 4 2 5 6.

Algorithm

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 Traversal  

Бул траверсалда алгач сол терекке өтүп, андан соң түйүндүн маалыматтарын басып чыгарабыз. Түйүндүн маалыматтарын басып чыгаргандан кийин оң жактагы даракка өтүңүз. Жогорудагы экилик дарактын инерардык өтүшү болуп саналат 1 3 4 0 2 5 6.

Algorithm

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 Traversal  

Бул траверсалда биринчи сол терекке өтүп, андан кийин оң терекке өтөбүз. Түйүндүн маалыматтарын басып чыгаргандан кийин. Жогоруда көрсөтүлгөн экилик дарактын постерден өтүшү 1 3 4 2 5 6 0.

ошондой эле
Изоморфтуу кылдар Leetcode чечими

Algorithm

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

Убакыт татаалдыгы  

O (N) мында N - берилген бинардык даракта жайгашкан түйүндөрдүн жалпы саны.

шилтемелер