====== سوال ۹ ======




**درخت جست‌وجوی دودویی** یک درخت ریشه‌دار $n$ رأسی با ویژگی‌های زیر است:

  * رأس‌ها با اعداد ۱ تا $n$ شماره‌گذاری شده‌اند.
  * هر رأس  __حداکثر__ دو فرزند دارد که یکی ریشه‌ی زیردرخت سمت چپ و دیگری، ریشه‌ی زیردرخت سمت راست است.
  * به ازای هر رأس، شماره‌های تمام رأس‌های زیردرخت سمت چپ آن (در صورت وجود) از شماره‌ی خودش  کوچک‌تر و شماره‌ی تمام رأس‌های زیردرخت سمت راست آن (در صورت وجود) از شماره‌ی خودش بزرگ‌‌تر است.


برای مثال، یک درخت جست‌وجوی دودویی در زیر کشیده‌ایم:


{{ :سوالات_المپیاد:مرحله‌ی_اول:دوره‌ی_۲۹:untitled104.png |}}


درخت زیر را در نظر بگیرید. در هر مرحله می‌توانیم یک یال در نظر گرفته و شماره‌ی دو رأس آن را جابه‌جا کنیم. کمینه‌ی تعداد مراحل لازم را بیابید، طوری که بتوانیم شکل را به یک درخت جست‌وجوی دودویی تبدیل کنیم.

{{ :سوالات_المپیاد:مرحله‌ی_اول:دوره‌ی_۲۹:untitled105.png |}}

  - 5
  - 6
  - 7
  - 8
  - 9

<پاسخ>
 گزینه‌ی ۳ درست است.





</پاسخ>

  * [[سوال ۸|سوال قبل]]
  * [[سوال ۱۰|سوال بعد]]