如何在python中实现树排序算法？在二进制搜索中

Question

我尝试用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)

Answer 1

您的代码很接近，但是，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))

输出：

^{pr2}$

编辑：不带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))

输出：

^{pr2}$