رده‌ای (class) به نام BTree تعریف شده است:
- این رده به صورت template پیاده شده است؛
- در درخت هر عنصر با یک کلید (key) و مقدار (value) مشخص میشود. کلیدها از نوع عدد صحیح علامتدار ۴ بیتی (int) هستند و مبنای مقایسه‌ی عناصر در اعمال افزودن، حذف و جستجو در درخت هستند. مقادیر از نوع داده‌ی template رده می‌باشند؛
- برای این رده علاوه بر توابع سازنده‌ی کپی و مخرب، یک تابع سازنده‌ی بدون ورودی پیاده شده . وظیفه‌ی این تابع ایجاد یک درخت بدون عنصر است؛
- این توابع نیز پیاده سازی شده اند:
- تابع search: این تابع در ورودی، یک مقدار به عنوان کلید می‌گیرد و اشاره‌گری به مقدار متاظر در درخت بازمیگرداند. اگر مقدار در درخت وجود نداشت، مقدار 0 (NULL) بازگردانده می شود؛
- تابع insert: علاوه بر یک مقدار به عنوان کلید در ورودی، مقدار متناظر با کلید را نیز در ورودی گرفته و عنصری با کلید و مقدار ورودی در درخت درج میکند. چنانچه عنصر با کلید ورودی در درخت وجود داشت، مقدار متناصر با کلید، با مقدار ورودی تابع به روز شود. خروجی مشابه تابع search است؛
- تابع remove: یک مقدار به عنوان کلید در ورودی گرفته و عنصر متناظر را از درخت حذف میکند. همچنین مقدار (value) عنصر حذف شده را بازمیگرداند.؛
- تابع min: اشاره‌گر به مقدار متناظر با کوچکترین کلید در درخت را بازمیگرداند؛ اگر درخت خالی بود مشابه تابع search عمل شود.
- تابع max: مشابه تابع min اما برای بزرگترین کلید در درخت؛
- تابع inorder: کلید‌های درخت را به صورت inorder در خروجی چاپ میکند. هر کلید با یک نویسه‌ی فاصله (' ') جدا میشود. این تابع به صورت غیر بازگشتی پیاده سازی شده؛
- تابع inorderRec: مشابه تابع inorder، با این تفاوت که به صورت بازگشتی پیاده سازی شده؛
- تابع count: تعداد عناصر موجود در درخت را چاپ میکند.
دانلود سورس پیاده سازی درخت جستجوی دودویی (Binary Search Tree) با سی پلاس پلاس
