Detailed steps to implement stack in-order traversal of a binary tree using 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)

The above is the detailed content of Detailed steps to implement stack in-order traversal of a binary tree using Python. For more information, please follow other related articles on the PHP Chinese website!