用递归函数在Python中实现决策二叉树

问题描述

我是数据结构的初学者，我正在使用Python从列表创建决策二叉树，列表的元素应该在叶子中。列表的长度始终是配对数字。

我创建了一个二叉树的数据结构：

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

   def insert_left(self, value):
      if self.left == None:
         self.left  = BinaryTree(value)
      else:
         new_node = BinaryTree(value)
         new_node.left = self.left
         self.left= new_node

   def insert_right(self, value):
      if self.right== None:
         self.right= BinaryTree(value)
      else:
         new_node = BinaryTree(value)
         new_node.right= self.right
         self.right= new_node

   def get_value(self):
      return self.value

   def get_left(self):
      return self.left

   def get_right(self):
      return self.right

我创建了一个递归函数来实现树：

def cons_tree(leaflist):
   size = len(leaflist)
   tag = int(math.log(size)/math.log(2))
   return cons_tree_sub(tag, leaflist)

def cons_tree_sub(tag, leaflist):
   size = len(leaflist)
   abd = BinaryTree(tag)
   if size < 3:
      abd.insert_left(leaflist[0])
      abd.insert_right(leaflist[1])
   else :
      mid= size//2
      subList1= leaflist[:mid]
      subList2= leaflist[mid:]
      #the code in java is :
      #return new Node(tag,cons_tree_sub(tag-1,subList1),cons_tree_sub(tag-1,subList2));
      abd.insert_left(cons_tree_sub(tag-1, subList1))
      abd.insert_right(cons_tree_sub(tag-1, subList2))
   return abd

def display(T):
   if T != None:
      print (T.get_value(),display(T.get_left()),display(T.get_right()))

abd = cons_tree([False, True, True, False, False, True, False, False])
display(abd)

当我执行该程序时，我得到以下结果：

                           _________________________3__________________________
                          /                                                    
<__main__.BinaryTree object at 0x000002B3F25E8F70> <__main__.BinaryTree object at 0x000002B3F25E87C0>

我知道当我向左或向右插入时，我插入的是树而不是值，我如何才能在递归函数中实现所有树的子级

我尝试对return函数执行get_value()，因为它返回树：

abd.insert_left(cons_tree_sub(tag-1, subList1).get_value())
abd.insert_right(cons_tree_sub(tag-1, subList2).get_value())

但是我得到了未完成树的结果：

 3
/ 
2 2

我想要的结果是：

           __________3__________
          /                     
      ____2____             ____2_____
     /                    /          
   __1__      _1__       __1__      __1__
  /         /         /         /     
False True True False False True False False

---

解决方案

主要问题在这里：

abd.insert_left(cons_tree_sub(tag-1, subList1))

因为abd.insert_left需要值作为参数，但您将其传递给节点实例(因为这就是cons_tree_sub返回的内容)。

这样做：

abd.left = cons_tree_sub(tag-1, subList1)

.或创建setter，或更改insert_left，以便它也可以处理节点实例。

我将更改节点构造函数，以便它可以有选择地接受左子节点和右子节点的参数：

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

我还将对递归使用更具原子性的基本情况，并利用math.log2。

然后您可以减少代码并编写cons_tree，如下所示：

def cons_tree(lst):
    size = len(lst)
    if size == 1:
        return BinaryTree(lst[0])
    mid = size//2
    return BinaryTree(int(math.log2(size)), cons_tree(lst[:mid]), cons_tree(lst[mid:]))