递归树的显示

目标&＃xff1a;显示每层节点数不定的递归树&＃xff0c;不同的类别用不同的颜色表示

所用python库&＃xff1a;matplotlib

1. 初始化窗口 

步骤&＃xff1a;

• 计算所需画面大小&＃xff0c;包括图幅高度height 和图幅宽度width。图幅宽度主要取决于叶子节点数目。a. 首先需要计算叶子节点的数目&＃xff0c;b. 然后需要定义node的半径radius和同一层级两个node之间的距离nodeInterval&＃xff0c;本次设置nodeInterval为radius的n倍&＃xff0c;n可以自己给定。最后图幅所需要的宽度width&＃61;(treeWidth &＃43; 1) * nodeInterval。默认使用正方形画布&＃xff0c;则height &＃61; width。最后用计算出来的height, width设置画布x轴和y轴的范围。
• 计算层间距disVec。首先计算树的深度maxDeepth&＃xff0c;然后用图幅高度height除以树的深度即可得出每层之间的纵向距离&＃xff0c;即disVec &＃61; height/(maxDeepth&＃43;1)&＃xff1b;
• 最后计算root的xy坐标&＃xff1a;xStart, yStart。root 位于图幅正中心&＃xff0c;距离页面顶部一个 disVec 距离。 
• 函数返回值&＃xff1a;返回根节点坐标、node的半径radius 和 树的纵向深度间隔disVec&＃xff08;用于递归画下一层节点&＃xff09;。因为是递归构建&＃xff0c;所以当前子树也就是当前父节点一直在变化&＃xff0c;所以需要事先计算好根节点&＃xff0c;作为递归的传入参数。

def creatWindow(self, radius &＃61; 300):&＃39;&＃39;&＃39;———————— O ————————————O———— ————O————-O--O--O- -O--O--O- radius &＃61; 2 #节点的半径nodeInterval &＃61; 4 * radius #定义为两个节点之间的距离,即--&＃39;&＃39;&＃39;#定义节点间距n &＃61; 1nodeInterval &＃61; n * radius# 定义图幅长宽&＃xff0c;默认为正方形图幅&＃xff0c;height&＃61;widthtree &＃61; self.treetreeWidth &＃61; self.getNumLeafs(tree)treeDepth &＃61; self.getMaxDepth(tree)width &＃61; (treeWidth &＃43; 1) * nodeIntervalheight &＃61; widthaspect &＃61; height/widthfig &＃61; plt.figure(figsize&＃61;(11, 11*aspect))plt.xlim(0, width)plt.ylim(0, height)#定义层间距disVec &＃61; height/(treeDepth&＃43;1)#给定根节点坐标xStart &＃61; int(width/2)yStart &＃61; height - disVec return fig, xStart, yStart, radius, width, disVec

重点&＃xff1a;计算树的宽度和深度。

• 计算树的宽度&＃xff1a;只要存在children&＃xff0c;就进入下一层&＃xff0c;直到遇到叶子节点. 每遇到一个叶子节点计数就加1&＃xff0c;即numLeafs &＃43;&＃61;1. 遍历完整棵树之后&＃xff0c;numLeafs就是树的宽度。

def getNumLeafs(self, tree):numLeafs &＃61; 0children &＃61; tree.childrennumChildren &＃61; len(children)if numChildren > 0:for childNode in children:branchNumLeafs &＃61; self.getNumLeafs(childNode)numLeafs &＃43;&＃61; branchNumLeafselse:numLeafs &＃43;&＃61; 1return numLeafs

• 计算树的深度&＃xff1a;只要存在children,就进入一下层&＃xff0c;同时深度值加1&＃xff0c;即&＃xff1a;深度 &＃61; 1 &＃43; 子树深度。当遇到叶子节点是&＃xff0c;返回深度值1。同一个parent下面的每个child, 遍历计算深度后&＃xff0c;只取他们中最大的深度值。

def getMaxDepth(self, tree):&＃39;&＃39;&＃39; 如果只有根节点&＃xff0c;最大深度为1;如果有子节点&＃xff0c;maxDepth &＃61; 1 &＃43; getHeight(child), 1 为根节点自身深度遍历所有子节点&＃xff0c;取最深的那个深度&＃39;&＃39;&＃39;maxDepth &＃61; 0children &＃61; tree.childrennumChildren &＃61; len(children)if numChildren > 0:for childNode in children:branchDepth &＃61; 1 &＃43; self.getMaxDepth(childNode)if branchDepth > maxDepth:maxDepth &＃61; branchDepthelse:maxDepth &＃61; 1return maxDepth

2. 画递归树

思路&＃xff1a;

        整个递归树包含 节点 和 边 两类。当我们把每个节点看作一棵小树&＃xff0c;一颗只包含边的小树。这个问题就简化为如何画出一个节点及其存在可能的边。依然是递归的方法。

过程&＃xff1a;

• 画当前节点&＃xff1b;
• 判断当前是否存在children,如果存在就画边&＃xff0c;负责就是叶子节点&＃xff0c;不画边。
• 更新节点&＃xff0c;直到叶节点。

难点&＃xff1a;确定子节点位置坐标。

&＃39;&＃39;&＃39;

                          O

                 O               O

           -O--O--O-   -O--O--O- 

&＃39;&＃39;&＃39;

如上红色父节点存在三个子节点&＃xff0c;每个节点占据父节点空间的1/3, 即&＃xff1a;

childWidth &＃61; parentWidth/numChildren&＃xff0c;则它们x轴坐标分别为&＃xff1a;

childWidth *&＃xff08;0&＃43;1/2&＃xff09;&＃xff1b;

childWidth *&＃xff08;1 &＃43; 1/2),&＃xff1b;

childWidth *&＃xff08;2&＃43;1/2)。

因此可以得出&＃xff0c;子节点位置坐标为childWidth *(i&＃43;1/2) &＃61;parentWidth/i * *(i&＃43;1/2) &＃xff0c; i为子节点个数。

对于左子树&＃xff0c;按照上述计算即可。但是对于右子树&＃xff0c;要根据父节点的左侧范围计算坐标&＃xff0c;上述例子右侧节点的左侧范围为图幅的1/2处&＃xff0c;所以子节点的坐标为&＃xff1a;parentWidth *1 &＃43; childWidth *(i&＃43;1/2).

最后综合左、右子树&＃xff0c;最终的子节点的坐标计算公式为&＃xff1a;parentWidth * j &＃43; parentWidth / i*(i&＃43;1/2)。其中&＃xff0c;j为上一层父节点的编号, i为子节点个数。

画递归树的函数draw 一定要单独写一个函数&＃xff0c;因为当前节点一直在变。

def draw(self, tree, xStart, yStart, radius, width, disVec, j&＃61;0):#先画当前节点 self.drawNode(tree, xStart, yStart, radius)#如果有子节点&＃xff0c;递归画子节点children &＃61; tree.childrennumChildren &＃61; len(children) if numChildren > 0: childBrachWidth &＃61; width/numChildrenfor i, childNode in enumerate(children):xEnd &＃61; width * j &＃43; childBrachWidth * (i &＃43; 0.5)yEnd &＃61; yStart - disVecself.drawEdge(xStart, yStart, xEnd,yEnd)self.draw(childNode, xEnd, yEnd, radius, childBrachWidth, disVec, i)def drawNode(self, node, x, y, radius&＃61;20):name &＃61; node.data.componentNamecolor &＃61; self.colors[node.data.label]plt.scatter(x,y,s &＃61; radius, c&＃61;color, edgecolors&＃61;color, marker&＃61;"o")plt.text(x-radius/3, y-radius, name, fontsize&＃61;13)def drawEdge(self, xStart, yStart, xEnd, yEnd):x &＃61; (xStart, xEnd)y &＃61; (yStart, yEnd)plt.plot(x,y,&＃39;g-&＃39;)

3. 最后将上述函数整理到show_Tree类中&＃xff0c;并用showTree函数调用


class show_Tree:def __init__(self, tree, colors &＃61; None):self.tree &＃61; treeself.colors &＃61; colors def showTree(self):tree &＃61; self.tree#1. 构建窗口_, xStart, yStart, radius, width, disVec &＃61; self.creatWindow()#2. 画树self.draw(tree, xStart, yStart, radius, width, disVec)#3. 保存即显示f &＃61; plt.gcf()plt.legend()#窗口最大化再保存比较清楚plt.show()f.savefig(&＃39;splitTree.png&＃39;)plt.close()def get_colour_name(requested_colour):try:closest_name &＃61; actual_name &＃61; webcolors.rgb_to_name(requested_colour)except ValueError:closest_name &＃61; closest_colour(requested_colour)actual_name &＃61; Nonereturn actual_name, closest_namedef randomColor(labels):num &＃61; len(labels)colors &＃61; [colorsys.hsv_to_rgb(i/num, 1, 1) for i in range(num)]colors &＃61; [(int(c[0]) *255, int(c[1]) *255, int(c[2]) *255) for c in colors]return colorslabels &＃61; []#### the category of component
colors &＃61; randomColor(labels)
colorDict &＃61; {key:get_colour_name(value)[0] for key,value in zip(labels, colors)}
p &＃61; show_Tree(tree, colorDict)
p.showTree()

 结果展示&＃xff1a;