CODEWITHSUNDEEP
pythonbinary-tree
johne
johne

Reputation: 31

generating a binary tree from given data in python

i wanted to know how to read values from a list into a binary tree. i have a triangle like this:

         0
       1   2
     3   4   5
   6   7   8   9

i have written a class node like this

class node:
    def __init__(self,data,left=None,right=None):
        self.data=data
        self.left=left
        self.right=right

basically what i want to do is something like this

node(0,node(1),node(2))

i want to make a recursive function that can handle much bigger triangles. Can somehow tell me what i am supposed to do?

edit: quite clearly binary tree is not the way to approach this problem. what i basically want to find out are all the different combination's from top to bottom. like 0,1,3,6 0,2,5,8 etc.

Upvotes: 3

Views: 5390

Answers (2)

Antony Hatchkins
Antony Hatchkins

Reputation: 33984

For such list:

a = 'aBCdef'

The program below generates the following structure:

- a -
- B C
B C -
- d e
d e f
e f -

Code (input list is assumed to correspond to a 'complete' triangular):

class Node:
    def __init__(self,data,left=None,right=None):
        self.data=data
        self.left=left
        self.right=right

    def __unicode__(self):
        return '%s %s %s' % (
                self.left.data if self.left or '-', 
                self.data, 
                self.right.data if self.right or '-')


nodelist = [Node(c) for c in a]

i,y = 0,1

while True:
    for x in range(y):
        nodelist[i].left = nodelist[i-1] if x!=0 else None
        nodelist[i].right = nodelist[i+1] if x!=y-1 else None
        i+=1
    if i<len(a):
        y+=1
    else:
        break

for n in nodelist:
    print unicode(n)

Upvotes: 0

danben
danben

Reputation: 83250

This does sound like homework, so I won't write code, but here are a couple of hints:

  1. This could be done even if your triangle were written as a list, like 0 1 2 3 4 5 6 7 8 9

  2. Because it seems like this is a full binary tree (assuming your triangle is wrong and the third row is actually supposed to be 3 4 5 6), you could maintain a parents queue whose head is the next parent that needs children. Note that I am specifically not recommending recursion.

A full binary tree is one where each non-leaf node has exactly two children. If this is not supposed to be a full binary tree, then there is no deterministic way to interpret the problem (since each of node 1 and 2 could have 1 or 2 children, given your picture).

Upvotes: 1

Related Questions