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

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

  1. درخت دودویی جستجو
  2. کلاس تودرتو در جاوا
  3. Constructor در جاوا
  4. توابع بازگشتی

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

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

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

پیمایش میان ترتیب: در این روش اول زیر درخت چپ سپس ریشه و در انتها زیر درخت راست پیمایش می‌شود به این ترتیب پیمایش میان ترتیب درخت زیر به صورت 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);

     }

}

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

  1. Treeins: این متد عناصر آرایه را دریافت و درخت دودویی آنها را می‌سازد.
  2. inorderRec: متدی است که پیمایش میان ترتیب را انجام می‌دهد.
  3. insertRec: این متد برای وارد کردن عنصری به درخت دودویی ما است.
  4. Node: کلاسی است که عناصر درخت‌ دودویی را در خود نگه‌داری می کند.
  5. Root: ریشه درخت دودویی ما است.

ورودی برنامه بالا آرایه‌ای با عناصر 11, 5, 7, 9, 12 می‌باشد و خروجی آن به صورت زیر است:

Sorted Array:

5 7 9 11 12

Download “دانلود سورس مرتب‌سازی درختی در جاوا” Tree-Sort-in-Java-www.codegate.ir_.zip – 26 بار دانلود شده است – 1 کیلوبایت

پسورد: www.codegate.ir