Как реализовать алгоритм сортировки дерева в Python? в бинарном дереве поиска - PullRequest
Новая
       28

Как реализовать алгоритм сортировки дерева в Python? в бинарном дереве поиска

0 голосов
/ 15 мая 2018

Я пытаюсь реализовать алгоритм сортировки деревьев в python.Это в настоящее время работа, которую я сделал.Я не совсем уверен, что такое алгоритм сортировки деревьев и как его реализовать.Любая помощь будет оценена.Спасибо 

 class BinTreeNode(object):

      def __init__(self, value):
           self.value=value
           self.left=None
           self.right=None


 def tree_insert( tree, item):
     if tree==None:
         tree=BinTreeNode(item)
     else:
         if(item < tree.value):
             if(tree.left==None):
                 tree.left=BinTreeNode(item)
             else:
                 tree_insert(tree.left,item)
      else:
          if(tree.right==None):
              tree.right=BinTreeNode(item)
          else:
              tree_insert(tree.right,item)
  return tree

def postorder(tree):
    if(tree.left!=None):
        postorder(tree.left)
    if(tree.right!=None):
       postorder(tree.right)
    print (tree.value)


def in_order(tree):
    if(tree.left!=None):
        in_order(tree.left)
    print (tree.value)
    if(tree.right!=None):
        in_order(tree.right)

if __name__ == '__main__':

  t=tree_insert(None,6);
  tree_insert(t,10)
  tree_insert(t,5)
  tree_insert(t,2)
  tree_insert(t,3)
  tree_insert(t,4)
  tree_insert(t,11)
  in_order(t)

1 Ответ

0 голосов
/ 15 мая 2018

Ваш код близок, однако tree_insert необходимо вызывать как атрибут переменных-членов left или right: 

class SortTree:
  def __init__(self, value):
    self.left = None
    self.value = value
    self.right = None
  def insert_val(self, _value):
    if _value < self.value:
       if self.left is None:
           self.left = SortTree(_value)
       else:
           self.left.insert_val(_value)
    else:
       if self.right is None:
          self.right = SortTree(_value)
       else:
          self.right.insert_val(_value)
  @classmethod
  def display(cls, _node):
     return list(filter(None, [i for b in [cls.display(_node.left) if isinstance(_node.left, SortTree) else [getattr(_node.left, 'value', None)], [_node.value], cls.display(_node.right) if isinstance(_node.right, SortTree) else [getattr(_node.right, 'value', None)]] for i in b]))


tree = SortTree(4)
for i in [5, 3, 1, 2, 8, 7, 4]:
  tree.insert_val(i)

print(SortTree.display(tree))

Выход: 

[1, 2, 3, 4, 4, 5, 7, 8]

Редактировать: без classmethod: 

class SortTree:
  def __init__(self, value):
    self.left = None
    self.value = value
    self.right = None
  def insert_val(self, _value):
    if _value < self.value:
       if self.left is None:
         self.left = SortTree(_value)
       else:
         self.left.insert_val(_value)
    else:
       if self.right is None:
         self.right = SortTree(_value)
       else:
         self.right.insert_val(_value)

def display(_node):
   return list(filter(None, [i for b in [display(_node.left) if isinstance(_node.left, SortTree) else [getattr(_node.left, 'value', None)], [_node.value], display(_node.right) if isinstance(_node.right, SortTree) else [getattr(_node.right, 'value', None)]] for i in b]))

tree = SortTree(4)
for i in [5, 3, 1, 2, 8, 7, 4]:
  tree.insert_val(i)

print(display(tree))

Выход: 

[1, 2, 3, 4, 4, 5, 7, 8]
...