PDA

View Full Version : سوال: تعاريف درختها



mehdi58
دوشنبه 09 دی 1387, 09:16 صبح
با سلام
من در مورد درختها دچار سردرگمي شدم و با مراجعه به منابع مختلف ، نتونستم تعريف درستي از اونها به دست بيارم .
درخت دودويي
درخت پر
درخت كامل
درخت دودويي كامل

manvaputra
دوشنبه 09 دی 1387, 09:56 صبح
درخت دودويي:
هر گره دو تا برگ داره یکی سمت چپ و یکی سمت راست


http://lcm.csa.iisc.ernet.in/dsa/img151.gif


درخت پر:

درختی است با سطح n که تمامی گره های سطح N-1 برگاشون پر باشه ، مثلا توی درخت دودویی هر گره می تونه دو تا برگ داشته باشه حالا درخت دو دوی پر میشه یه درخت دودویی مثلا با سطح N که تمام گرهه های سطح N-1 دو تا برگ داشته باشن.


http://www.gamedev.net/reference/programming/features/trees2/FullBinary.jpg


درخت كامل:
درختی است با سطح n اگه در خت تا سطح N-1 پر باشه (با توجه به تعریف بالا) و در سطح N هم برگها از چپ به راست پر شده باشه.


http://www.maths.abdn.ac.uk/%7Eigc/tch/mx4002/notes/img162.gif

mehdi58
سه شنبه 10 دی 1387, 18:07 عصر
1 - آيا تعريف درخت دودويي با درخت دودويي محض يا توسه يافته برابر است ؟
تعريف درخت دودويي محض يا توسعه يافته :
هر گره يا برگ است يا داراي دو فرزند .

2 - در شكل سومي كه دوستمون manvaputra ارسال كردن ( يعني شكل درخت كامل ) ، اگه نود G رو در شكل در نظر نگيريم باز هم درخت كامله ؟

3 - آيا درخت دودويي كامل همان درخت دودويي است ؟ در صورتيكه پاسخ شما منفي است لطفا توضيح دهيد .