آشنایی با درخت ها در مبحث گراف
اسلاید 1: فصل دهم: درخت‌ها (Trees) بخش 10.1 آشنایی با درخت‌ها (Introduction to Trees)
اسلاید 2: درختیک گراف ساده همبند بدون دور ساده را درخت می گویند.قضیه: یک گراف درخت است اگر و فقط اگر بین هر دو راس آن دقیقا یک مسیر ساده وجود داشتته باشد.
اسلاید 3: 3کدامیک از گراف های زیر درخت است؟ a)b)c)
اسلاید 4: درخت ریشه دار (Rooted Tree)یک درخت ریشه دار درختی است که در آن یک راس به عنوان ریشه معرفی شده و همه یال ها از سمت ریشه جهت دار می شوند.4
اسلاید 5: چهار نمونه از درخت ریشه دار5
اسلاید 6: درخت m-aryبه یک درخت ریشه دار درخت m-ary می گویند اگر هر راس داخلی آن (راس های که فرزند دارند) در این درخت بیشتر از m بچه نداشته باشد.یک درخت m-ary کامل (full m-ary tree) درخت ریشه داری است که تمام رئوس داخلی آن دقیقا m تا بچه داشته باشند.به یک درخت m-ary که مقدار m آن برابر با 2 باشد یک درخت دودویی (Binary Tree) می گویند.6
اسلاید 7: 7Rooted Tree
اسلاید 8: 8A Tree Has a RootTREE ROOTریشه درخت
اسلاید 9: 9Leaf nodes have no childrenLEAF NODESگره های برگ
اسلاید 10: 10A Tree Has LevelsLEVEL 0
اسلاید 11: 11Level OneLEVEL 1
اسلاید 12: 12Level TwoLEVEL 2
اسلاید 13: 13SIBLINGSبرادر یا خواهرSibling nodes have same parent
اسلاید 14: 14SIBLINGSSibling nodes have same parent
اسلاید 15: 15A SubtreeLEFT SUBTREE OF ROOTزیر درخت سمت چپ ریشهROOT
اسلاید 16: 16Another SubtreeRIGHT SUBTREE OF ROOTROOT
اسلاید 17: 17How many internal vertices?
اسلاید 18: خصوصیات درختقضیه: درختی با n راس 1- n یال دارد.قضیه: یک دخت m-ary کامل با i راس داخلی دارای n=mi+1 راس می باشدقضیه: یک دخت m-ary کامل (full m-ary tree) با18
اسلاید 19: خصوصیات درختقضیه: در یک درخت m-ary به ارتفاع h حداکثر mh برگ دارد.قضیه: اگر یک درخت m-ary دارای l برگ و ارتفاع h داشته باشد آنگاه h≥⌈logml⌉. اگر این درخت m تایی، پر و متوازن باشد، h=⌈logml⌉19
اسلاید 20: فصل دهم: درخت ها (Trees) بخش 10.3 پیمایش درخت (Tree Traversal)
اسلاید 21: سیستم آدرس دهی جهانی (Universal Address System)21
اسلاید 22: پیمایش پیش ترتیب (Preorder Traversal)ابتدا ریشه سپس زیر درخت به ترتیب از سمت چپ به راست دیده می شود.22
اسلاید 23: 23
اسلاید 24: 24
اسلاید 25: پیمایش میان ترتیب (Inorder Traversal)ابتدا زیر درخت اول از سمت چپ دیده می شود سپس ریشه دیده می شود و بعد بقیه زیر درخت ها از سمت چپ به راست. 25
اسلاید 26: 26
اسلاید 27: 27
اسلاید 28: 28
اسلاید 29: پیمایش پس ترتیب (Postorder Traversal)ابتدا زیردرخت ها به ترتیب از سمت چپ به راست دیده می شوند و در انتها ریشه دیده می شود.29
اسلاید 30: 30
اسلاید 31: 31
اسلاید 32: 32
اسلاید 33: 33
نقد و بررسی ها
هیچ نظری برای این پاورپوینت نوشته نشده است.