مرتب‌سازی درختی در جاوا (Tree Sort)

مارس 24, 2024
ارسال توسط سعید غریبی

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

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

مرتب‌سازی درختی در جاوا

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

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

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

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

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

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

public class TreeSort {

     class Node {

          int key;

          Node left, right;



          public Node(int item) {

              key = item;

              left = right = null;

          }

     }



     Node root;



     TreeSort() {

          root = null;

     }



     void insert(int key) {

          root = insertRec(root, key);

     }



     Node insertRec(Node root, int key) {



          if (root == null) {

              root = new Node(key);

               return root;

          }



          if (key < root.key)

              root.left = insertRec(root.left, key);

          else if (key > root.key)

              root.right = insertRec(root.right, key);



          return root;

     }



     // A function to do

     // inorder traversal of BST

     void inorderRec(Node root) {

          if (root != null) {

              inorderRec(root.left);

              System.out.print(root.key + " ");

              inorderRec(root.right);

          }

     }



     void treeins(int arr[]) {

          for (int i = 0; i < arr.length; i++) {

              insert(arr[i]);

          }



     }



     public static void main(String[] args) {

          TreeSort tree = new TreeSort();

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

          tree.treeins(arr);

          tree.inorderRec(tree.root);

     }

}

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