برای ساخت و نگه‌داری یک درخت دودودیی (Binary Search Tree) ساختار زیر به ما داده شده است و ما اجازه نداریم در آن تغییری به‌وجود بیاوریم.

1.	struct node {
2.	  node *left, *right;
3.	  int value;
4.	  node(){
5.	    right = left = value = 0;
6.	  }
7.	};

برای این ساختار کدهای زیر را با حداقل تعداد حلقه و شرط، در زیبایی کامل بنویسید.

1. برای ساختار بالا عملگرهای < و > را طوری بازتعریف کنید که بر حسب مقدار valueی دو گره به‌درستی کار کنند.
2. تابع node *insert(node *root, int x) را بنویسید که گره‌ای با مقدار x را در زیر درخت به-ریشه‌ی root درج کند. این عمل باید ساختار درخت را (همه نوادگان راست، ناکوچکتر و همه نوادگان چپ، نابزرگتر از ریشه) حفظ کند.
3. تابع node *find(node *root, int x) را بنویسید که در زیردرخت به‌ریشه‌ی root، عنصر x را بیابد. اگر موجود بود اشاره‌گری به آن گره برگرداند (اگر چند تا بود، هر کدام‌شان مقبول است). اگر موجود نبود هم باید 0 یا NULL برگرداند.
4. تابع void delete(node *here) را بنویسید که گره‌ی پارامتر را حذف کند.
5. تابع void print(node *root, int mode) را بنویسید که عناصر زیردرخت را در یک خط چاپ کند. برحسب این که mode برابر با صفر یا یک یا دو باشد، خروجی می‌بایست preorder یا inorder یا postorder باشد. تعداد دستورهای شما (با شمارش معقول و نه چپاندن!) می‌بایست حداقل باشد.
6. تابع node *next(node *here) را بنویسید که گره‌ی حاوی کوچکترین عدد بزرگتر از here→value را برگرداند. در این آیتم فرض کنید اعداد همگی متفاوتند. اگر here→value عدد بیشینه بود باید اشاره گری به 0 (همان NULL) برگردانده شود.
7. تابع bool checktree(node *root) را بنویسید که بررسی کند زیردرخت به‌ریشه‌ی root از نظر نسبت مقادیر موجود در گره‌ها آیا معتبر است یا نه؟ به این معنی که آیا مقادیر گره‌های درخت ساختار BST را دارند یا نه؟
8. برای هر کدام از ۶ تابع بالا مشخص کنید که پارامتر اشاره‌گری که تابع مربوطه می‌گیرد، آیا می‌تواند const باشد یا نه؟

• سوال بعد
• سوال قبل