advertise laitec sharif univercity استخراج بیت کوین با کامپیوتر استخراج بیت کوین با کامپیوتر
سورس پروژه دفترچه تلفن ساده در سی شارپ #c و بانک Access

سورس پروژه دفترچه تلفن ساده در سی شارپ #c و بانک Access

3000 تومان
دانلود پایان نامه وب سایت مهندسی پزشکی با ASP.net

دانلود پایان نامه وب سایت مهندسی پزشکی با ASP.net

12000 تومان
دانلود سورس هوش مصنوعی رنگ آمیزی گراف با ژنتیک در #C

دانلود سورس هوش مصنوعی رنگ آمیزی گراف با ژنتیک در #C

4800 تومان
پروژه پایانی PHP وب سایت فروشگاه کامپیوتری

پروژه پایانی PHP وب سایت فروشگاه کامپیوتری

23000 تومان
دانلود پروژه معمای 8 با الگوریتم ژنتیک در سی شارپ

دانلود پروژه معمای 8 با الگوریتم ژنتیک در سی شارپ

3000 تومان

ساختمان داده درخت های دودویی

درخت یکی از ساختمان داده های مهم غیرخطی است و درخت دودویی ، مجموعه محدودی از گره هاست که، حاوی گره خاصی به نام ریشه است و بقیه گره های آن، دو زیر درخت دودویی مجزا به نام های زیردرخت چپ و زیردرخت راست را تشکیل میدهند.
ساختمان داده درخت های دودویی

ساختمان داده درخت های دودویی

درخت یکی از ساختمان داده های مهم غیرخطی است که کاربردهای فراوانی در علم کامپیوتر دارد و انواع مختلفی دارند که در اینجا درخت های دودویی را مورد بحث قرار میدهیم.

درخت از مجموعه ای عناصر به نام گره تشکیل شده است که یکی از گره ها ریشه نام دارد. برخلاف درختهای طبیعی که ریشه آنها در پایین و برگها در بالا قرار دارند، در درختهای کامپیوتری ، ریشه در بالا و برگها در پایین قرار دارند. هر گره شامل فیلدی برای داده هاست و تعدادی پیوند دارد که از طریق آنها به گره های دیگری وصل میشود. این پیوندها را انشعاب یا اتصال نیز میگویند. گره ای که هیچ انشعابی از آن خارج نشود، برگ نام دارد.

درختها بطور کلی بر دو دسته اند: درختهای عمومی و درختهای دودویی. درخت دودویی درختی است که از هر گره آن حداکثر دو پیوند خارج میشود. درختی که دودویی نباشد، درخت عمومی است.

اصطلاحات مربوط به درختها:

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

عمق گره: طول مسیر آن به گره ریشه است. عمق درخت برابر با بیشترین عمق گره های برگ آن است.

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

ارتفاع درخت: حداکثر تعداد گره های موجود در مسیری از ریشه به یک گره برگ ارتفاع درخت نامیده میشود. در واقع، ارتفاع درخت یک واحد بیشتر از بزرگترین سطح برگهای آن است.

درخت یگانه: درختی که فقط دارای گره ریشه است، درخت یگانه نام دارد که عمق آن صفر است.

والد (پدر) گره: جد بلافصل یک گره را والد یا پدر آن گره گویند.

فرزندان گره: نسل های بلافصل یک گره را فرزندان آن گره گویند. ریشه تنها گره ای است که والد ندارد.

همزاد: گره هایی که والد انها یکسان است همزاد نامیده میشوند.

گره های برگ: گره هایی که هیچ فرزندی ندارند، برگ نامیده میشوند.

گره های داخلی: گره های غیر برگ را گره های داخلی مینامند.

اندازه درخت: تعداد گره های موجود در درخت را اندازه درخت گویند.

طول مسیر درخت: مجموع طولهای تمام مسیرها از ریشه آن است.

درجه گره: درجه گره برابر با تعداد فرزندان آن است.

 

مفهوم درخت های دودویی:

درخت دودویی ، مجموعه محدودی از گره هاست که، حاوی گره خاصی به نام ریشه است و بقیه گره های  آن، دو زیر درخت دودویی مجزا به نام های زیردرخت چپ و زیردرخت راست را تشکیل میدهند. در این نوع درخت هر گره حداکثر دو فرزند دارد و ترتیب فرزندان مهم است. اگر درخت دودویی در سطح i دارای m گره باشد، در سطح i+1 حداکثر دارای 2m گره است.

 

درخت دودویی پر:

درخت دودویی پر درختی است که تمام برگهای آن در یک سطح میباشند و هر گره داخلی نیز دارای دو فرزند است. در این نوع درخت، تعداد گره های هر سطح بدین صورت است: سطح صفر دارای 1 گره (2)، سطح 1 دارای 2 گره ()  و سطح i دارای  گره میباشد.

 

درخت دودویی کامل:

درخت دودویی کامل، درختی است که یا پر است یا با افزودن گره های پشت سر هم به سمت راست سطح پایینی، به درخت پر تبدیل میشود. اگر عمق درخت دودویی d باشد، در چنین درختی برگها در سطوح  d یا d-1 قرار دارند.

 

خواص درختهای دودویی:

در هر درخت دودویی، حداکثر تعداد گره ها در سطح Ɩ برابر با  2 است، بطوریکه Ɩ≥0 .

حداکثر تعداد گره های ممکن در درخت دودویی به ارتفاع h برابر با (2ͪ)-1 است.

حداقل تعداد گره ها در درخت دودویی به ارتفاع h برابر با h است.

برای هر درخت دودویی غیرتهی، اگر n تعداد گره ها و e تعداد پیوندها باشد، آنگاه n=e+1 .

برای هر درخت دودویی غیر خالی T، اگر n تعداد گره های برگ و n تعداد گره های داخلی باشد ، آنگاه n=n+1 .

 

 

 



0
نظرات

نظر خود را ارسال کنید



نام:
ایمیل:
دیدگاه:
captcha
کد امنیتی :


advertise
معرفی ساختمان داده binary treeدرخت های دودویی در ساختمان دادهدرخت های دودویی چه هستند؟عملیات درخت های دودویی در Data Structureآموزش درخت های دودویی در سی شارپمفهوم درختهای دودویی به زبان سادهآموزش درخت های دودویی در ساختمان دادهاصطلاحات مربوط به درختهای دودوییbinary tree در ساختمان داده هاآشنایی با binary tree در Data Structure لیست برچسب ها
تمامی حقوق این سایت اعم از محتوی ، تصاویر ، قالب و ... متعلق به گروه مهندسی وب سایت سورس کد می باشد.
SourceCodes.ir ، افقی روشن برای برنامه نویسان ، از مبتدی تا حرفه ای

تولید بیت کوین با کامپیوتر

پیشنهادات ویژه سورس کد

پکیج ویژه پروژه پایانی رشته کامپیوتر دانلود مجموعه 70 پروژه کاربردی سی شارپ وب سایت فروشگاه با php