advertise laitec sharif univercity تبلیغات در سایت سورس کد تبلیغات در سایت سورس کد
دانلود برنامه آزمون تستی در مالتی مدیا بیلدر MMb

دانلود برنامه آزمون تستی در مالتی مدیا بیلدر MMb

3000 تومان
سیستم اتوماسیون دهیاری ، پروژه مهندسی نرم افزار

سیستم اتوماسیون دهیاری ، پروژه مهندسی نرم افزار

3000 تومان
دانلود PDF مجموعه 300 نکته جالب برنامه نویسی در سی شارپ #C

دانلود PDF مجموعه 300 نکته جالب برنامه نویسی در سی شارپ #C

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

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

23000 تومان
سورس پروژه پایانی آزمون گیری با زبان سی شارپ و SQL

سورس پروژه پایانی آزمون گیری با زبان سی شارپ و SQL

7000 تومان

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 

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

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

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

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