پیمایش درختی چیست ؟

پیمایش درختی چیست ؟

ما میتوانیم یک درخت عبارت را پیمایش کنیم و محتویات آن را به صورت زیر چاپ کنیم:

def printTree(tree):
if tree == None: return
print tree.cargo,
printTree(tree.left)
printTree(tree.right)

به بیان دیگر، براي چاپ یک درخت، ابتدا محتویات ریشه را چـاپ مـیکنـیم، سـپس سرتاسـر زیردرخت سمت چپ و آنگاه سرتاسر زیردرخت سمت راست را چـاپ مـینمـاییم. ایـن روش پیمـایش درخت preorder نامیده میشـود، زیـرا محتویـات ریشـه قبـل از محتویـات فرزنـدان نمـایش داده میشود. خروجی مثال قبل به این صورت است:

>>> tree = Tree(‘+’, Tree(1), Tree(‘*’, Tree(2), Tree(3)))
>>> printTree(tree)
+ 1 * 2 3

این قالب متفاوت از انواع postfix و infix است. این نوع دیگـري از نمادگـذاري بـه نـام prefix است که در آن عملگرها قبل از عملوندها ظاهر میشوند. اگـر درخـت را بـه ترتیـب دیگـري پیمایش کنید، ممکن است به این خروجی شک کنید. چـرا کـه عبـارتی بـا یـک نمادگـذاري متفـاوت به دست میآورید. براي مثال اگر ابتدا زیردرختها را چاپ کنید و سپس گره ریشه، خواهید داشت:

def printTreePostorder(tree):
if tree == None: return
printTreePostorder(tree.left)
printTreePostorder(tree.right)
print tree.cargo,

نتیجه، + * 3 2 1 ،به فرم postfix است! این ترتیـب پیمـایش postorder نامیـده میشود. در پایان اینکه، جهت پیمایش یک درخت به صورت inorder ،درخـت سـمت چـپ، سـپس ریشه و آنگاه درخت سمت راست را چاپ مینمایید:

def printTreeInorder(tree):
if tree == None: return
printTreeInorder(tree.left)
print tree.cargo,
printTreeInorder(tree.right)

حاصل، 3 * 2 + 1 میباشد که همان نمایش infix عبارت است. با دیدي منصفانه، باید متذکر شویم که ما اشکال مهمی را از قلم انداختیم. بعضی مواقـع، وقتـی یک عبارت infix را مینویسیم، مجبوریم براي حفظ ترتیب عملیات از پرانتز استفاده کنیم. بنـابراین یک پیمایش inorder براي تولید یک عبارت infix کافی نیست. با این همه با کمی پیشرفت، درخت عبارت و سه پیمایش بازگشتی، روشی کلـی بـراي ترجمـۀ عبارات از یک قالب به قالب دیگر ارائه میدهند. تمرین 20-1 :printTreePreorder را طوري تغییر دهید که دو پرانتز به دور هر عملگر و جفت عملوند آن قرار دهد. آیا خروجی درست و غیر مبهم است؟ آیا پرانتزها همیشه ضـروري هستند؟ اگر یک پیمایش inorder انجام دهیم و رد محلی را که در درخت بسر میبریم نگـه داریـم، میتوانیم نمایشی گرافیکی از یک درخت تولید کنیم:

def printTreeIndented(tree, level=0):
if tree == None: return
printTreeIndented(tree.right, level+1)
print ‘ ‘*level + str(tree.cargo)
printTreeIndented(tree.left, level+1)

پارامتر level موقعیت ما در درخت را ضبط میکند. این پارامتر در آغاز بهطور پیشفـرض 0 است. هر بار که یک فراخوانی بازگشتی انجام دهیم، 1+level را ارسال میکنیم، چرا که سطح فرزند همیشه یک واحد از سطح والد بزرگتر است. هر عضو بهوسیلۀ دو فاصـله در هـر سـطح کنگـرهگـذاري میشود. نتیجه براي درخت نمونه بدین صورت است:

>> printTreeIndented(tree)
3
*
2
+
1

اگر از پهلو به خروجی نگاه کنید، نسخۀ سادهشدهاي از شکل اصلی را میبینید.

برای اموزش های ویدیویی زبان پایتون به بستر ویدیو های اموزشی بروید

بستر اموزش های ویدویی