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

发布:2022-10-12 10:25:29
阅读:1315
作者:网络整理
分享:复制链接

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

算法思路

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)
扫码进群
微信群
免费体验AI服务