python - 树中 Twig 的长度总和

Question

例如，像这样的树:

    5
   / \
  3   6
 / \
7   2

print(tree.branchLenSum())

将是1+1+2+2=6

树类:

class BinaryTree:

    # Constructor, takes in new key value
    def __init__(self, myKey):
        self.key = myKey
        self.leftChild = None
        self.rightChild = None

    # Returns root key value
    def getRootValue(self):
        return self.key

    # Changes root key value
    def setRootValue(self, newKey):
        self.key = newKey

    # Returns reference to left child
    def getLeftChild(self):
        value=None
        if self.leftChild!=None:
            value=self.leftChild
        return value

    # Returns reference to right child
    def getRightChild(self):
        value=None
        if self.rightChild!=None:
            value = self.rightChild
        return value

    def insertLeftChild(self, childKey):
        newNode = BinaryTree(childKey)
        newNode.leftChild = self.leftChild
        self.leftChild = newNode

    # Inserts key as right child. Existing right child becomes new right child
    # of new key
    def insertRightChild(self, childKey):
        newNode = BinaryTree(childKey)
        newNode.rightChild = self.rightChild
        self.rightChild = newNode

我为示例构建的树:

tree=BinaryTree(5)
tree.insertLeftChild(3)
tree.insertRightChild(6)
nodeA=tree.getLeftChild()
nodeA.insertLeftChild(7)
nodeA.insertRightChild(2)

到目前为止我所拥有的:

def branchLenSum(self):
    rounds=0
    if self.getLeftChild() ==None and self.getRightChild()==None:
        return rounds+rounds+1
    else:
        rounds+=rounds+1
        if self.getLeftChild()!=None:
            rounds+=self.getLeftChild().branchLenSum()
        if self.getRightChild()!=None:
            rounds+=self.getRightChild().branchLenSum()
        return rounds

我的想法是，每次旅行到下一个节点时，计数器都会添加 1+计数器本身。我认为这将得到所有的长度总和。

Answer 1

好吧，所以你只得到 5 结果的原因相当简单:你正在做的就是计算节点。所以在你的例子中，你有 5 个节点，所以结果是 5。

如果您想获得内部路径长度，那么我相信您必须在浏览树时跟踪当前深度。您只需使用可选参数即可完成此操作。

def branchLenSum(self, depth = 0):
    rounds = depth
    if self.leftChild:
        rounds += self.leftChild.branchLenSum(depth + 1)
    if self.rightChild:
        rounds += self.rightChild.branchLenSum(depth + 1)
    return rounds

在这种情况下，每当我们向下导航到子级时，我们都会将当前深度增加一。而在计算节点的分支长度时，我们是从深度开始的。

顺便说一句。请注意，正式地，内部路径长度被定义为仅内部节点的长度，即不是叶子的长度。上面的方法对包括叶子在内的每个节点进行计数。如果您想遵循官方定义，则必须在开头添加叶子检查，并为叶子返回0。

<小时/>

其他一些事情:

• 方法 getLeftChild 和 getRightChild 实际上什么也不做。您将 None 分配给返回值，然后检查左/右子级是否为 None，如果不是，则将子级分配给返回值并返回它。

  所以本质上，您正在返回 self.leftChild/self.rightChild;无需实际查看该值并检查 None。

• 在 Python 中，通常不使用访问器或修改器方法(getters/setters)；您只需访问底层属性本身。这使得 getLeftChild、getRightChild、getKey 和 setKey 方法变得多余。

• 使用 != None 或 == None 检查 None 是一种反模式。例如，如果您想检查子项是否不是 None，只需执行 if child 即可。如果您想检查它是否未设置(即不是 None)，只需执行 if not child 即可。