在Python中使用inorder遍历(递归)打印二叉搜索树节点
问题描述:
我想在二叉搜索树上实现简单的inorder遍历方法。在Python中使用inorder遍历(递归)打印二叉搜索树节点
10
/ \
5 15
\
8
我想打印整个树,但我只打印前3个节点。我的问题是:
- 如何解决我的'inorder'打印方法? 'insert'方法正常工作。 - inorder方法的基本条件是什么?如何知道在所有节点打印完后停止?
class Tree:
def __init__(self, value):
self.node = value
self.leftChild = None
self.rightChild = None
def insert(self, value):
if self.node is None:
self.node = value
return True
if self.node is not value:
if self.node > value:
if self.leftChild is None:
self.leftChild = Tree(value)
else:
return self.leftChild.insert(value)
if self.node < value:
if self.rightChild is None:
self.rightChild = Tree(value)
else:
return self.rightChild.insert(value)
else:
return False
def inorder(self):
if self:
if self.leftChild:
return self.leftChild.inorder()
print self.node
if self.rightChild:
return self.rightChild.inorder()
tree = Tree(10)
tree.insert(5)
tree.insert(8)
tree.insert(15)
tree.inorder()
> 5
8
10
答
在return self.leftChild.inorder()
return
结束呼叫到inorder
self
之前和self.rightChild
可以处理。删除return
,该方法不会返回任何内容。
非常感谢!就是这样!关于我的基本条件问题,我真的迷失在这些递归中。让我这样问:假设我们的树只有4个节点:根是10:10的左边的孩子是5:10的右边的孩子是15:5的右边的孩子是8. Inorder()将以Root开始并调用self。 leftChild.inorder(),它是'5'。现在,节点'5'将再次调用self.leftChild.inorder(),但由于它没有离开子节点,所以会执行'print self.node'。接下来,它会调用self.rightChild.inorder(),它会将其引导为8.由于8没有正确的子节点,它将执行'print self.node'。 – Batool
问题:从节点8,inorder()如何知道它应该一直回到10?它将如何知道所有节点何时被访问? – Batool
“节点'5'将调用self.leftChild.inorder()”不,如果self.leftChild'意味着它甚至不会尝试。顺便说一句,如果“自我”没有意义,请删除它。对你的问题:递归不是魔术,它只是函数调用。当一个函数调用完成时,调用该函数的函数将继续它停止的地方。 Python会跟踪堆栈中帧中的所有函数调用。我建议单步调试。 [这是一个简单的](http://www.pythontutor.com/)。它不知道如何做任何你没有看到或不熟悉的事情。这只是做你告诉它。 –