Till KTH:s startsida Till KTH:s startsida

Trädrekursion

  • REKURSIV TRÄDSUMMA

    Ge en rekursiv tanke för summan av alla talen i trädet och programmera den så att anropet tree.sum() ger rätt svar.

    Rekursiv tanke: Summan är rottalet plus vänsterträdets summa plus högerträdets summa ... men tomt träd har summan noll. 

       def summa(p):     # Om den står utanför klassen slipper man self
      if p == None: 
         return 0
      else:
         return int(p.value)+summa(p.left)+summa(p.right)

   class Bintree
     - - -
     def sum(self):
       return summa(self.rot)

  • REKURSIV TRÄDHÖJD

    Ge en rekursiv tanke för höjden av ett träd. Höjden är den maximala nivån som nån av trädets noder befinner sig på. Ett träd med bara en rotnod har höjden 0, och ett tomt träd har höjden -1.
    Rekursiv tanke: Höjden är 1 + max(höjden av vänsterträdet, höjden av högerträdet) ...men tomt träd har höjden -1. 

       def height(p):
      if p == None: 
         return -1
      else:
         h1 = height(p.left)
         h2 = height(p.right)
         return max(h1,h2) + 1