二叉树的所有节点之和

2022-03-13 00:00:00 python python-3.x list sum binary-tree

问题描述

我正在尝试编写一个程序来计算由列表列表表示的二叉树(不是二叉树)中所有节点(包括根)的总和。从概念上讲,我理解递归方式是最好的方式,但就是无法弄清楚代码。到目前为止,我的代码是:

class BinaryTree:
    def __init__(self,rootObj, leftChild = None, rightChild = None):
        self.key = rootObj
        self.leftChild = None
        self.rightChild = None
        self.node=[rootObj, leftChild, rightChild]
    def getrightChild(self):
        return self.rightChild
    def getleftChild(self):
        return self.leftChild
    def setRootObj(self,obj):
        self.key = obj
    def getRootObj(self):
        return self.key
    def sumTree(BinaryTree):
        if BinaryTree is None: return 0
        return sumTree(BinaryTree.leftChild)  
             + sumTree(BinaryTree.rightChild)
             + BinaryTree.rootObj

print(sumTree([8,[],[]]))
print(sumTree([9, [6, [ ], [ ]], [65, [ ], [ ]]]))

解决方案

从我从这段代码中读取的信息来看,您的递归算法是正确的。 但是,其中存在许多语法错误和其他语义错误,导致无法正确运行。

我看到的是:

  • 您创建了BinaryTree类,但从未创建过它的实例。 会尝试计算列表总和,但这不会起作用,因为您希望它对对象进行求和。您需要首先解析该列表并创建BinaryTree的实例。(如tree = BinaryTree(*write your list here*)可能。当然,您需要使__init__()方法允许传递列表。参见下一点。)
  • 您的__init__()方法将BinaryTree对象作为参数,因此不会分析您的列表。
  • __init__()方法中,您将两个子节点都设置为None,因此任何节点都不会有子节点。
  • 调用sumTree()方法时,需要指定上下文。 它必须是BinaryTree.sumTree(..)。不过,您仍然需要创建应该传递给sumTree方法的二叉树实例。
  • sumTree()方法中,您尝试访问不存在的rootObj成员,因为您将其称为key

除了错误之外,如果您愿意,我还想指出一些"代码气味"。

  • 您应该将sumTree()方法的参数重命名为与类名不同的名称。
  • 在python中,不需要getter-method。您可以直接访问成员。如果您仍然希望定义更复杂的get/set行为,您应该了解一下python属性。
  • 成员node从未使用过。

相关文章