python - Python 中二叉搜索树的深度

Question

在我的二叉搜索树中，我正在创建一个深度函数，它将告诉用户他们插入的树的深度是多少。这个函数对于我独特的删除函数至关重要，该函数从最大深度节点中删除节点。我想我知道问题到底出在哪里，但我不确定。

这是我不断收到的错误。

C:\Python33\python.exe "C:/Users/koopt_000/Desktop/College/Sophomore Semester 2/Computer Science 231/Chapter7/Test.py"
Traceback (most recent call last):
PRE-ORDER TRANSVERSE:
  File "C:/Users/koopt_000/Desktop/College/Sophomore Semester 2/Computer Science 231/Chapter7/Test.py", line 19, in <module>
4
    print("The max depth of the tree is,", a.height(tree),"nodes deep.")
2
  File "C:\Users\koopt_000\Desktop\College\Sophomore Semester 2\Computer Science 231\Chapter7\BinarySearchTree.py", line 245, in height
1
3
7 
6 
5
10
None
IN-ORDER TRANSVERSE:
1
2
3
4
5
6
7
10
None
POST-ORDER TRANSVERSE:
1
    return max(BST.height(root.left), BST.height(root.right)) + 1
3
TypeError: height() missing 1 required positional argument: 'root'
2
5
6
10
7
4
None

Process finished with exit code 1

现在我认为我的问题出现在这部分代码中:

return max(BST.height(root.left), BST.height(root.right)) + 1

我相信这个语句是导致它的原因，因为它让我调用 BST 函数，高度函数已经在其中，以便它“工作”。我只是尝试了“height.(root.left)”，但它不起作用，因为它说没有全局变量高度。我不相信事实并非如此。

这是我的函数的完整代码列表，从我的树节点开始，然后是我的 BST 文件(主)，然后是我的测试代码。

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
        self.size = 0

    def delete(self, item):

        """remove item from binary search tree
        post: item is removed from the tree"""

        self.root = self._subtreeDelete(self.root, item)

    #------------------------------------------------------------

    def _subtreeDelete(self, root, item):

        if root is None:   # Empty tree, nothing to do
            return None
        if item < root.item:                             # modify left
            root.left = self._subtreeDelete(root.left, item)
        elif item > root.item:                           # modify right
            root.right = self._subtreeDelete(root.right, item)
        else:                                            # delete root
            if root.left is None:                        # promote right subtree
                root =  root.right
            elif root.right is None:                     # promote left subtree
                root = root.left
            else:
                # root node can't be deleted, overwrite it with max of 
                #    left subtree and delete max node from the subtree
                root.item, root.left = self._subtreeDelMax(root.left)
        return root

 def _subtreeDelMax(self, root):

        if root.right is None:           # root is the max 
            return root.item, root.left  # return max and promote left subtree
        else:
            # max is in right subtree, recursively find and delete it
            maxVal, root.right = self._subtreeDelMax(root.right)
            return maxVal, root  

   def height(self, root):
        if root is None:
            return 0
        else:
            return max(BST.height(root.left), BST.height(root.right)) + 1

<小时/>

from BinarySearchTree import BST
from TreeNode import TreeNode

tree = TreeNode(4, TreeNode(2, TreeNode(1), TreeNode(3)), TreeNode (7, TreeNode(6),TreeNode(9)))


a = BST()
a._subtreeInsert(tree, 10)
a._subtreeInsert(tree, 5)
a._subtreeDelete(tree, 9)

print("PRE-ORDER TRANSVERSE:")
print(a.preOrder(tree))
print("IN-ORDER TRANSVERSE:")
print(a.inOrder(tree))
print("POST-ORDER TRANSVERSE:")
print(a.postOrder(tree))

print("The max depth of the tree is,", a.height(tree),"nodes deep.")
print("There are,", a.treeSize(tree),"nodes in this tree.")

有人知道我的高度功能无法正常工作的原因吗？谢谢!

Answer 1

您的函数height是类BST的实例方法，您需要通过self调用它，而不是通过类调用它> BST 。因此，在您的特定情况下，这是:

def height(self, root):
    if root is None:
        return 0
    else:
        return max(self.height(root.left), self.height(root.right)) + 1

但是，您的函数 height 实际上并不依赖于与搜索树直接关联的任何数据。 self 只需要继续递归即可。因此，您还可以通过 staticmethod decorator 将其转换为静态方法。 :

@staticmethod
def height(root):
    if root is None:
        return 0
    else:
        return max(BST.height(root.left), BST.height(root.right)) + 1

或者，您也可以将函数完全移出 BST 类并摆脱 BST.height 并通过 height 调用它>.

从您发布的代码来看，这基本上适用于 BST 类的所有函数。我真的不认为有必要这样做。您只能在 Python 模块中使用 TreeNode 和一些顶级函数(没有 BST 类)来修改树并与树交互。