CODEWITHSUNDEEP
pythonrecursiontree
Mei
Mei

Reputation: 80

Tree in python: recursive children creating

I have a class called rectangle with two parametres (SX and SZ). I need to do a function that will devide me a first rectangle in two parts with a line in a random place on the wider dimension, then these two new rectangles will be divided in two, then four etc. I use a simple tree structure and a function like this:

def devide(self):
    if (self.SX>self.SZ):                #check which dimension is bigger
        temp=randint (int(self.SX/4), int(self.SX*3/4))  #generate random from x/4,3x/4           
        left=rectangle(temp, self.SZ)             #create nodes
        right=rectangle(self.SX-temp, self.SZ)
        self.addChild(left) 
        self.addChild(right)
    else:
        temp=randint (int(self.SZ/4), int(self.SZ*3/4))              
        up=rectangle(self.SX, temp)                 
        down=rectangle(self.SX, self.SZ-temp)
        self.addChild(up)
        self.addChild(down)

    for c in self.getChilds():
        while (c.level()<3):     ####why doesn't it work?:(
            c.devide()

And the function level()— it should (but it doesn't) return a value of how many levels are between the root and the actual node:

def level(self): 
    root=self
    a=0
    while root.isRoot()==False: 
        a+=1
        root=root.getParent()
    return a

Important things for me are:

I am new in programming, especially in Python. Could somebody help me, please?

Upvotes: 0

Views: 4161

Answers (3)

Hyperboreus
Hyperboreus

Reputation: 32429

Maybe you are looking for something like this: (It is a double-linked (parent knows children and children know parent) binary tree)

#! /usr/bin/python3.2

import random

class Rectangle:
    def __init__ (self, width, height, parent = None):
        self.width = width
        self.height = height
        self.parent = parent
        self.children = []

    @property
    def level (self):
        return 0 if not self.parent else 1 + self.parent.level

    def split (self):
        if self.children: raise Exception ('Already split')
        ratio = random.random () * .5 + .25 #split between 1/4 and 3/4
        if self.width > self.height:
            width = int (ratio * self.width)
            self.children = [Rectangle (width, self.height, self),
                Rectangle (self.width - width, self.height, self) ]
        else:
            height = int (ratio * self.height)
            self.children = [Rectangle (self.width, height, self),
                Rectangle (self.width, self.height - height, self) ]

    def splitUntilLevel (self, maxLevel):
        if maxLevel <= self.level: return
        self.split ()
        for child in self.children: child.splitUntilLevel (maxLevel)

    def __str__ (self):
        s = '{}{} x {}\n'.format (' ' * (2 * self.level), self.width, self.height)
        for child in self.children: s += str (child)
        return s

r = Rectangle (100, 100)
r.splitUntilLevel (3)
print (r)

Upvotes: 2

the_grandson
the_grandson

Reputation: 15

What does addChild(up) and addChild(down)? You could associate to each rectangle an integer that contains the self level, much more easy and if you want to limit the depth of the tree when generating a new rectangle just evaluate the result of: 2^h h-> depth of the tree.

Upvotes: 0

Lev Levitsky
Lev Levitsky

Reputation: 65781

It should be a += 1, not a = +1.

Also, calling divide() on an object will not increase its own level, so you'll never get out of the loop. You should check the level on the terminal leaves of the tree.

Upvotes: 0

Related Questions