Decision Binary Tree implementation in Python with recursive function-CodePudding

I am beginner in data structure and I am using Python to create a decision binary tree from a list, the elements of the list should be in the leaf. the length of the list is always a pair number.

I create a data structure of binary tree:

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

I create a recursive function to implement a tree :

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)

When I execute the program I have this result :

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

I understand that when I insert in the left or the right I insert a tree not a value, how I can get to implement all the tree children in a recursive function

I tried to do get_value() for the return function because it returns a tree :

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

but I have a result of uncomplete tree :

 3
/ \
2 2

The result I want is :

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

CodePudding user response：

The main problem is here:

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

Because abd.insert_left expects a value as argument, but you pass it a node instance (as this is what cons_tree_sub returns).

So do:

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

...or create a setter, or alter insert_left so that it can also deal with node instances.

I would change the node constructor so it can optionally take arguments for left and right children:

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

I would also use a more atomic base case for the recursion, and make use of math.log2.

Then you could reduce code and write cons_tree as follows:

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:]))

CodePudding user response：

You're using a top-down approach, constructing the tree from the top and inserting values in the tree.

I suggest a bottom-up approach, constructing the tree from the bottom and merging two small trees into a bigger tree.

One way to do that is to add a new .__init__ method to class Tree, in order to allow constructing a tree from two subtrees:

class Tree:
    def __init__(self, v, l=None, r=None):
        self.value = v
        self.left = l
        self.right = r
    def __repr__(self):
        if self.left is None and self.right is None:
            return repr(self.value)
        else:
            return 'T({},{},{})'.format(self.value, self.left, self.right)

def build_tree(seq):
    if len(seq) == 1:
        return Tree(1, seq[0], None)
    elif len(seq) == 2:
        return Tree(1, seq[0], seq[1])
    else:
        m = (len(seq)   1) // 2
        l = build_tree(seq[:m])
        r = build_tree(seq[m:])
        return Tree(max(l.value, r.value)   1, l, r)

print( build_tree([False, True, True, False, False, True, False, False]) )
# T(3,T(2,T(1,False,True),T(1,True,False)),T(2,T(1,False,True),T(1,False,False)))