为什么我的深度函数 returns 二叉树的高度不是深度？

Question

我使用 Python 实现了二叉搜索树。一切都运行良好，nodeHeight() 函数 returns 任何节点的确切高度，但 nodeDepth() returns 与 hegiht 相同的答案，即使我递归调用深度parent？使用我的类实现树深度的最佳方法是什么？提前致谢！

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
        self.parent = None

class BST:

    def __init__(self):
        self.root = None

    def insertNode(self, data):
        if self.root != None:
            self._insertNode(self.root, data)
        else:
            self.root = Node(data)


    def _insertNode(self, node, data):
        if data < node.data:
            if node.left == None:
                node.left = Node(data)
                node.left.parent = node
            else:
                self._insertNode(node.left, data)
        elif data > node.data:
            if node.right == None:
                node.right = Node(data)
                node.right.parent = node
            else:
                self._insertNode(node.right, data)
        else:
            self._insertNode(node.right, data)


    def printNodes(self):
        if self.root != None:
            self._printNodes(self.root)

    def _printNodes(self, node):
        if node != None:
            self._printNodes(node.left)
            print(str(node.data))
            self._printNodes(node.right)

    def returnNode(self, data):
        if self.root != None:
            return self._returnNode(self.root, data)

    def _returnNode(self, node, data):
        if node.data == data:
            return node
        elif data < node.data and node.left != None:
            return self._returnNode(node.left, data)
        elif data > node.data and node.right != None:
            return self._returnNode(node.right, data)
        else:
            return 'Node not in tree'

    def isExternal(self, node):
        return node.left == None and node.right == None


    def nodeHeight(self, value):
        node = self.returnNode(value)
        if node != None:
            return self._nodeHeight(node, 0)

    def _nodeHeight(self, node, curHeight):
        if node == None or self.isExternal(node):
            return curHeight
        left_height = self._nodeHeight(node.left, curHeight + 1)
        right_height = self._nodeHeight(node.right, curHeight + 1)

        return max(left_height, right_height)

    def treeHeight(self):
        if self.root != None:
            return self.nodeHeight(self.root.data)
        else:
            return "no tree"

    def searchTree(self, data):
        if self.root != None:
            return self._searchTree(self.root, data)
        else:
            return False

    def _searchTree(self, node, data):
        if data == node.data:
            return True
        elif data < node.data and node.left != None:
            return self._searchTree(node.left, data)
        elif data > node.data and node.right != None:
            return self._searchTree(node.right, data)
        else:
            return "Not in Tree"

    def nodeDepth(self, data):
        node = self.returnNode(data)
        if node != None:
            return self._nodeDepth(node, 0)
        else:
            return "Node is None"

    def _nodeDepth(self, node, curDepth):
        if node == None or node == self.root:
            return 0
        return self.nodeDepth(node.parent, curDepth + 1)



tree = BST()
tree.insertNode(3)
tree.insertNode(7)
tree.insertNode(1)
tree.insertNode(5)

print(tree.nodeHeight(3))
print(tree.nodeHeight(3))

Answer 1

这里的代码没有调用 nodeDepth，它调用了两次 nodeHeight。

你的 nodeDepth 函数在我看来确实有缺陷。我看不出它怎么能 return 除了 0 之外的任何值。最简单的解决方法是更改 _nodeDepth 以在父项的高度上加一。

def nodeDepth(self, data):
    node = self.returnNode(data)
    if node != None:
        return self._nodeDepth(node)
    else:
        return "Node is None"

def _nodeDepth(self, node):
    if node == None or node == self.root:
        return 0
    return self._nodeDepth(node.parent) + 1

最好的解决方案是编写一个版本的 returnNode 函数，在递归通过树时跟踪深度。这样一来，您就可以在找到节点后停止，而无需再次在树中冒泡。

def nodeDepth(self, data):
    return self._nodeDepth(self.root, data)


def _nodeDepth(self, curr, data):
    if curr is None:
        return None
    if curr.data == data:
        return 0
    path = curr.left if data < curr.data else curr.right
    result = self._nodeDepth(path, data)
    if result is None:
        return None
    return result + 1

为什么我的深度函数 returns 二叉树的高度不是深度？

Why my Depth function returns the Height of Binary tree not the depth?

python

tree

binary-tree

binary-search-tree

python-3.x