Почему моя функция Depth возвращает высоту двоичного дерева, а не глубину? - PullRequest
Новая
       60

Почему моя функция Depth возвращает высоту двоичного дерева, а не глубину?

0 голосов
/ 13 декабря 2018

Я реализовал двоичное дерево поиска, используя Python.Все работает отлично, и функция nodeHeight() возвращает точную высоту для любого узла, но nodeDepth() возвращает тот же ответ, что и hegiht, даже если я рекурсивно вызываю глубину для родителя?и каков наилучший способ реализовать глубину для дерева, используя мои классы?Заранее спасибо! 

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))

1 Ответ

0 голосов
/ 13 декабря 2018

Ваш код здесь не вызывает nodeDepth, он вызывает nodeHeight дважды.

Ваша nodeDepth функция мне кажется некорректной.Я не понимаю, как он может вернуть что-либо, кроме 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
...