实践 - 一棵树的建造

  本实践介绍用Python在Tkinter上画一棵树的方法。通过本实践，读者可以练习面向对象的程序设计方法、练习生成器的使用方法、运用递归函数、了解Tkinter画图的基本方法以及学习“树”这种重要的数据结构。

  本章要画的树“大概”如图1所示。为什么说是大概呢？ 因为树的结构是在一定约束条件下随机生成的，所以每个人画出来的树多少会有一些差异。

1. 数据结构——树

  要完成本章实践，读者首先要了解一点数据结构（data structure）的知识。数据结构是指计算机内部表达和组织数据的方式。

1.1 树

  树（Tree）是一种数据结构，它模拟现实世界中的树形结构，我们通常将其描绘成图2所示的样子。为了说明方便，作者把每个节点用字母作了标识。

  T是一棵树，树上的每个圆圈被称为一个节点（node），其中，a是树T的根节点（root node）。节点可以有后代 （descendents），其中，直接的后代称为儿子节点（child）。图2中，b、c、d是节点a的儿子，h、i是节点d的儿子。有儿子的节点称为内节点，没有儿子的节点称为叶子（leaf）。图2中，e、f、k等节点没有儿子，作者用浅蓝色作了填充，它们是叶子。

  T’是树T的一棵子树（sub tree），其根节点为d，我们称树T’是树T中以d节点为根的子树。理论上，任何一个节点其及全部后代都可视为一棵树。

  图2中右侧的数字0、1、2、3表示节点在树中的深度（depth）。a节点的深度为0，g、h节点的深度为2，j、k、l节点的深度为3。

1.2 树的递归表示

  下述代码展示了一个表示树的Python递归结构。

1
2
3
4
5
6
7
8
9
10
11
12

class TreeNode:
    def __init__(self,label):
        self.sLabel = label
        self.children = []

a = TreeNode('a')
b = TreeNode('b')
c = TreeNode('c')
d = TreeNode('d')
a.children.extend([b,c,d])
b.children.extend([TreeNode('e'),TreeNode('f')])
...

  TreeNode类有一个sLabel属性，用于存储节点的标签。此外，该类还有一个类型为列表的数据成员children，用于存储该节点的全部儿子节点。而儿子节点的类型也为TreeNode，其也有children列表用于存储该儿子节点的儿子。当一个TreeNode对象的children列表为空时，表明该节点为叶子。

  上述代码的6~11行建立了1.1小节所述的树结构的一部分。其中a为根节点，a有b、c、d 3个儿子，而b又有两个儿子e和f…

2. Top-Left坐标系

  在图形程序设计中，一般采用Top-Left坐标系。如图3所示，以屏幕或者窗口的左上角为原点，横向为x轴，纵向为y轴。位置越靠右，x越大；位置越靠下，y越大。窗口内任意一个点的位置可用一对（x,y）来表示，这一对（x,y）值被称为该点的坐标。

3. 实例中的树表达

  如下述代码所示，Point类的成员x和y用于表明一个坐标点。TreeNode类表示树节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y

class TreeNode:
    maxDepth = 8
    nBranches = 3
    def __init__(self, bottom, top, depth=0):
        self.bottom = bottom
        self.top = top
        self.drawingTop = top
        self.depth = depth
        self.children = []
        self.__generateDescendents()

  类属性maxDepth表示树所允许的最大深度。类属性nBranches表示“建议”的树分叉数，即一根树枝将分出多少根下层树枝。此处之所以用了“建议”一词，是因为实际树在生成过程中分支数会引入随机成分。

  TreeNode对象的children属性是其儿子列表，depth表示该节点在树中的深度。TreeNode对象的另外几个属性需要结合图4来理解，这是作者在树上截取的一段小树枝。图4中，a是一个TreeNode节点，其bottom表示以该节点为根的子树的“下”顶点；其top表示以该节点为根的子树的“上”顶点。注意，这里作者为上、下两字加了引号，那是因为实践中，程序试图模拟地球引力的作用，树枝可能事实上是倒垂向下的。

  drawingTop定义为该节点自身（不含其子孙）的描绘用“上”顶点。a节点在树中的实际表现为一段树枝，树枝的描绘范围即为bottom至drawingTop点。从drawingTop一直到top则是a的子孙们的描绘区域。图4中，b、c、d为a的儿子，b、c、d也是TreeNode类型，其bottom应等于a的drawingTop。图4中，可以看到，b、c、d的bottom与a的drawingTop是同一个点。

  此外，TreeNode类构造函数的最后一行执行了一个“不公开”成员函数__generateDescendents（），这个函数将递归生成以该节点为根的子树，该子树中节点的深度不超过TreeNode.maxDepth。该部分内容参见后节。

【变量、函数、类的判定准则】

① 新手们写出来的程序通常可读性和健壮性都有问题。作者建议，当读者试图定义一个变量、函数、类时，都必须满足如下规则：如果其作用和取值可以用简洁明了没有歧义地讲清楚，那么其存在可能是合理的。如果说不清道不明，那么读者需要另寻他法。本实践中的，TreeNode的bottom、top、drawingTop，受限于其复杂性，所以很难用一句话描述，但借助图示，是可以讲清楚的。

② Python之禅里有一句话是——“If the implementation is easy to explain, it may be a good idea”。请读者品味其含义。

4. 树的递归生成

4.1 分叉树支生成

  下述__generateDescendents（）函数在节点的构造函数中被调用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class TreeNode:
    ...
    def __generateDescendents(self):
        "Recursively build sub-tree of the current node."
        n = random.randint(TreeNode.nBranches//2, \
                           round(TreeNode.nBranches*1.5))
        n = n if n >=1 else 1

        r = 0.20 + random.random() * 0.2
        x = self.bottom.x + (self.top.x - self.bottom.x) * r
        y = self.bottom.y + (self.top.y - self.bottom.y) * r
        self.drawingTop = Point(x, y)

        if self.depth < self.maxDepth:
            a = math.pi * 0.5 / n
            for i in range(n):
                angleOffset =  a * (n-1) / 2 - a * i + math.pi
                angleOffset *= (0.9 + random.random() * 0.2)
                son = self.__bornSon(self.drawingTop,self.top,angleOffset)
                self.children.append(son)

  首先，函数确定当前树枝的分叉数，也就是当前节点的儿子数量n。可以看到，n随机取值为TreeNode.nBranches的0.5~1.5倍。为了稳妥起见，程序还限定n值至少为1。

  接下来，程序确定当前树枝的描绘顶点，即当前节点的drawingTop。drawingTop的确定也引入了随机性，从bottom顶点出发，往top顶点方向，前进总距离的0.2 ~ 0.4倍，即确定为drawingTop顶点。这里，random.random（）返回[0,1）之间的随机浮点数，这说明，r的取值为0.2 ~ 0.4。

  最后，如果当前节点的深度（depth）小于约定的最大深度（maxDepth），则生成该节点的n个儿子节点，也就是当前树枝的n个分叉。这里的代码比较复杂，涉及了弧度和三角函数的数学知识，简要描述它就是——当前节点/树枝的drawingTop即为儿子节点/分叉的bottom。在当前节点/树枝的drawingTop点，沿当前树枝的伸展方向，向左右各45°，共90°（即 π/2）范围内逐一“均布”生成n个分叉儿子节点。这里的“均布”是大致的，上述代码中的angleOffset被乘以了随机数0.9~1.1。__bornSon（self.drawingTop, self.top, angleOffset）函数以当前树枝的drawingTop为bottom，以“以当前树枝为根的子树”的top为top，生成一个分叉儿子节点，分叉的伸展角度为当前树枝的伸展角度加上偏移角angleOffset。 一个儿子生成完后，再将其加入children列表中。

4.2 生成一个儿子

  紧接着4.1节的内容，本节中__bornSon（）函数需要沿其子树的伸展方向偏转一个偏移角生成一个儿子，具体实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class TreeNode:
        ...
    def __bornSon(self, bottom, top, angleOffset):
        "Born a son of current node, with designated offset angle."
        xWidth = top.x - bottom.x    #Width of sub-tree
        yHeight = top.y - bottom.y   #Height of sub-tree
        angleSubTree = math.atan(yHeight/xWidth) if xWidth !=0 else math.pi/2
        if (angleSubTree < 0 and bottom.y > top.y) or (angleSubTree > 0 and bottom.y < top.y):
             angleSubTree += math.pi
        angleSon = angleSubTree + angleOffset

        r = 0.9 + random.random() * 0.2
        c = math.sqrt(xWidth ** 2 + yHeight ** 2) * r
        xOffset = c * math.cos(angleSon)
        yOffset = c * math.sin(angleSon)
        topNew = Point(xOffset + bottom.x, yOffset + bottom.y)
        return TreeNode(bottom, topNew, self.depth + 1)

  函数首先通过bottom和top之间的相对位置关系，使用反正切函数计算得到子树的伸展角angleSubTree。请注意，由于反正切函数的局限性（值域为（-π/2, +π/2），不能表达全部圆周角度），代码不得不再次通过bottom，top的相对关系对angleSubTree进行修正。接下来，子节点的伸展角angleSon等于子树伸展角加上偏移角。

  有了分支子节点的伸展角angleSon，再借助子树的对角线长度c乘以0.9~1.1随机数，使用正余弦函数计算出分支子节点的top - topNew。然后，函数以topNew为“上”顶点构造一个TreeNode对象，子节点的深度为当前节点深度加1。

  需要特别说明的是，__bornSon（）函数通过TreeNode构造函数生成一个子节点，而该子节点的构造函数又会执行__ generateDescendents（）函数生成其后代。所以，只要我们通过TreeNode的构造函数构造一个根节点（root node），该节点的构造函数会执行__generateDescendents（）生成其子节点，而子结点的构造又会导致子节点的子结点被生成……，最终，生成了一棵完整的树。在生成后代的过程中，并且仅当当前节点的深度小于约定的最大深度时，才会尝试生成后代，因此，递归有恰当的边界条件会导致其终结。这种情况，我们也称递归函数会收敛。

4.3 生成整棵树

  TreeBuilder是一个所谓的“帮助”类，读者可以看到其两个函数都没有self参数，都属于类函数的范畴。也就是说，这两个函数的执行不以TreeBuilder类型对象的存在为前提。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class TreeBuilder:
    def setPara(bottom,top,nBranches=3,maxDepth=8):
        TreeBuilder.bottom = bottom
        TreeBuilder.top = top
        TreeBuilder.nBranches = nBranches
        TreeBuilder.maxDepth = maxDepth

    def buildTree(depthOffset=0):
        TreeBuilder.maxDepth += depthOffset
        TreeBuilder.maxDepth = TreeBuilder.maxDepth \
                               if TreeBuilder.maxDepth <=10 else 10
        TreeBuilder.maxDepth = TreeBuilder.maxDepth \
                               if TreeBuilder.maxDepth >=2 else 2

        print("Build a tree, branches:{},depth:{}.".
              format(TreeBuilder.nBranches,TreeBuilder.maxDepth))
        TreeNode.maxDepth = TreeBuilder.maxDepth
        TreeNode.nBranches = TreeBuilder.nBranches
        t = TreeNode(TreeBuilder.bottom,TreeBuilder.top)
        RenderHelper.showTree(t)
... 
TreeBuilder.setPara(bottom=Point(1024/2,768-20),
                       top=Point(1024/2,768*0.1))
TreeBuilder.buildTree()

  在主程序中，我们首先通过TreeBuilder.setPara（）函数设置了将要生成的树的bottom“下”顶点及top“上”顶点。1 024和768是窗口的宽度和高度，可以看出，bottom左右居中，距窗口下边缘20个像素；top左右居中，距窗口上边缘10%。建议的树枝分叉数nBranches以及树的最大深度maxDepth均使用了默认值。

  接下来，主程序调用TreeBuilder.buildTree（）函数构造并显示一棵树。这个函数允许通过一个深度偏移量来改变原设定最大深度。在调整完深度并把深度及建议分叉数存入TreeNode.maxDepth和TreeNode.nBranches后，函数简单地构造了一个TreeNode对象t，这个t即为树的根节点。请注意，由于前小节所述的递归的原因，这个以t为根的树会被完整地生成出来，其深度为TreeNode.maxDepth。

  作者对TreeBuilder.maxDepth进行了限定，不允许其超过10。这是因为树的节点的总数量随深度呈指数级增长，超过10的深度的树可能需要非常长的运行时间，甚至可能会超过你的计算机的存储或计算能力。

  在buildTree（）函数的最后，执行语句RenderHelper.showTree（t）将树显示出来。

5. 树的显示

5.1 计算机里的颜色显示

  画家可以仅凭“红”“绿”“蓝”调出他所需要的所有颜色，计算机也可以。计算机通常用3个字节来表示一种颜色，从左往右分别表示红、绿、蓝3种颜色成分，取值为0~255，即十六进制的0x00 ~ 0xff。通过3种颜色成分的不同组合，我们可以得到任意颜色。这种用红（Red）、绿（Green）、蓝（Blue）来组合构成颜色的模型称为RGB模型。常用的RGB数值及说明如表1所示。

  印刷业使用的配色方案跟计算机里的有所不同，使用青（Cyan）、品红（Magenta）和黄（Yellow）来组合构成所有颜色，即所谓的减色法，又称为CMY模型。

5.2 树的遍历

  显示一棵树就是要迭代列举树的全部节点，并将其全部画出来。列举树的全部节点，又称为树的遍历。作者在这里使用了树的宽/广度优先遍历算法（breadth first search）。其代码如下所示：

1
2
3
4
5
6
7
8
9
10

class TreeNode:
    ...
    def bfs(self):                     #breadth first search
        nodesQueue = [self]
        while True:
            if len(nodesQueue)==0:
                break
            x = nodesQueue.pop(0)
            yield x
            nodesQueue.extend(x.children)

  为了便于读者理解，作者以图5所示的这棵小树为例说明宽度优先遍历的过程。执行A节点的bfs（）函数，队列nodesQueue初始化为[A]。遍历过程将一直持续到nodesQueue队列为空，即len（nodesQueue）==0为止。

  首先，从队列中弹出A并yield。请注意，这里的bfs（）函数被写成了生成器函数，关于生成器函数的工作原理，请参考本书A.1中的内容。这里简单地将yield x语句理解为将x节点“抛”给使用方即可。

  A被yeild后，A的儿子节点B和D被加入nodesQueue （队列变为[B,D]）中。接下来，弹出并yield B，B的儿子节点C被加入nodesQueue （队列变为[D,C]）。接着，弹出并yield D，D的儿子节点E被加入nodesQueue （队列变为 [C,E]）。接下来，弹出并yield C，C没有儿子，故nodesQueue只剩下一个节点E。接着，E被弹出并yield，E的儿子F被加入nodesQueue （队列变为[F])。最后，F被弹出并yield，F是叶子，没有儿子可以加入nodesQueue，所以nodesQueue为空，全部节点已经被成功列举，遍历结束。

  如果列出全部节点的列举顺序，应该是A、B、D、C、E、F，这正好是树的节点一层一层逐层列举的结果。这种逐层列举树的全部节点的遍历方法称为“宽度优先”。与“宽度优先”对应的是“深度优先”，“深度优先”的内容在数据结构课程中会深入介绍。

5.3 树的显示

  同样地，RenderHelper是一个帮助类，可以在不经过实例化的情况下使用其类函数。canvas是由主程序设置的Tkinter“画布”。showTree（tree）函数负责在canvas上把树“画”出来。具体实现过程为：

1
2
3
4
5
6
7
8
9
10
11

class RenderHelper:
    canvas = None
    def showTree(tree):
        "Render a tree on canvas."
        assert RenderHelper.canvas != None, "Please set canvas first."
        RenderHelper.tree = tree
        for x in RenderHelper.canvas.find_all():
            RenderHelper.canvas.delete(x)
        for x in tree.bfs():
            RenderHelper.__renderNode(x)
        RenderHelper.canvas.update()

  可以看到，showTree（）首先并断言了canvas的可用性。然后，删除了canvas内已有的全部内容。接下后，通过for x in tree.bfs（）遍历列举tree的全部节点x，逐一调用_ _renderNode（x）在画布上将节点“画”出来。这里所谓的“画”其实只是在canvas的内部数据表达中增加相关元素（如线、椭圆或其他图形），真正要把画布的内容展示在计算机屏幕上，还需要执行canvas.update（）函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class RenderHelper:
   ...
   def __renderNode(node):
       "Render a TreeNode."
       colorFill = "#{0:0>2x}{0:0>2x}{0:0>2x}".\
           format(int(0x60 * node.depth / node.maxDepth))
       RenderHelper.__drawLine(node.bottom,node.drawingTop,
           colorFill=colorFill,width=1.5 ** (node.maxDepth - node.depth))
 
       if not node.children: #draw leaf if it is a leaf
           red = 0xff *node.drawingTop.y / RenderHelper.tree.drawingTop.y
           red = int(red * (0.8 + random.random() * 0.4))
           red = red if red <= 0xff else 0xff
           colorFill = "#{0:0>2x}9000".format(red)
           RenderHelper.canvas.create_oval(
               node.drawingTop.x - 3,node.drawingTop.y - 3,
               node.drawingTop.x + 3,node.drawingTop.y + 3,
               fill=colorFill)
       RenderHelper.canvas.update() #This sentence for contruction show

   __renderNode（node）函数负责在画布中“画”一个节点。首先，画出这个节点所代表的树枝。

1
2

colorFill = "#{0:0>2x}{0:0>2x}{0:0>2x}".\
                   format(int(0x60 * node.depth / node.maxDepth))

  colorFill为形如”#101010”的RGB模型颜色字符串，在这里，R，G，B 3个值相等且与当前节点的深度有关。深度越浅，说明节点离树根越近，colorFill取值接近”#000000”，黑色越深。当深度较大时，说明节点离叶子较近，colorFill取值接近”#606060”，黑色较浅，为灰色。

  __drawLine（）函数从节点的bottom至drawingTop画一条线表示树枝，颜色即上述colorFill，而线宽则同样与节点深度有关，深度越浅，树枝越接近树根，线越宽。

  当节点的儿子列表为空时，说明节点是叶子节点，此时需要画一个实心圆点表示树叶。树叶本来是绿色（取值0x90）的，但作者刚才正好从美丽的重庆大学虎溪校区泛黄的银杏树下走过，决定给树叶加点“红”色。红色成分的多少取决于树叶的描绘高度，越靠近树顶，红色越少，树叶越绿；越靠近地面，红色越多，树叶越黄。上述的colorFill字符串格式化的结果为”#309000”这样的字符串，绿色为0x90，红色为0x30或者其他值，蓝始终为0x00。注意，红色成分的多少也加入了一些随机因素。

  canvas.create_oval（）函数在画布上创建一个实心圆树叶，该实心圆以drawingTop为圆心，colorFill为填充色。这个函数本来是画椭圆的，但由于正圆是椭圆的特例，所以也可以用来画正圆。

  __renderNode（）函数的最后一行为RenderHelper.canvas.update（）。update（）会在显示器上实际渲染画布的内容，所以该函数执行至少要“花费”一个显示帧的时间。考虑到显示器的刷新频率一般是60Hz，这意味着程序每秒钟只能“画”出大约60个节点。所以，如果该行代码存在，你可以在计算机上看到树被一点点的画出来，并且还可以根据树枝、叶片在界面上出现的先后顺序来理解树的“宽度优先遍历”算法。读者可以删除该行代码，再运行试一试。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class RenderHelper:
    ...
	def __drawLine(pt0, pt1, width, colorFill, minDist=10):
        dots = RenderHelper.__generateDotsSequence(pt0,pt1,minDist)
        RenderHelper.canvas.create_line(dots,fill=colorFill,width=width,
                                        smooth=True)

    def __generateDotsSequence(pt0,pt1,minDist):
        dots = []
        dx, dy = pt1.x - pt0.x, pt1.y - pt0.y
        c = math.sqrt(dx ** 2 + dy ** 2)
        n = int(c / minDist) + 1

        xPrev,yPrev = pt0.x,pt0.y
        for i in range(n):
            xOffset = dx * i / n
            yOffset = dy * i / n
            if i > 0:
                xOffset += minDist * (0.5 - random.random()) * 0.25
                yOffset += minDist * (0.5 - random.random()) * 0.25
            x,y = pt0.x + xOffset,pt0.y + yOffset
            dots.extend([xPrev,yPrev,x,y])
            xPrev,yPrev = x,y
        dots.extend([xPrev,yPrev,pt1.x,pt1.y])
        return dots

  __drawLine（）函数负责从pt0 （bottom）到pt1 （ drawingTop）画一条宽度为width，颜色为colorFill的实心线来表示一根树枝。但现实中的树，树枝可能不完全是直的。所以，借助__generateDotsSequence（）函数，作者以minDist=10为间距，将树枝分成多个小段，并加入一些随机因素。最后，再用canvas.create_line（）将多点线画出来，尽可能模仿现实世界中树枝的模样。

6. Tkinter循环

  本章程序的主体代码如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

tk = tkinter.Tk()
tk.title("Build Tree")
canvas = tkinter.Canvas(tk,width=1024,height=768,bg="#ffffff")
canvas.pack()

RenderHelper.canvas = canvas
TreeBuilder.setPara(bottom=Point(1024/2,768-20),
                    top=Point(1024/2,768*0.1))
TreeBuilder.buildTree()
 
tk.bind("n", lambda evt: TreeBuilder.buildTree())
tk.bind("=", lambda evt: TreeBuilder.buildTree(depthOffset=1))
tk.bind("+", lambda evt: TreeBuilder.buildTree(depthOffset=1))
tk.bind("-", lambda evt: TreeBuilder.buildTree(depthOffset=-1))
tk.mainloop()

  在主程序中，我们创建了一个tkinter对象，并生成了1 024（长）×768（宽）像素的背景色为白色的画布（canvas）。然后，建造并显示了一棵树。接下来，我们在程序中创建了几个快捷键，程序运行中，当你按下n时，TreeBuilder.buildTree（）会被执行，这将建造并显示一棵新树。按下+或者=时，TreeBuilder.buildTree（depthOffset=1）会被执行，系统会尝试将树的深度加1并建造和显示一棵新树。按下-时，TreeBuilder.buildTree（depthOffset=-1），系统会尝试将树的深度减1并建造和显示一棵新树。

  此处的lambda表示匿名函数，它将带有实参的TreeBuilder.buildTree（depthOffset=1）封装成一个没有名字的函数。tk.mainloop（）将执行所谓的消息循环， Tkinter将不断地循环等待来自用户的命令并执行，直到用户关闭Tkinter窗口。

7. 小结

  本实践的主要用意在于帮助读者掌握和运用面向对象的程序设计方法、递归算法以及树的数据结构表示方法等。Tkinter库的使用不是重点。作为Python自带的标准GUI工具包，Tkinter库在小型应用中仍有一席之地，但当应用的规模略大时，作者认为不太实用。在本书中，作者着重介绍了另一种更强大的GUI工具包——PyQt。