时间戳

首页 > 解决方案 > BST算法的实现

python - BST算法的实现

问题描述

我想在 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()

标签： pythonbinary-search-tree

解决方案

首先，您的printTree方法是无参数的，但是，您正在传递它self.gauche并且self.droit. 相反，您应该在左侧 ( gauche) 和右侧 ( droit) 节点上调用 printTree() 方法：

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()

推荐阅读