مرتب‌سازی درختی در سی پلاس پلاس (Tree Sort)

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

پیش‌نیازهای این آموزش در زیر آورده شده است:

مرتب‌سازی درختی در سی پلاس پلاس

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

عناصر ورودی را در آرایه وارد کنید.
با وارد کردن داده های آرایه در درخت جستجوی دودویی، یک درخت جستجوی دودویی تشکیل دهید.
بر روی درخت جستجوی دودویی پیمایش میان ترتیب اجرا کنید تا عناصر مرتب شوند.

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

پیاده‌سازی مرتب‌سازی درختی در سی پلاس پلاس

همانطور که در قسمت قبل توضیح داده شد ابتدا باید درخت دودویی جستجو را ایجاد کنیم سپس بر روی درخت پیمایش میان ترتیب را پیاده‌سازی کنیم. در آموزش‌های گذشته در مورد پیاده‌سازی درخت دودویی جستجو توضیح داده شده است از همین رو در این قسمت در مورد پیاده سازی درخت دودویی جستجو صحبت نمی‌کنیم.

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

struct Node {

    int key;

    struct Node *left, *right;

};



struct Node *newNode(int item) {

    struct Node *temp = new Node;

    temp->key = item;

    temp->left = temp->right = NULL;

    return temp;

}



void Print(Node *root, int &i) {

    if (root != NULL) {

         Print(root->left, i);

         cout << root->key << " ";

         Print(root->right, i);

    }

}



Node* insert(Node* node, int key) {

    if (node == NULL)

         return newNode(key);



    if (key < node->key)

         node->left = insert(node->left, key);

    else if (key > node->key)

         node->right = insert(node->right, key);



    return node;

}



void treeSort(int arr[], int n) {

    struct Node *root = NULL;



    root = insert(root, arr[0]);

    for (int i = 1; i < n; i++)

         insert(root, arr[i]);



    int i = 0;

    Print(root, i);

}



int main() {

    int arr[] = { 5, 4, 7, 2, 11 };

    int n = sizeof(arr) / sizeof(arr[0]);



    treeSort(arr, n);



    return 0;

}

توابع و Structهای مورد استفاده در کد بالا به صورت زیر است: