====== درخت دودویی ======

برنامه‌ی زیر یک درخت دودودیی جست‌جو را تعریف می‌کند. در این برنامه یک جای‌گشت از اعداد ‎۱‎ تا ‎۱۰‎ ساخته شده
و در درخت درج می‌شود. هدف این‌است که در پایان این اعداد (با پیمایش درخت) به‌صورت مرتب چاپ شوند.
<code c>
#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;
}

</code>

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

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

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

  * [[سوال ۱۷|سوال قبل]]