реализация алгоритма BST - PullRequest
Новая
       5

реализация алгоритма BST

0 голосов
/ 04 июня 2018

Я хочу преобразовать этот алгоритм в Python.Алгоритм должен построить дерево на основе алгоритма BST.Когда я запускаю свой код, они дают мне 0 в качестве результата.

Я делаю это рекурсивно: 

def complet(self,li=[]):
       N=len(li)
       n=log2(N+1)
       delta=N-2**(n-1)
       delta=delta+1
       m1=2**(n-1)
       m1=m1-1
       m2=(2**(n-2))/2
       if delta <= m2: x=m1+delta
       else: x=m1
       self=Noeud(x)
       if len(li)==1: return self
       else:
        lg=li[int(len(li)/2):]
        ld=li[:int(len(li)/2)]
        self.gauche=self.complet(lg)
        self.droit=self.complet(ld)
       return self

bst алгоритм

мой код:

from math import log2
import cmath
import math
L=["0111","10000","11100","100011","11","1","010" ]
def sort(l=[]):
 for n in range(0,len(l)):
  while len(l[n])<8:
    l[n]=l[n]+"1"
 print(l)
 for k in range(0,len(l)):
     for j in range(k,len(l)):
       if int(l[j],2)> int(l[k],2):
           bj=l[j]
           l[j]=l[k]
           l[k]=bj
 print(l)
 return l
sort(L)
class Noeud:
    def __init__(self,va):
        self.droit=None
        self.gauche=None
        self.valur=va
    def complet(self,li=[]):
       N=len(li)
       n=log2(N+1)
       delta=N-2**(n-1)
       delta=delta+1
       m1=2**(n-1)
       m1=m1-1
       m2=(2**(n-2))/2
       if delta <= m2: x=m1+delta
       else: x=m1
       self=Noeud(x)
       if len(li)==1: return self
       else:
        lg=li[int(len(li)/2):]
        ld=li[:int(len(li)/2)]
        self.gauche=self.complet(lg)
        self.droit=self.complet(ld)
       return self
    def printTree(self):

          if self.gauche:
            self.printTree(self.gauche)
          print(self.valur, end="")
          if self.droit:
            self.printTree(self.droit)

ar=Noeud(0)
ar.complet(L)
ar.printTree()

1 Ответ

0 голосов
/ 04 июня 2018

Прежде всего, ваш метод printTree не имеет параметров, однако вы передаете его self.gauche и self.droit.Вместо этого вам следует вызывать метод printTree () для левого (gauche) и правого (droit) узлов: 

def printTree(self):
    if self.gauche:
        self.gauche.printTree()
    print(self.valur, end="")
    if self.droit:
        self.droit.printTree()

Во-вторых, вы не используете значение, возвращаемое методом complet,Вы можете исправить это следующим образом: 

ar=Noeud(0)
ar2 = ar.complet(L)
ar2.printTree()
...