Pythonでヒープトラバーサルを実装する方法

Question

私はちょうどPythonでヒープクラスを作って、まだツリートラバーサルで働いています。 inoder functionを呼び出すと、エラーが発生しました。None is not in the listです。私の3つのトラバーサル機能では、すべてがleftとrightの機能を必要とします。私は問題がこれらの2つの機能にあると仮定しますが、私はそれを修正する方法がわかりません。

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 left childになることが保証されています。これは再帰を終了するための基本ケースにすべきです。

左の子の値を索引で検索する代わりに、その値から既存の索引を逆計算します（重複がないことを望みます）。結局Noneが残っているので、Noneのインデックスを逆順に計算しようとすると、 "self.heapArray"にNoneがなく、 "Noneはリストにありません"と表示されます。

Answer 2

Imagineリーフノードでinorderを呼び出すとどうなりますか？これはifステートメントの本体に入り、リーフノードの左右の子を取得しようとしますが、子はありません。したがって、self.left(i)が評価されずにindexメソッドに渡されるとチョークします。再帰を終了する方法を変更して、ノードに左右の子があるかどうかを確認する必要があります。