پیمایش میان‌ترتیب و پیش‌ترتیب بدون بازگشت

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

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

ورودی:

درخت جستجوی هفت‌گره‌ای؛ میان‌ترتیب ۳ ۶ ۷ ۱۵ ۱۷ ۱۸ ۲۰ (مرتب) و پیش‌ترتیب ۱۵ ۶ ۳ ۷ ۱۸ ۱۷ ۲۰.

class Node:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
def iterative(root):
stack = []
on_stack = [] # the keys of the nodes on the stack, for the picture
# Inorder: go left as far as possible, pushing each node; then pop, visit, and go right.
ino = []
out = ino
node = root
while node is not None or stack:
if node is not None:
stack.append(node)
on_stack.append(node.key)
node = node.left
else:
node = stack.pop()
on_stack.pop()
ino.append(node.key)
node = node.right
# Preorder: pop and visit; push the right child first so the left one comes out first.
pre = []
out = pre
if root is not None:
stack.append(root)
on_stack.append(root.key)
while stack:
node = stack.pop()
on_stack.pop()
pre.append(node.key)
if node.right is not None:
stack.append(node.right)
on_stack.append(node.right.key)
if node.left is not None:
stack.append(node.left)
on_stack.append(node.left.key)
return ino, pre

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

شروع اجرا

on_stack—

ino—

pre—

نارنجی = در همین گام عوض شد

key = 15
left = Node(key=6, left=Node(key=3, left=None, right=None), right=Node(key=7, left=None, right=None))
right = Node(key=18, left=Node(key=17, left=None, right=None), right=Node(key=20, left=None, right=None))

گام ۱ از ۱۴۵

توضیح

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

هر گره یک بار وارد و یک بار خارج پشته می‌شود: Θ(n). پشته حداکثر به اندازه‌ی ارتفاع درخت (h) رشد می‌کند.