gpt4 book ai didi

python 如何使用中序/前/后/无递归遍历二叉搜索树?

转载 作者:太空宇宙 更新时间:2023-11-04 05:20:07 25 4
gpt4 key购买 nike

在 python 3

class BinaryTree:
"""
=== Private Attributes ===
@type _root: object | None
@type _left: BinaryTree | None
@type _right: BinaryTree | None

"""
def __init__(self, root, left, right):

if root is None:
# store an empty BinaryTree
self._root = None
self._left = None
self._right = None
else:
self._root = root
self._left = left
self._right = right

def is_empty(self):
return self._root is None

我知道如何递归地遍历这棵二叉树,但我想知道如何不递归地做到这一点

最佳答案

不用递归就可以用栈的方式遍历树。我举的例子是有序的

def inOrder(root):

# Set current to root of binary tree
current = root
s = [] # initialze stack
done = 0

while(not done):

# Reach the left most Node of the current Node
if current is not None:

# Place pointer to a tree node on the stack
# before traversing the node's left subtree
s.append(current)

current = current.left


# BackTrack from the empty subtree and visit the Node
# at the top of the stack; however, if the stack is
# empty you are done
else:
if(len(s) >0 ):
current = s.pop()
print current.data,

# We have visited the node and its left
# subtree. Now, it's right subtree's turn
current = current.right

else:
done = 1

更多解释你可以考虑https://www.youtube.com/watch?v=xLQKdq0Ffjg&t=755s教程

关于python 如何使用中序/前/后/无递归遍历二叉搜索树?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/40613405/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com