python二叉树迭代器-为什么返回的节点变成None？
python二叉树迭代器-为什么返回的节点变成None？
提问于 2019-04-14 16:32:03
我抓了一个小时的头。
我使用迭代器和堆栈实现了二叉树的顺序遍历。
class Node:
def __init__(self, val, left, right):
self.val = val
self.left = left
self.right = right
class BTIterator:
def __init__(self, root):
self.stack = [] # Use a list as a stack by using pop() & append()
self.root = root
self.leftmost = None
def Run(self):
node = self.root
while (node.left != None):
self.stack.append(node)
node = node.left
print(self.stack)
self.leftmost = node
print(self.leftmost.val)
while (self.Next(node) != None):
node = self.Next(node)
print(node.val)
def Next(self, node):
if (node.left != None):
while (node.left != None):
self.stack.append(node.left)
node = node.left
return node
elif (node.right != None):
node = node.right
while (node.left != None):
self.stack.append(node)
node = node.left
return node
else:
if self.stack != []:
node = self.stack.pop()
node.left = None
return nodeif __name__ == '__main__':
# Let's construct the tree.
n12 = Node(12, None, None)
n11 = Node(11, None, n12)
n9 = Node(9, None, None)
n10 = Node(10, n9, n11)
n15 = Node(15, None, None)
n13 = Node(13, n10, n15)
n5 = Node(5, None, None)
n3 = Node(3, None, n5)
n7 = Node(7, n3, n13)
bti = BTIterator(n7)
bti.Run()我还在IDE上运行了上面的实现。通过调试，我清楚地看到def Next(self, node)返回n7。但是，一旦node = self.Next(node)行获得了n7，它就会将n7转换为None。为什么？!
我想这一定是一种我不知道的python语法。任何指针都将受到欢迎。
回答 1
Stack Overflow用户
回答已采纳
发布于 2019-04-14 17:46:55
在您的实现中，我想指出三个问题：
- 主要的问题是你在
Next中的实现是不正确的。因为inorder遍历是left->root->right的，所以if (node.left != None):部件是正确的，但是这里：
elif (node.right != None):
node = node.right
while (node.left != None):
self.stack.append(node)
node = node.left
return node在处理right子节点之前，应该先返回节点本身。
else:
if self.stack != []:
node = self.stack.pop()
node.left = None
return node当节点是叶子时，你不应该只弹出( pop )，你应该推入堆栈中的每个节点，并弹出每个Next。
- 您不能将
Next同时放在while条件和block中，因为它将调用两次。
while (self.Next(node) != None):
node = self.Next(node)python中不需要
!= None，只需要使用if node.left:
就可以了
因为Next有很多问题，所以我不得不重写Next，这是我根据你的代码编辑的版本，我做了详细的评论：
class BTIterator:
def __init__(self, root):
self.stack = [] # Use a list as a stack by using pop() & append()
self.root = root
def Run(self):
# find the left most node, which means then first node
node = self.root
while node.left:
self.stack.append(node)
node = node.left
# start from left most node
while node:
print(node.val)
node = self.Next(node)
def Next(self, node):
# find right node, if it is none, it's ok, we will deal with it afterwards
node = node.right
# reach the end
if not self.stack and not node:
return None
# push left child iteratively
while node:
self.stack.append(node)
node = node.left
# this is next node we want
return self.stack.pop()希望这对你有帮助，如果你有更多的问题可以发表意见。：)
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/55673394
复制相关文章
相似问题