درخت یک مجموعه ای که دارای یک یا چند تا گره است . این گره ها توسط یال به هم وصل شده اند .هر گره میتونه پدر چندتا گره دیگه باشه و یا فرزند باشه یعنی دارای پدر باشه .
درجه : تعداد زیر درختای یک گره (مثلا گره A درجه ان ۳ میباشد)
ریشه : گره ای که هیچ پدری نداشته باشه( گره A)
برگ : گره ای که هیچ فرزندی نداشته باشه ( درجه اون صفره)
خواهر یا برادر : گره های که پدر مشترک داشته باشند
ارتفاع گره : ار گره به سمت برگ میریم . بزرگترین مسیر میشه ارتفاع اون گره (مثلا ارتفاع گره A برابر ۳ میباشد ارتفاع گرهH برابر ۰ )
ارتفاع درخت : ارتفاع ریشه میشه ارتفاع درخت
سطح گره : سطح 0 به ریشه اختصاص داده میشه و برای همه گره های دیگه به ترتیب سطح ریشه به علاوه ۱ میشه (سطح گره A برابر 0 است . سطح گره های B,C برابر 1 است .)
درخت دودویی (full ): درختی که همه گره ها حتما ۲ تا فرزند دارن به جز برگ ها و همه برگ ها هم سطح هستند.
درخت دودویی کامل (complete): همه سطح های قبل از اولین سطح کاملا پر هستند . همه گره های تا جایی که ممکنه در سمت چپ قرار میگیرند .
پیمایش درخت دودویی : در این روش میایم توی درخت حرکت میکنیم و هر گره را حداقل یکبار ملاقات میکنیم پیمایش پیشوندی (Preorder ) : ریشه - چپ - راست .
پیمایش میانوندی (Inorder): چپ - ریشه - راست
پیمایش پسوندی (Postorder): چپ - راست - ریشه
برای مثال در شکل بالا توی پیمایش پیشوندی : اول گره ریشه (۸) ملاقات میشه بعد میریم توی زیر درخت سمت چپ (۵و۳و۴) حالا باز همین پیمایش و اجرا میکنیم . باز اول ریشه یعنی ۵ ملاقات میشه بعد گره سمت چپ یعنی ۵ ملاقات میشه و حالا الان ۳ فرزند چپ نداره پس فرزند سمت راست یعنی ۴ را ملاقات میکنیم
پیمایش میانوندی : اول زیر درخت چپ پیمایش میشه (۵و۳و۴) خب خودش یه درخته پس همین پیمایش روش اجرا میشه . در زیر درخت با گره های ۳و۴ فرزند چپ نداریم پس ریشه ان یعنی ۳ ملاقات میشه و بعد فرزند راست یعنی ۴ ملاقات میشه . میایم بالا الان گره ۵ فرزند چپش پیمایش شده پس نوبت ریشه اس یعنی ۵ حالا باز میایم بالا میرسیم به ۸ که فرزند چپش کامل پیمایش شده حالا نوبت ریشس که خودشه یعنی ۸ . حالا میریم سراغ فرزند راستش و همین پیمایش و روش اجرا میکنیم .
پیمایش پسوندی : اول زیر درخت چپ پیمایش میشه (۵و۳و۴) خب خودش یه درخته پس همین پیمایش روش اجرا میشه . در زیر درخت با گره های ۳و۴ فرزند چپ نداریم پس فرزند راست ان یعنی ۴ ملاقات میشه و بعد ریشه یعنی ۳ میشه . میایم بالا الان گره ۵ فرزند چپش پیمایش شده پس نوبت فرزند راسته که نداره پس نوبت ریشس یعنی ۵ حالا باز میایم بالا میرسیم به ۸ که فرزند چپش کامل پیمایش شده حالا نوبت فرزنده راستشه همین پیمایش و روش اجرا میکنیم .
درخت جستجوی دودویی (BTS) :
جستجو در BTS:
میایم اول عنصر مورد نظر را با ریشه مقایسه میکنیم اگه برابر بود که خب به جواب رسیدیم :)
اگه کوچکتر از ریشه بود میریم توی زیر درخت سمت چپ همین روش به صورت بازگشتی انجام میدیم
اگه بزرگتر از ریشه بود میریم توی زیر درخت سمت راست همین روش به صورت بازگشتی انجام میدیم
دنباله جستجو دنباله ای که برای جستجوی عنصر مورد نظر طی میشه .
مثلا دنباله جستجوی ۷ برابر <۷-۶-۸-۵>
درج در BTS:
میایم اول عنصر مورد نظر را با ریشه مقایسه میکنیم اگه کوچکتر از ریشه بود میریم توی زیر درخت سمت چپ اضافه میکنیم اگه بزرگتر از ریشه بود میریم توی زیر درخت سمت راست اضافه میکنیم. بعد از اضافه کردن چک کنید درخت حاصل حتما BTS باشد.
حذف گره از BTS:
اگر گره فرزند نداشته باشد (یعنی گره یک برگ باشد)خب میایم راحت حذفش میکنیم
اگر گره یک فرزند داشته باشد میایم همون فرزندو میزاریم جاش
اگر گره ۲ فرزند داشته باشد میایم کوچک‌ترین مقدار در زیردرخت راست گره را پیدا میکنیم.میزاریم جاش
مرتب سازی BTS : اگه پیمایش Inorder توی درخت انجام بدیم یه لیست مرتب شده داریم . به این روش tree sort میگن .
خب دوستان قطعا درخت خیلی مبحث بزرگتریه و من چیزای خیلی خیلی کمی بهتون گفتم امیدوارم زیاد گیج کننده و بد توضیح نداده باشم شبتون بخیر :)
