python中的树：创建递归子项

我有一个叫做带有两个参数（SX和SZ）的矩形的类。我需要做一个函数，将我的第一个矩形分成两部分，在一个宽的维度上随机放置一条线，然后这两个新的矩形将分为两部分，然后是四部分。我使用一个简单的树结构和这样的功能：python中的树：创建递归子项

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()

，功能level() —应该（但并不）返回多少级是根与实际节点之间的值：

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

重要对我来说，事情是：

如何限制这些分割（例如，只有1 + 2 + 4 + 8个节点）？我的意思是，Python中没有静态变量，我的函数level()无法正常工作。
如何获得访问年幼的孩子（例如，让他们在阵列）

我在编程新的，尤其是在Python。请有人帮助我吗？

来源

2012-12-29 Mei

要在级别数增加的限制只是通过它通过像这样的关键字：'def divide（rectangle，Max_levels = 5）'，然后在递归调用中的每次迭代执行以使得“max_level_1”和一旦max_level达到0时停止拒绝。 – sean

也许你正在寻找的东西是这样的：（这是一个双联（父母都知道孩子和孩子们知道父母）二叉树）

#! /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)

来源

2012-12-29 18:34:33 Hyperboreus

只是...哇。非常感谢你，你的代码是如此的优雅和明确。这将是有益的，我真的很感激。 – Mei

非常欢迎。 – Hyperboreus

它应该是a += 1而不是a = +1。

此外，在对象上调用divide()不会增加自己的level，所以你永远不会退出循环。您应该检查树的终端叶子上的等级。

来源

2012-12-29 18:04:35

addChild（up）和addChild（down）是什么？您可以将每个矩形与一个包含自身级别的整数相关联，这更容易，并且如果要在生成新矩形时限制树的深度，只需计算以下结果：2^h h->树的深度。

来源

2012-12-29 18:12:33

这只是添加一个新的节点（调用向上或向下）作为一个孩子的一个实际的节点 - 我需要这个功能的一些图形的东西，这就是为什么这样称呼它。感谢您使用新整数的想法，我想我会使用它。 – Mei

python中的树：创建递归子项

回答

相关问题