تحقیق مقاله درخت پشته و لیست پیوندی

درخت ها 

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

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

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

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

مسیر (path)، دنباله‌ای از گره‌های همجوار است. طول مسیر برابر با تعداد اتصال همجوار است که یکی کمتر از تعداد گره‌های موجود در آن مسیر است. 

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

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

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

سطح درخت : بزرگترین سطح‌ برگهای آن است. 

ارتفاع درخت: حداکثر تعداد گرههای موجود در مسیری از ریشه به یک گره برگ، ارتفاع درخت نامیده می‌شود. معمولاً با h نمایش داده می‌شود. 

H=d+1

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

درخت خالی : درختی که فاقد هر گونه گره‌ای باشد، درخت خالی نام دارد و عمق آن 1- تعریف می‌شود. 

اجداد گره : فرض کنید p(x) مسیری از گره x به ریشه را نشان می‌دهد. تمام گرههای موجود در p(x) به جز خود x، اجداد x نام دارند. ریشه درخت، جد تمام گرهها است و تنها گره‌ای که فاقد جد است.

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

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

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

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

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

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

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

 درخت دودویی (Brinary Tree) : 

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

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

1- درخت دودویی می‌تواند تهی باشد، ولی درخت عمومی نمی‌تواند تهی باشد. 

2- در درخت دودویی، هر گره حداکثر دو فرزند دارد. 

3- در درخت دودویی ترتیب فرزندان هر گره مهم است، در حالیکه در درخت عمومی اینطور نیست. 

همانگونه بیان گردید، ترتیب فرزندان در درخت دودویی مهم است، به عنوان مثال، دو درخت دودویی زیر یکسان نیستند. 

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

درخت دودویی کامل: درختی است که یا پر است یا با افزودن گرههای پشت سرهم به سمت راست سطح پائیی، به درخت پر تبدیل می‌شود. 

پیاده سازی درخت دودویی با آرایه :

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

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

دستیابی به گرههای درخت در نمایش آن با آرایه:

یکی از موضوعات مهم در هر نمایش یا پیاده سازی درخت آن است که به ریشه و گرههای درخت دسترسی پیدا کنیم. با فرض اینکه درخت در آرایه node قرار گرفته و تعداد گرههای درخت n باشند. 

1- ریشه درخت در خانه اول آرایه (node [1]) قرار دارد.

2- والد گرهی که در محل : قرار دارد در محل i/2 می‌باشد. 

3- فرزند چپ گره‌ای که در محل : قرار دارد، در محل 2i واقع است به شرط آنکه  . 

4- فرزند راست گره‌ای که در محل : قرار دارد، در محل 2i+1 واقع است به شرط آنکه   

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

1- هر گره‌ای از طریق گره دیگر قابل دستیابی است. 

2- فقط داده‌ ها زنجیره می‌شود و نیازی به فیلد اضافی برای مشخص کردن فرزند چپ و راست نیست. 

پیاده سازی درخت دودویی با اشاره گر:

ساختار هر گره در درخت مانند ساختار گرهها در لیست دوپیوندی می‌باشد، که اشاره‌گر راست به فرزند راست درخت و اشاره‌گر چپ به فرزند چپ درخت اشاره دارد. 

پیمایش درخت‌های دودویی : 

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

سه روش متداول برای پیمایش درختها وجود دارد که عبارتند از: 

1- روش پیشوندی یا preorder

2- روش پسوندی یا postorder

3- روش میانون یا inorder

1- روش پیمایش  preorder

در این روش، گرههای درخت که غیر خالی هستند بصورت زیر پیمایش می‌شوند. 

1- ریشه درخت را ملاقات کن 

2- اگر زیر درخت چپ خالی نیست، آن را به روش preorder پیمایش کنید. 

3- اگر زیر درخت راست خالی نیست، آن را به روش preorder پیمایش کنید. 

 در این روش ابتدا به گره سمت چپ می‌رود و تا منتهاالیه سمت چپ ادامه می‌دهد و پس از رسیدن آخرین گره سمت چپ به سمت راست حرکت می‌کند. 

procedur       preorder (node : node ptr);

begin 

        if node <> nil then 

          begin   

               write (node ^. info);

                preorder (node ^. left);

                 preorder (node ^. right);

             end; 

end;

2- پیمایش postorder : 

در این روش گرههای درخت که غیر خالی هستند به صورت زیر پیمایش می‌شوند. 

1- اگر زیر درخت چپ خالی نیست، آن را به روش postorder ملاقات کنید.

2- اگر زیر درخت راست خالی نیست، آن را به روش postorder ملاقات کنید.

3- ریشه درخت را ملاقات کنید. 

procedur       postorder (node : node ptr);

begin 

        if node <> nil then 

          begin   

               post Order (node ^ .left);

    post order   (node^.right);

                write (node ^. info);

             end; 

end;

3- روش پیمایشی inorder :

در این روش گرههای درخت که غیرقابل هستند بصورت زیر پیمایش می‌شوند:

1- اگر زیر درخت چپ خالی نیست، آن را به روش inorder پیمایش کنید.

2- ریشه درخت را ملاقات کنید.

3- اگر زیر درخت راست خالی نیست، آن را به روش inorder پیمایش کنید.

Procedure inorder (node: nodeptr);

begin

if node < > nil then

begin

inorder (node^.left);

write (node^.info);

inorder (node^.right);

end;

end;

ساخت درخت دودویی با استفاده از پیمایش آن:

برای ساخت درخت دودویی، با استفاده از یک نوع پیمایش نمی‌توان درخت منحصر به فردی ایجاد کرد، ولی اگر پیمایش inorder با یکی از پیمایش postorder یا preorder موجود باشد، اینکار امکان پذیر است. برای ساخت درخت بصورت زیر عمل می‌کنیم.

1- اگر پیمایش preorder موجود باشد، اولین گره ریشه است. اگر postorder موجود باشد، آخرین گره ریشه است.