پیمایش درخت، آموزش پیمایش درخت دودویی

برخلاف ساختمان دادهآموزش ساختمان داده و الگوریتمهر ساختمان داده یک نوع فرمت ذخیره‌سازی و مدیریت داده‌ها در کامپیوتر است، که امکان دسترسی و اصلاح کارآمد آن داده‌ها را برای یکسری از الگوریتم‌ها و کاربردها فراهم می‌کند، در این صفحه به بررسی و آموزش ساختمان داده و الگوریتم پرداخته شده است های خطی (آرایه، لیست پیوندی، صف، پشته، و غیره) که تنها یک راه منطقی برای پیمایش آنها وجود دارند، درختان را می‌توان به روش‌های مختلف پیمایش کرد. در این مقاله ما به بررسی انواع این پیمایش‌ها و نحوه پیاده‌سازی آن‌ها می‌پردازیم.

انواع پیمایش درخت

پیمایش اول عمق یا DFSالگوریتم جستجوی اول عمق ⚡️ آموزش الگوریتم dfs گرافدر این مقاله عالی الگوریتم جستجوی اول عمق بررسی و الگوریتم dfs گراف آموزش داده شده و مثال ها و پیاده سازی و کاربردهای الگوریتم جستجوی اول (DFS) عمق بیان شده
- پیمایش Inorder
- پیمایش Preorder
- پیمایش Postorder
پیمایش اول سطح یا جستجوی اول عرض یا الگوریتم BFS الگوریتم جستجوی اول سطح چیست؟ پیمایش سطحی (BFS) چیست؟این صفحه عالی الگوریتم جستجوی اول سطح یا همان پیمایش سطحی (BFS) را آموزش داده و پیاده سازی، پیچیدگی زمانی، مکانی و کاربردهای الگوریتم جستجوی اول سطح را گفته

ما در این مقاله به بررسی انواع پیمایش اول عمق می‌پردازیم.

پیمایش Inorder

در این روش پیمایش ابتدا زیر درخت سمت چپ و سپس ریشه و بعداً زیر درخت سمت راست بازدید می‌شود. همیشه باید به یاد داشته باشیم که هر گره ممکن است خودش ریشه یک زیر درخت باشد.اگر یک درخت باینری به ترتیب Inorder پیمایش شود، خروجی، مقادیر کلید مرتب شده را به ترتیب صعودی تولید می‌کند. الگوریتمآموزش طراحی الگوریتم به زبان سادهدرس طراحی الگوریتم‌ یکی از مهم‌ترین و بنیادیترین دروس‌ رشته کامپیوتر است. هدف از این درس، معرفی روش‌های مختلف طراحی الگوریتم‌ها برای حل مسائل گوناگون است، در این صفحه به معرفی و آموزش طراحی الگوریتم پرداخته شده است. پیمایش Inorder یا میان ترتیب به شکل زیر است:

مرحله 1: به‌صورت بازگشتیتوضیح تابع بازگشتی، دنباله بازگشتی و رابطه بازگشتیاین صفحه عالی به توضیح تابع بازگشتی و دنباله بازگشتی و رابطه بازگشتی پرداخته و توضیح داده تابع بازگشتی چیست و چگونه کار می کند و کاربرد توابع بازگشتی را گفته زیر درخت سمت چپ را پیمایش کنید.
مرحله 2: گره ریشه را بازدید کنید.
مرحله 3: به‌صورت بازگشتی زیر درخت سمت راست را پیمایش کنید.

برای مثال درخت زیر را در نظر بگیرید:

از A شروع می‌کنیم و با پیمایش Inorder به زیر درخت سمت چپ آن حرکت می‌کنیم یعنی B.B نیز به ترتیب Inorder پیمایش می‌شود. این فرایند تا زمانی ادامه می‌یابد که تمام گره‌ها بازدید شوند. خروجی پیمایش Inorder این درخت به این شکل خواهد بود:

D → B → E → A → F → C → G

کد پیمایش Inorder به‌صورت زیر است:

#include <bits/stdc++.h>
using namespace std;
// A binary tree node has data, pointer to left child
// and a pointer to right child
struct Node {
    int data;
    struct Node *left, *right;
};
// Utility function to create a new tree node
Node* newNode(int data)
{
    Node* temp = new Node;
    temp->data = data;
    temp->left = temp->right = NULL;
    return temp;
}
// Given a binary tree, print its nodes in inorder
void printInorder(struct Node* node)
{
    if (node == NULL)
        return;
    // First recur on left child
    printInorder(node->left);
    // Then print the data of node
    cout <data << " ";
    // Now recur on right child
    printInorder(node->right);
}
// Driver code
int main()
{
    struct Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    // Function call
    cout <<"Inorder traversal of binary tree is \n";
    printInorder(root);
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
// A binary tree node has data, pointer to left child
// and a pointer to right child
struct Node {
    int data;
    struct Node *left, *right;
};
// Utility function to create a new tree node
Node* newNode(int data)
{
    Node* temp = new Node;
    temp->data = data;
    temp->left = temp->right = NULL;
    return temp;
}
// Given a binary tree, print its nodes in inorder
void printInorder(struct Node* node)
{
    if (node == NULL)
        return;
    // First recur on left child
    printInorder(node->left);
    // Then print the data of node
    cout <data << " ";
    // Now recur on right child
    printInorder(node->right);
}
// Driver code
int main()
{
    struct Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    // Function call
    cout <<"Inorder traversal of binary tree is \n";
    printInorder(root);
    return 0;
}

پیمایش Preorder

در این روش پیمایش ابتدا گره ریشه و سپس زیر درخت سمت چپ و در نهایت زیر درخت سمت راست بازدید می‌شود. الگوریتم پیمایش Preorder یا پیش ترتیب به شکل زیر است:

مرحله 1: از گره ریشه بازدید کنید.
مرحله 2: به‌صورت بازگشتی زیر درخت سمت چپ را پیمایش کنید.
مرحله 3: به‌صورت بازگشتی زیر درخت سمت راست را پیمایش کنید.

برای مثال درخت زیر را در نظر بگیرید:

از A شروع می‌کنیم و با پیمایش پیش ترتیب، ابتدا از خود A بازدید می‌کنیم و سپس به زیر درخت سمت چپ آن یعنی B می‌رویم. B نیز به‌صورت پیش ترتیب پیمایش می‌شود. این فرایند تا زمانی ادامه می‌یابد که تمام گره‌ها بازدید شوند. خروجی پیمایش پیش‌ ترتیب این درخت به شکل زیر خواهد بود:

A → B → D → E → C → F → G

کد پیمایش Preorder به‌صورت زیر است:

#include <bits/stdc++.h>
using namespace std;
// A binary tree node has data, pointer to left child
// and a pointer to right child
struct Node {
    int data;
    struct Node *left, *right;
};
// Utility function to create a new tree node
Node* newNode(int data)
{
    Node* temp = new Node;
    temp->data = data;
    temp->left = temp->right = NULL;
    return temp;
}
// Given a binary tree, print its nodes in preorder
void printPreorder(struct Node* node)
{
    if (node == NULL)
        return;
    // First print data of node
    cout << node->data << " ";
    // Then recur on left subtree
    printPreorder(node->left);
    // Now recur on right subtree
    printPreorder(node->right);
}
// Driver code
int main()
{
    struct Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    // Function call
    cout << "Preorder traversal of binary tree is \n";
    printPreorder(root);
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
// A binary tree node has data, pointer to left child
// and a pointer to right child
struct Node {
    int data;
    struct Node *left, *right;
};
// Utility function to create a new tree node
Node* newNode(int data)
{
    Node* temp = new Node;
    temp->data = data;
    temp->left = temp->right = NULL;
    return temp;
}
// Given a binary tree, print its nodes in preorder
void printPreorder(struct Node* node)
{
    if (node == NULL)
        return;
    // First print data of node
    cout << node->data << " ";
    // Then recur on left subtree
    printPreorder(node->left);
    // Now recur on right subtree
    printPreorder(node->right);
}
// Driver code
int main()
{
    struct Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    // Function call
    cout << "Preorder traversal of binary tree is \n";
    printPreorder(root);
    return 0;
}

پیمایش Postorder

در این روش پیمایش، همان‌طور که از نامش پیداست گره ریشه در آخر بازدید می‌شود. ابتدا زیر درخت سمت چپ، سپس زیر درخت سمت راست و در نهایت گره ریشه را پیمایش می‌کنیم. الگوریتم پیمایش Postorder یا پس ترتیب به شکل زیر است:

مرحله 1: به‌صورت بازگشتی زیر درخت سمت چپ را پیمایش کنید.
مرحله 2: به‌صورت بازگشتی زیر درخت سمت راست را پیمایش کنید.
مرحله 3: از گره ریشه بازدید کنید.

برای مثال درخت زیر را در نظر بگیرید:

از A شروع می‌کنیم و پس از پیمایش پس ترتیب، ابتدا از زیر درخت سمت چپ یعنی B دیدن می‌کنیم. B نیز به‌صورت پس ترتیب پیمایش می‌شود. این فرایند تا زمانی ادامه می‌یابد که تمام گره‌ها بازدید شوند. خروجی پیمایش پس ترتیب این درخت به شکل زیر خواهد بود:

D → E → B → F → G → C → A

کد پیمایش Postorder به‌صورت زیر است:


using namespace std;
// A binary tree node has data, pointer to left child
// and a pointer to right child
struct Node {
    int data;
    struct Node *left, *right;
};
// Utility function to create a new tree node
Node* newNode(int data)
{
    Node* temp = new Node;
    temp->data = data;
    temp->left = temp->right = NULL;
    return temp;
}
// Given a binary tree, print its nodes according to the
// "bottom-up" postorder traversal.
void printPostorder(struct Node* node)
{
    if (node == NULL)
        return;
    // First recur on left subtree
    printPostorder(node->left);
    // Then recur on right subtree
    printPostorder(node->right);
    // Now deal with the node
    cout << node->data << " ";
}
// Driver code
int main()
{
    struct Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    // Function call
    cout << "Postorder traversal of binary tree is \n";
    printPostorder(root);
    return 0;
}

using namespace std;
// A binary tree node has data, pointer to left child
// and a pointer to right child
struct Node {
    int data;
    struct Node *left, *right;
};
// Utility function to create a new tree node
Node* newNode(int data)
{
    Node* temp = new Node;
    temp->data = data;
    temp->left = temp->right = NULL;
    return temp;
}
// Given a binary tree, print its nodes according to the
// "bottom-up" postorder traversal.
void printPostorder(struct Node* node)
{
    if (node == NULL)
        return;
    // First recur on left subtree
    printPostorder(node->left);
    // Then recur on right subtree
    printPostorder(node->right);
    // Now deal with the node
    cout << node->data << " ";
}
// Driver code
int main()
{
    struct Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    // Function call
    cout << "Postorder traversal of binary tree is \n";
    printPostorder(root);
    return 0;
}

پیمایش سطحی

در این روش پیمایش، همان‌طور که از نامش پیداست گره‌ها به‌صورت سطح به سطح ویزیت می‌شوند. ابتدا یک گره سمت چپ کمترین سطح شروع می‌کنیم و پس از ویزیت‌کردن تمام گره‌های آن سطح به سطح بعدی می‌رویم. الگوریتم پیمایش سطحی به شکل زیر است:

مرحله 1: از گره با کمترین سطح شروع کنید.
مرحله 2: تمام گره‌های آن سطح را طی کنید.
مرحله 3: به سطح بعدی بروید و دوباره مرحله 1 را تکرار کنید.

برای مثال درخت زیر را در نظر بگیرید:

در این درخت از گره A شروع می‌کنیم و پس از ویزیت‌کردن آن به سطح بعدی می‌رویم و گره‌های B و C را به ترتیب ویزیت می‌کنیم. سپس در سطح بعدی 4 گره باقی‌مانده را به ترتیب ویزیت می‌کنیم.

کد پیمایش سطحی به شکل زیر است:


#include 
// A binary tree node has data,
// pointer to left child
// and a pointer to right child
struct node
{
    int data;
    struct node *left, *right;
};
// Function prototypes
void printCurrentLevel(struct node *root, int level);
int height(struct node *node);
struct node *newNode(int data);
// Function to print level order traversal a tree
void printLevelOrder(struct node *root)
{
    int h = height(root);
    int i;
    for (i = 1; i <= h; i++) printCurrentLevel(root, i); } // Print nodes at a current level void printCurrentLevel(struct node *root, int level) { if (root == NULL) return; if (level == 1) printf("%d ", root->data);
    else if (level > 1)
    {
        printCurrentLevel(root->left, level - 1);
        printCurrentLevel(root->right, level - 1);
    }
}
// Compute the "height" of a tree -- the number of
// nodes along the longest path from the root node
// down to the farthest leaf node
int height(struct node *node)
{
    if (node == NULL)
        return 0;
    else
    {
        // Compute the height of each subtree
        int lheight = height(node->left);
        int rheight = height(node->right);
        // Use the larger one
        if (lheight > rheight)
            return (lheight + 1);
        else
            return (rheight + 1);
    }
}
// Helper function that allocates a new node with the
// given data and NULL left and right pointers.
struct node *newNode(int data)
{
    struct node *node = (struct node *)malloc(sizeof(struct node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return (node);
}
// Driver program to test above functions
int main()
{
    struct node *root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    printf("Level Order traversal of binary tree is \n");
    printLevelOrder(root);
    return 0;
}

#include 
// A binary tree node has data,
// pointer to left child
// and a pointer to right child
struct node
{
    int data;
    struct node *left, *right;
};
// Function prototypes
void printCurrentLevel(struct node *root, int level);
int height(struct node *node);
struct node *newNode(int data);
// Function to print level order traversal a tree
void printLevelOrder(struct node *root)
{
    int h = height(root);
    int i;
    for (i = 1; i <= h; i++) printCurrentLevel(root, i); } // Print nodes at a current level void printCurrentLevel(struct node *root, int level) { if (root == NULL) return; if (level == 1) printf("%d ", root->data);
    else if (level > 1)
    {
        printCurrentLevel(root->left, level - 1);
        printCurrentLevel(root->right, level - 1);
    }
}
// Compute the "height" of a tree -- the number of
// nodes along the longest path from the root node
// down to the farthest leaf node
int height(struct node *node)
{
    if (node == NULL)
        return 0;
    else
    {
        // Compute the height of each subtree
        int lheight = height(node->left);
        int rheight = height(node->right);
        // Use the larger one
        if (lheight > rheight)
            return (lheight + 1);
        else
            return (rheight + 1);
    }
}
// Helper function that allocates a new node with the
// given data and NULL left and right pointers.
struct node *newNode(int data)
{
    struct node *node = (struct node *)malloc(sizeof(struct node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return (node);
}
// Driver program to test above functions
int main()
{
    struct node *root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    printf("Level Order traversal of binary tree is \n");
    printLevelOrder(root);
    return 0;
}

کاربردهای پیمایش درخت

پیمایش پیش‌ ترتیب را می‌توان برای ساخت یک عبارت پیشوندی (نشان‌گذاری لهستانی) از درخت‌ های بیان استفاده کرد. به‌عنوان‌مثال، پیمایش عبارت حسابی نشان‌داده‌شده در پیش ترتیب، "+ * A − B C + D E" را می‌دهد. در نمادگذاری پیشوندی، تا زمانی که هر عملگر دارای تعداد ثابت عملوند باشد، نیازی به پرانتز نیست. پیمایش پیش‌ ترتیب برای ایجاد یک کپی از درخت نیز استفاده می‌شود.

پیمایش پس ترتیب می‌تواند یک نمایش پسوند (نشان‌گذاری معکوس لهستانی) از یک درخت دودویی ایجاد کند. با پیمایش عبارت حسابی نشان‌داده‌شده به‌صورت پس ترتیب "A B C − * D E + +" به دست می‌آید. دومی را می‌توان به‌راحتی به کد ماشین برای ارزیابی عبارت توسط یک ماشین پشته‌ای تبدیل کرد. پیمایش پس ترتیب برای حذف درخت هم استفاده می‌شود. هر گره پس از آزادکردن فرزندان خود آزاد می‌شود.

پیمایش میان ترتیب معمولاً در درخت‌ های جستجوی باینری استفاده می‌شود، زیرا طبق مقایسه‌کننده‌ای که درخت جستجوی باینری را تنظیم کرده است، مقادیر را از مجموعه عناصر موجود در درخت به‌صورت مرتب شده برمی‌گرداند.

جمع‌بندی

پیمایش درخت یک تکنیک حیاتی برای کار با ساختمان داده درخت است. در این مقاله انواع روش های پیمایش درخت مانند پیمایش پیش ترتیب، پیمایش میان ترتیب و پیمایش پس ترتیب را بررسی کردیم. همچنین بحث کردیم که چگونه می توان از پیمایش درخت برای حل الگوریتم های مختلف و مسائل علوم کامپیوتر استفاده کرد. علاوه بر این، نمونه های پیاده سازی را در زبان برنامه نویسی C++‎برنامه نویسی سی پلاس پلاس چیست؟ مزایای برنامه نویسی C++‎؟برنامه نویسی سی پلاس پلاس چیست و چه کاربردی دارد؟ این صفحه عالی به بررسی مزایای برنامه نویسی C++ پرداخته و نمونه هایی از کدهای زبان برنامه نویسی ++C را آورده ارائه کردیم.

پیمایش درخت چیست؟

در علوم کامپیوتر، پیمایش درخت (که به‌عنوان جستجوی درخت نیز شناخته می‌شود) شکلی از پیمایش گرافگراف چیست، آموزش گراف از 0 تا 100 توسط دانشجو ارشد صنعتی شریفدر این مقاله تمامی مطالب مربوط به گراف از 0 تا 100 تدریس شده است. مواردی همچون : گراف چیست؟ انواع گراف، گراف همبند، مکمل گراف،‌ گراف کامل، گراف جهت دار، گراف بدون جهت،‌ گراف ساده و ... است و به فرایند بازدید (به‌عنوان‌مثال بازیابی، به‌روزرسانی یا حذف) هر گره در ساختمان داده درخت که هر گره دقیقاً یک‌بار بازدید می‌شود اشاره دارد. چنین پیمایش‌هایی بر اساس ترتیب بازدید از گره‌ها طبقه‌بندی می‌شوند.

پیمایش DFS درخت چیست؟

جستجوی اول عمق (DFS) روشی برای کاوش یک درخت یا گراف است. در یک DFS، قبل از پشتیبان‌گیری و امتحان مسیر دیگری، تاحدامکان در یک مسیر عمیق می‌رویم.

چگونه یک درخت را پیمایش می‌کنند؟

در پیمایش میان ترتیب درخت، ابتدا از زیر درخت سمت چپ و به دنبال آن گره ریشه و در نهایت زیر درخت سمت راست بازدید می‌کنیم. این پیمایش به طور گسترده در BSTها استفاده می‌شود. در پیمایش پیش ترتیب درخت، از ریشه به زیر درخت سمت چپ و سپس به زیر درخت سمت راست پیمایش می‌کنیم. این نوع پیمایش در ایجاد عبارات پیشوندی از درخت بیان یا برای کپی‌کردن یک درخت استفاده می‌شود. در پیمایش پس ترتیب درخت، از زیر درخت سمت چپ به زیر درخت سمت راست و سپس به ریشه پیمایش می‌کنیم. این نوع پیمایش در حذف درختان و تولید عبارات پسوندی در درختان باینری مفید است.

تفاوت پیمایش DFS و BFS چیست؟

BFS یک رویکرد پیمایشی است که در آن ابتدا از تمام گره‌ها در یک سطح عبور می‌کنیم و سپس به سطح بعدی می‌رویم. در مقابل DFS یک رویکرد پیمایشی است که در آن پیمایش از گره ریشه شروع می‌شود و تا آنجا که ممکن است از طریق گره‌ها ادامه می‌یابد تا زمانی که به گره‌ای برسیم که هیچ گره مجاور بازدید نشده‌ای ندارد.

تفاوت بین جستجو و پیمایش چیست؟

پیمایش یک درخت شامل بررسی هر گره در درخت است. جستجو شامل بازدید سیستماتیک گره‌ها در یک درخت یا گراف است و ممکن است منجر به بازدید از همه گره‌ها بشود یا نشود.