在 Python 中计算二叉搜索树中的节点
Counting the nodes in a Binary Search Tree in Python
我对编程还很陌生,我想搞些二叉搜索树。我想创建一个函数来递归地计算树中节点的数量,但是,当我 运行 我的函数似乎不起作用并且它一直返回 'none' 就好像里面什么都没有一样我的树。谁能帮我找出问题所在?
这是我的 TreeNode class:
class TreeNode(object):
def __init__(self, data = None, left=None, right=None):
self.item = data
self.left = left
self.right = right
def __str__(self):
return str(self.item)
这是我的主要功能,我削减了大部分,以便我们可以解决与节点计数相关的问题。
from TreeNode import TreeNode
class BST(object):
#------------------------------------------------------------
def __init__(self):
"""create empty binary search tree
post: empty tree created"""
self.root = None
def treeSize(self, root, size = 0):
if root is None:
return -1
if root is not None:
size += 1
if root.left is not None:
self.treeSize(root.left, size)
if root.right is not None:
self.treeSize(root.right, size)
这是我用来测试我的功能的代码:
from BinarySearchTree import BST
from TreeNode import TreeNode
tree = TreeNode(4, TreeNode(2, TreeNode(1), TreeNode(3)), TreeNode (7, TreeNode(6),TreeNode(8)))
a = BST()
print(a.postOrder(tree))
print(a.treeSize(tree))
当我调用 'print(a.treeSize(tree))' 时,它只是 returns 'none' 而不是它应该的“7”。
我明白了。您认为 size 将在被调用的函数中得到更新。它不会,因为它对每个函数都是本地的。您可以对其调用 global
,但这不是最佳选择。
您可以将其设置为成员变量(实际上不要这样做):
def __init__(self):
...
self.size = 0
def treeSize(self,...):
...
self.size += 1
...
return self.size
但明显的错误是 self.size 每次调用 treeSize 时都会加倍。你也可以解决这个问题,但让我们使用我们知道和喜爱的模式。像 VHarisop 写的那样用旧的递归方式做。
你也可以用递归的方式来做:
def treeSize(self, root):
if root is None:
return 0
if root is not None:
return 1 + self.treeSize(root.left) + self.treeSize(root.right)
Jonathan 的回答也很好。
我对编程还很陌生,我想搞些二叉搜索树。我想创建一个函数来递归地计算树中节点的数量,但是,当我 运行 我的函数似乎不起作用并且它一直返回 'none' 就好像里面什么都没有一样我的树。谁能帮我找出问题所在?
这是我的 TreeNode class:
class TreeNode(object):
def __init__(self, data = None, left=None, right=None):
self.item = data
self.left = left
self.right = right
def __str__(self):
return str(self.item)
这是我的主要功能,我削减了大部分,以便我们可以解决与节点计数相关的问题。
from TreeNode import TreeNode
class BST(object):
#------------------------------------------------------------
def __init__(self):
"""create empty binary search tree
post: empty tree created"""
self.root = None
def treeSize(self, root, size = 0):
if root is None:
return -1
if root is not None:
size += 1
if root.left is not None:
self.treeSize(root.left, size)
if root.right is not None:
self.treeSize(root.right, size)
这是我用来测试我的功能的代码:
from BinarySearchTree import BST
from TreeNode import TreeNode
tree = TreeNode(4, TreeNode(2, TreeNode(1), TreeNode(3)), TreeNode (7, TreeNode(6),TreeNode(8)))
a = BST()
print(a.postOrder(tree))
print(a.treeSize(tree))
当我调用 'print(a.treeSize(tree))' 时,它只是 returns 'none' 而不是它应该的“7”。
我明白了。您认为 size 将在被调用的函数中得到更新。它不会,因为它对每个函数都是本地的。您可以对其调用 global
,但这不是最佳选择。
您可以将其设置为成员变量(实际上不要这样做):
def __init__(self):
...
self.size = 0
def treeSize(self,...):
...
self.size += 1
...
return self.size
但明显的错误是 self.size 每次调用 treeSize 时都会加倍。你也可以解决这个问题,但让我们使用我们知道和喜爱的模式。像 VHarisop 写的那样用旧的递归方式做。
你也可以用递归的方式来做:
def treeSize(self, root):
if root is None:
return 0
if root is not None:
return 1 + self.treeSize(root.left) + self.treeSize(root.right)
Jonathan 的回答也很好。