فرق درخت پر با درخت كامل چيه ؟

[majidmir]

سلام فكر كنم عنوانم مشخص باشه فرق يه درخت پر با يه درخت كامل در چيه ؟

[qwerty11]

A binary tree in which each node has exactly zero or two children is called a full binary tree. In a full tree, there are no nodes with exactly one child



A complete binary tree is a tree, which is completely filled, with the possible exception of the bottom level, which is filled from left to right. A complete binary tree of the height h has between 2^h and 2^(h+1)-1 nodes


http://up.iranblog.com/Files/9f21cca8b08144e0a249.jpg

[اوبالیت به بو]

آقا اين شكل اشتباه هستش.

درخت پر درختي هست كه تمام گره هاي فرزند تا سطح آخر هر دو فرزند داشته باشند.

الان تو شكل شما درخت سمت چپ در سطح 2 و 3 گره ها كامل نيستند. چون درخت عمقش 4 هست پس بايد تمام گره هاي سطح 2 و 3 كامل تمام فرزندان رو داشته باشن كه ندارن.

درخت كامل شما هم بايد در سطح آخر يا برگ تمامي پدرانشون 2 فرزند رو داشته باشند به غير از آخرين گره. (يعني سمت چپ پر باشه)

اين درخت پر هست:

http://www.cs.mcgill.ca/%7Ecs251/OldCourses/1997/topic8/images/completetreetwo.gif


حالا بر اساس همون فرمول كه دوستمون در پست قبلي اشاره كرد فرزندان درخت رو ميشه شمرد:


2 ^ (H + 1) -1

H عمق درخت هست كه چون ريشه پدر هميشه 1 دونه هست بهش Level 0 مي دن و در فرمول بعدا +1 مي كنن كه جبران بشه

[qwerty11]

از شما با این تعداد پست بعیده !!!!

این تعریفه و من نمیتونم کار خاصی انجام بدم ! فقط میتونم کار زیر رو انجام بدم !!!! :

http://www.itl.nist.gov/div897/sqg/dads/HTML/fullBinaryTree.html

http://www.itl.nist.gov/div897/sqg/dads/HTML/completeBinaryTree.html

http://wiki.answers.com/Q/What_is_the_difference_between_a_binary_tree_and_a _complete_binary_tree

http://en.wikipedia.org/wiki/Binary_tree#Types_of_binary_trees

اگر قانع نشدین میشه نتیجه گرفت الآن روز هستش :)

ویرایش !: majidmir (http://www.barnamenevis.org/forum/member.php?u=63457) : راستی منظورت از درخت کامل کدومشه !؟ چون هم perfect tree داریم و هم complete tree . هم perfect و هم complete معنی کامل میده :-/

[mohsensaghafi]

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

http://www.cis.cau.edu/Curriculum/123/notes/binaryTreeExs.gif

[اوبالیت به بو]

از شما با این تعداد پست بعیده !!!!سلام

چي بعيده؟

اگر قانع نشدین میشه نتیجه گرفت الآن روز هستش :)
قرار نيست قانع بشم. ياد ميگيرم

درخت پر درختی است که تعداد فرزندان هر نود صفر یا 2 بوده و تمامی برگ ها در یک level قرار داشته باشند.
درخت کامل درختی است که تعداد فرزندان هر نود صفر یا 2 بوده و تمامی برگ ها در levelهای با اختلاف 1 level قرار داشته باشند. و هیچ فضای خالی در سمت چپ آخرین برگ وجود نداشته باشد.متشكر