Detaillierte Schritte zum Implementieren der Stapeldurchquerung eines Binärbaums in der richtigen Reihenfolge mit Python

使用堆栈无需递归就能遍历二叉树，下面是一个使用堆栈中序遍历二叉树的算法。

算法思路

1)创建一个空栈S。

2）将当前节点初始化为root

3)将当前节点推入S并设置current=current->left直到current为NULL

4)如果current为NULL且堆栈不为空，则

a)从堆栈中弹出顶部项目。

b)输出弹出的项目，设置current=popped_item->right

c)转到步骤3)。

5)如果current为NULL并且stack为空，那么算法结束。

算法实现步骤

1

/\

2 3

/\

4 5

步骤1创建一个空堆栈：S=NULL

步骤2将current设置为root的地址：current->1

步骤3推送当前节点并设置current=current->left

直到当前为NULL

当前->1

推1：堆栈S->1

当前->2

推2：堆栈>2,1

当前->4

推4：堆栈S>4、2、1

当前=NULL

步骤4从S弹出

a)弹出4：堆栈S->2,1

b)打印“4”

c)current=NULL/*right of 4*/并转到步骤3

由于current is NULL step 3没有做任何事情。

步骤4再次弹出。

a)弹出2：堆栈S->1

b)打印“2”

c)current->;5/*right of 2*/并转到步骤3

第3步将5推入堆栈并使当前为NULL

堆栈S->5,1

当前=NULL

步骤4从S弹出

a)弹出5：堆栈S->1

b)打印“5”

c)current=NULL/*right of 5*/并转到步骤3

由于current is NULL step 3没有做任何事情

步骤4再次弹出。

a)弹出1：堆栈S->NULL

b)打印“1”

c)当前->3/*1的右边*/

第3步将3推入堆栈并使当前为NULL

堆栈S->3

当前=NULL

步骤4从S弹出

a)弹出3：堆栈S->NULL

b)打印“3”

c)current=NULL/*3的右边*/

由于堆栈S为空且当前为NULL，因此遍历已完成。

Python实现堆栈中序遍历二叉树

class Node:
def __init__(self,data):
self.data=data
self.left=None
self.right=None
def inOrder(root):
current=root
stack=[]
while True:
if current is not None:
stack.append(current)
current=current.left
elif(stack):
current=stack.pop()
print(current.data,end="")
current=current.right
else:
break
print()
root=Node(1)
root.left=Node(2)
root.right=Node(3)
root.left.left=Node(4)
root.left.right=Node(5)
inOrder(root)

Das obige ist der detaillierte Inhalt vonDetaillierte Schritte zum Implementieren der Stapeldurchquerung eines Binärbaums in der richtigen Reihenfolge mit Python. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!