帶有輔助函式的Python遞回函式-有解無憂

我正在撰寫一個函式來確定二叉搜索樹的大小。我以遞回方式嘗試過：

def size(self) -> int: #self representing the whole bst
        """Return number of nodes contained in the tree."""

        if self._root is None:
            return 0
        else:
            return self._size(self, 0, self._root)

def _size(self, current_size, current_node):

        if current_node != None:
            current_size  = 1
        if current_node.left != None:
                current_size  = self._size(current_size, current_node.left)
        if current_node.right != None:
                current_size  = self._size(current_size, current_node.right)

        return current_size

但是，這會為該行引發 TypeError：

return self._size(self, 0, self._root)
TypeError: 'int' object is not callable

我是遞回函式的新手，不知何故無法真正找出輔助函式和原始函式應該如何協同作業，以及我的方法是否朝著正確的方向發展。因此，非常感謝任何幫助。

以下是類的代碼：

from typing import Any


class TreeNode:

    def __init__(self, key: int, value: Any, right: 'TreeNode' = None,
                 left: 'TreeNode' = None, parent: 'TreeNode' = None):
        """Initialize TreeNode.

        Args:
            key (int): Key used for sorting the node into a BST.
            value (Any): Whatever data the node shall carry.
            right (TreeNode, optional): Node to the right, with a larger key. Defaults to None.
            left (TreeNode, optional): Node to the left, with a lesser key. Defaults to None.
            parent (TreeNode, optional): Parent node. Defaults to None.
        """
        self.key = key
        self.value = value
        self.right = right
        self.left = left
        self.parent = parent


from tree_node import TreeNode


class BinarySearchTree:
    """Binary-Search-Tree implemented for didactic reasons."""

    def __init__(self, root: TreeNode = None):
        """Initialize BinarySearchTree.

        Args:
            root (TreeNode, optional): Root of the BST. Defaults to None.
        
        """
        self._root = root
        self._size = 0 if root is None else 1

uj5u.com熱心網友回復：

有以下問題：

_size是在__init__函式中設定的實體屬性。這意味著self._size它將參考該屬性，而不是同名的類方法。這是您得到錯誤的原因。您應該為這兩件事使用不同的名稱：一個名稱用于整數大小，另一個名稱用于遞回計算大小的輔助函式。我建議將_sizerecur其用作輔助方法的名稱——并將在下一點以這種方式參考它：
self._sizerecur(self, 0, self._root)不應self作為引數傳遞，因為該引數已經self通過這種型別的方法呼叫語法獲取值（點符號中的前綴用作該引數）。
if current_node != None應該在其塊中包含該代碼的所有其余部分，否則current_node.left仍將在 is 時進行評估current_node，None從而導致錯誤。
尺寸計算不正確。基本上有兩種方法可以實作此遞回，并且您的代碼似乎混合了這兩種方法，使其不正確：當您將當前大小作為引數傳遞給遞回呼叫并且該呼叫回傳更新后的值時，您不應該添加到您已經傳遞給它的原始大小。通過這樣做，你有雙重計算。您應該將它分配回您的變數（不添加到它），或者（更好），不將當前計數作為引數傳遞，而是讓每個遞回呼叫從 0 開始計數。

這是保留現有current_size引數的更正：

    def size(self) -> int:
        if self._root is None:
            return 0
        else:
            return self._sizerecur(0, self._root) # don't pass self as arg

    # A distinct name for this method
    def _sizerecur(self, current_size, current_node):
        if current_node:
            current_size  = 1
        if current_node.left:
            # don't ADD again to current size
            current_size = self._sizerecur(current_size, current_node.left)
        if current_node.right:
            current_size = self._sizerecur(current_size, current_node.right)

        return current_size

但如前所述，最好的做法是在沒有current_size引數的情況下實作這個遞回函式。不要在遞回更深時更新計數器，而是在退出遞回時更新它：

    def size(self) -> int:
        if self._root is None:
            return 0
        else:
            return self._sizerecur(self._root)

    def _sizerecur(self, current_node):
        current_size = 0
        if current_node:
            current_size = 1
            if current_node.left:
                current_size  = self._sizerecur(current_node.left)
            if current_node.right:
                current_size  = self._sizerecur(current_node.right)
        return current_size

uj5u.com熱心網友回復：

self呼叫 self.function_name() 時不需要顯式傳遞

return self._size(0, self._root)

轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/482924.html

標籤：Python 递归二叉搜索树

上一篇：如何以最有效的方式完全調平（映射/減少/遞回）未知深度的嵌套物件？

下一篇：創建一個洗掉整數奇數位的遞回函式