گروه تلگرامی برنامه نویسان advertise ساخت اپلیکیشن آندروید و IOS و اپ ساز laitec sharif univercity
دانلود پایان نامه وب سایت مهندسی پزشکی با ASP.net

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

12000 تومان
دانلود پروژه فروشنده دوره گرد با الگوریتم گرانشی در #C

دانلود پروژه فروشنده دوره گرد با الگوریتم گرانشی در #C

4800 تومان
دانلود سورس پروژه سی شارپ شبیه سازی صف بانک تحت شبکه

دانلود سورس پروژه سی شارپ شبیه سازی صف بانک تحت شبکه

3000 تومان
دانلود سورس n وزیر با جست وجوی ممنوع در سی شارپ #C

دانلود سورس n وزیر با جست وجوی ممنوع در سی شارپ #C

3000 تومان
دانلود پروژه آموزش چندرسانه ای با دایرکتور Director

دانلود پروژه آموزش چندرسانه ای با دایرکتور Director

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 در ساختمان داده هاآموزش درخت های دودویی در سی شارپمفهوم درختهای دودویی به زبان سادهاصطلاحات مربوط به درختهای دودوییدرخت های دودویی در ساختمان دادهمعرفی ساختمان داده binary treeآشنایی با binary tree در Data Structureعملیات درخت های دودویی در Data Structure لیست برچسب ها
تمامی حقوق این سایت اعم از محتوی ، تصاویر ، قالب و ... متعلق به گروه مهندسی وب سایت سورس کد می باشد.
SourceCodes.ir ، افقی روشن برای برنامه نویسان ، از مبتدی تا حرفه ای

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

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