在Python中计算二进制搜索树中的节点

Question

我对编程很新,我想要使用一些二进制搜索树.我想创建一个以递归方式计算树中节点数的函数,但是,当我运行我的函数时它似乎不起作用并且它一直返回'none',好像我的树中没有任何东西.谁能帮我找到问题呢？

这是我的TreeNode类:

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))时,它只返回'none'而不是'7'.

Answer 1

您也可以使用旧的递归方式:

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)

乔纳森的回答也很好.