برنامه‌ی زیر یک درخت دودودیی جست‌جو را تعریف می‌کند. در این برنامه یک جای‌گشت از اعداد ‎۱‎ تا ‎۱۰‎ ساخته شده و در درخت درج می‌شود. هدف این‌است که در پایان این اعداد (با پیمایش درخت) به‌صورت مرتب چاپ شوند.

#include <cstdio>
#include <algorithm>
 
struct Node {
  Node *left, *right;
  int value;
} *head;
 
int a[10], n;
 
void printSorted(Node *here) {
  // implement this function in 4 lines
}
 
void insertIntoBST(Node *&here, int x) {
  // implement this function in 5 lines!
}
 
int main() {
  n = 10;
  for (int i=0; i<n; i++)
    a[i] = i+1;
  std::random_shuffle(a, a+n);
 
  for (int i=0; i<n; i++)
    insertIntoBST(head, a[i]);
 
  printSorted(head);
  return 0;
}

1. تابع ‎printSorted‎ را در چهار خط (یا اگر نمی‌توانید، بیش‌تر) پیاده‌سازی کنید که یک اشاره‌گر به ‎Node بگیرد و درخت مربوط به آن را طوری پیمایش و در خروجی چاپ کند که اعداد خروجی مرتب شده (از ‎۱‎ تا ‎(۱۰ باشند. مزیّتی در پیاده سازی بازگشتی یا غیربازگشتی نیست، منتهی پیاده‌سازی بازگشتی به‌دلیل اختصار و سادگی توصیه می‌شود.
2. تابع insertIntoBST‎ را که یک ‎reference‎ به یک ‎Node *‎ و یک مقدار می‌گیرد، طوری پیاده‌سازی کنید که آن مقدار را در درخت (یا زیردرخت) ای که ریشه‌اش here‎ است درج کند.

از آن‌جا که here‎ یک reference‎ به یک ‎Node *‎ است، می‌توانید در صورت NULL بودن، آن را به‌سادگی ‎new‎ کنید‎!‎

در این قسمت نیز بازگشتی یا غیربازگشتی نوشتن تابع مزیّتی ندارد. با این‌حال، رویه بازگشتی اکیداً توصیه می‌شود.

• سوال قبل