Как реализовать обход кучи в Python

Question

Я только что сделал кучу классов в Python и до сих пор работаю в обход дерева. Когда я призвал inoder functionЯ получил ошибку сказал None is not in the list, В моих трех функциях обхода они все нужны left а также right функция. Я предполагаю, что проблема в этих двух функциях, но я не знаю, как это исправить.

class myHeap:
    heapArray = []

    def __init_(self):
            self.heapArray = []

    def __str__(self):
            string = " ".join(str(x) for x in self.heapArray)
            return string

    def makenull(self):
            self.heapArray = []

    def insert(self, x):
            self.heapArray.append(x)
            self.upheap(self.heapArray.index(x))

    def parent(self, i):
            p = (i - 1) / 2
            p = int(p)
            if(p >= 0):
                    return self.heapArray[p]

            else:
                    return None

    def left(self, i):
            l = (i + 1) * 2 - 1
            l = int(l)
            if(l < len(self.heapArray)):
                    return self.heapArray[l]
            else:
                    return

    def right(self, i):
            r = (i + 1) * 2
            r = int(r)
            if(r < len(self.heapArray)):
                    return self.heapArray[r]
            else:
                    return None
    def swap(self, a, b):
            temp = self.heapArray[a]
            self.heapArray[a] = self.heapArray[b]
            self.heapArray[b] = temp

    def upheap(self, i):
            if(self.parent(i) and self.heapArray[i] < self.parent(i)):
                    p = (i - 1) / 2
                    p = int(p)
                    self.swap(i, p)
                    i = p
                    self.upheap(i)
            else:
                    return

    def downheap(self, i):
            if(self.left(i) and self.right(i)):
                    if(self.left(i) <= self.right(i)):
                            n = self.heapArray.index(self.left(i))
                            self.swap(i, n)
                            self.downheap(n)
                    else:
                            n = self.heapArray.index(self.right(i))
                            self.swap(i, n)
                            self.downheap(n)
            elif(self.left(i)):
                    n = self.heapArray.index(self.left(i))
                    self.swap(i, n)
                    self.downheap(n)
            elif(self.right(i)):
                    n = self.heapArray.index(self.right())
                    self.swap(i,n)
                    self.downheap(n)
            else:
                    return

    def inorder(self, i):
            if(self.heapArray[i] != None):
                    self.inorder(self.heapArray.index(self.left(i)))
                    print(self.heapArray[i], end=" ")
                    self.inorder(self.heapArray.index(self.right(i)))

    def preorder(self, i):
            if(self.heapArray[i] != None):
                    print(self.heapArray[i], end=" ")
                    self.preorder(self.heapArray.index(self.left(i)))
                    self.preorder(self.heapArray.index(self.right(i)))

    def postorder(self, i):
            if(self.heapArray[i]!= None):
                    self.postorder(self.heapArray.index(self.left(i)))
                    self.postorder(self.heapArray.index(self.right(i)))
                    print(self.heapArray[i], end=" ")

    def min(self):
            return self.heapArray[0]

    def deletemin(self):
            self.swap(0, len(self.heapArray) - 1)
            self.heapArray.pop
            self.downheap(0)

def main():
    heap = myHeap()
    heap.insert(0)
    heap.insert(15)
    heap.insert(7)
    heap.insert(8)
    heap.insert(1)
    heap.insert(2)
    heap.insert(22)
    print(heap)
    print(heap.heapArray[0])
    heap.inorder(0)
    heap.preorder(0)
    heap.postorder(0)

if __name__ == "__main__":
    main()

Answer 1

Когда вы следуете по дереву к его левому потомку, а левого потомка нет, тогда вы должны покончить с этим путем. Вы гарантированно в конечном итоге доберетесь до левого ребенка, что должно стать вашим базовым случаем для прекращения рекурсии

Вместо этого вы ищите значение левого потомка (используя его индекс), а затем вычисляете индекс, который у вас уже есть, по этому значению (надеюсь, что нет дубликатов). Поскольку в конечном итоге None останется дочерним, при попытке выполнить обратное вычисление индекса None вы обнаружите, что в "self.heapArray" нет None, и получите точную ошибку "None отсутствует в списке"

Answer 2

Представьте, что происходит, когда вы вызываете inorder на листовом узле. Он входит в тело оператора if и пытается получить левого и правого потомков конечного узла, но потомков нет, поэтому он задыхается, когда self.left(i) оценивается в None и подается в index метод. Вам нужно изменить способ завершения рекурсии, чтобы проверить, есть ли у узла левый и правый дочерний элемент.