用Python实现堆栈中序遍历二叉树的详细步骤

知识点掌握了，还需要不断练习才能熟练运用。下面golang学习网给大家带来一个文章开发实战，手把手教大家学习《用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)

以上就是《用Python实现堆栈中序遍历二叉树的详细步骤》的详细内容，更多关于算法的概念的资料请关注golang学习网公众号！