Wie zu implementieren Heap Traversal in Python

Question

Ich habe gerade eine Heap-Klasse in Python und arbeitet immer noch in Tree Traversal. Als ich inoder function angerufen habe, erhielt ich Fehler None is not in the list. In meinen drei Traversalfunktionen benötigen sie alle left und right Funktion. Ich nehme an, dass das Problem in diesen beiden Funktionen liegt, aber ich weiß nicht, wie ich es beheben soll.

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

Wenn Sie den Baum auf der linken Kind folgen, und es gibt keine linke Kind, dann sollten Sie mit diesem Weg erfolgen. Du wirst garantiert irgendwann zu Keinem linken Kind mehr kommen, was dein Basisszenario sein sollte, um die Rekursion zu beenden.

Stattdessen suchen Sie den Wert des linken untergeordneten (mit seinem Index), dann berechnen Sie umgekehrt den Index, den Sie bereits von diesem Wert haben (hoffe, es gibt keine Duplikate). Da es schließlich keine Kind verlassen wird, wenn Sie versuchen, den Index von None umzukehren, finden Sie, dass es keine Keine in der "self.heapArray" und erhalten Sie den genauen Fehler "Keine ist nicht in der Liste"

Answer 2

Stellen Sie sich vor Was passiert, wenn Sie einen Inorder auf einem Blattknoten aufrufen? Es tritt in den Körper der if-Anweisung ein und versucht, die linken und rechten Kinder des Blattknotens zu erhalten - aber es gibt keine Kinder -, so dass es würgt, wenn self.left(i) zu None ausgewertet wird und in die index-Methode eingegeben wird. Sie müssen die Art, wie Sie die Rekursion beenden, überarbeiten, um zu überprüfen, ob der Knoten ein linkes und rechtes Kind hat.