Tree Traversal (สั่งซื้อล่วงหน้า, Inorder & Postorder)


ระดับความยาก สะดวกสบาย
ถามบ่อยใน อะโดบี อเมซอน MAQ คำพยากรณ์ Snapdeal
ต้นไม้ไบนารี ต้นไม้ ทรีทราเวอร์ซัล

ขั้นแรกเราต้องรู้เกี่ยวกับ Traversal ใน Binary Tree คืออะไร. Traversal เป็นวิธีการประเภทหนึ่งที่เราเข้าไปที่โหนดทั้งหมดหนึ่งครั้งในลักษณะ / คำสั่งเฉพาะบางอย่าง โดยทั่วไปมีสองประเภทของการส่งผ่านใน ต้นไม้ไบนารี:

เรารู้แล้วว่าไฟล์ แนวคิดของ BFS. ตอนนี้เราเห็นการส่งผ่าน Preorder, Inorder และ Postorder และการข้ามผ่านเหล่านี้เป็นส่วนหนึ่งของ DFS ของไบนารีทรี ดังนั้นเราจึงเห็นรายละเอียดประเภทต้นไม้ทั้งหมด:

Tree Traversal (สั่งซื้อล่วงหน้า, Inorder & Postorder)

สั่งซื้อล่วงหน้า

ในการส่งผ่านนี้เราจะพิมพ์ข้อมูลของโหนดปัจจุบันก่อนจากนั้นย้ายไปที่ทรีย่อยด้านซ้ายก่อนและหลังจากนั้นย้ายไปยังทรีย่อยด้านขวา การส่งผ่านคำสั่งซื้อล่วงหน้าของต้นไม้ไบนารีข้างต้นคือ 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 Traversal

ในการส่งผ่านนี้เราย้ายไปที่ทรีย่อยด้านซ้ายก่อนแล้วจึงพิมพ์ข้อมูลของโหนด หลังจากพิมพ์ข้อมูลของโหนดแล้วให้ย้ายไปที่แผนผังย่อยด้านขวา การข้ามตามลำดับของต้นไม้ไบนารีข้างต้นคือ 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 Traversal

ในการข้ามผ่านนี้เราย้ายไปที่ทรีย่อยด้านซ้ายก่อนจากนั้นย้ายไปยังทรีย่อยด้านขวา หลังจากย้ายพิมพ์ข้อมูลของโหนด การข้ามผ่านของลำดับหลังของต้นไม้ไบนารีข้างต้นคือ 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 คือจำนวนโหนดทั้งหมดที่มีอยู่ในต้นไม้ไบนารีที่กำหนด

อ้างอิง