不堪回首

第一篇前就想画了，没有底气只能说打印。曾经手画过，也显示了更紧凑的234B树，还盗过图。“直男”应该是女程序员给她男朋友取的，她知道他的心底压满了栈，只能直进直出；也期待着出栈的欣喜。

图

0到49插入的红黑树

略显粗糙

最美公式

${\log }_{2}n$

${\log }_{2}n$是完全二叉树的层数，其中$n$是接点数；只有一个结点的根结点是0层。书上原话：**性质4具有$n$个结点的完全二叉树的高度$k$为$\lfloor {\log }_{2}n\rfloor$。⌊ ⌋向下取整。**从上图可以看出，画图的代码里构造了完全二叉树，用count += 1 #计数得到公式中的$n$,从而求出层数。再用层数计算$x,y$坐标。

>>> import math
>>> math.log(1,2)
0.0
>>> 

$2^n$

每层的结点数。代码$step=(1/2)\ast ((1/2)\ast \ast level)\ast 1500$ #用结点数计算$x$的间隔$step$,根是$\frac{1}{2}$的宽度，下一层就再乘以一个$\frac{1}{2}$。x =(count - 2**level)step2 + step 便求出了x坐标。

NIL节点（空叶子节点）为黑色

红黑树性质里都有说这个NIL结点。之前以为没有用。这次画图用到了，它是画图结束的关键，红黑树远远不是完全二叉树。只要有NIL结点就还要往下画一层。endlevel = 1 #null层，添加一个变量作为最后层的标志。

准备工作

海龟可以画直线和圆，显示数字；结点类可以添加xy坐标，树类可以添加层、接点数量属性，还可以结合后根序倒推。还有很多失败的过程，要追求的是逻辑编程的简洁。

不用担心本子不够画了

python">	from turtle import *import mathdef draw(self, node):#不用担心本子不够画了if node is None: returnsetup(width=1600, height=900) #画布大小setworldcoordinates(-50, -850, 1550, 50) #50像素页眉speed("fastest")#最快temp = [] #队列先进先出temp.append(node)#入队 step = 1/2 #根结点居中 x,y = 0,0 #结点坐标count = 0 #结点计数，完全二叉树level = 0 #层数endlevel = 1 #nul层，最后层split = True #重在一起的处理while temp:q=temp.pop(0)#出队count += 1 #计数level = int(math.log(count,2)) #当前层y = 0 - 50 * level #y下降step = (1/2)**(level+1) * 1500 #x的间隔stepif count == 2**level:x = stepelse:x =(count - 2**level)*step*2 + stepif step < 10:#重在一起处理if split:goto(x-3,y)split = Falseelse:goto(x+3,y)split = Trueelse:goto(x,y)color(q.color) #着色                if q.val != -1: #nul接点不显示 write(q.val, font=("微软雅黑", 10, "normal"))color('black') #着色完恢复if q.left and q.right: #下一层temp.append(q.left)temp.append(q.right)endlevel = level + 1 #nul层，最后层要增加elif q.left:temp.append(q.left)temp.append(RBTnode(-1))endlevel = level + 1elif q.right:temp.append(q.right)temp.append(RBTnode(-1))endlevel = level + 1elif endlevel >= level:temp.append(RBTnode(-1))temp.append(RBTnode(-1))getcanvas().postscript(file="filename.ps")#保存图片

说明

1. 在还有子结点的情况下，endlevel = level + 1表示还有一层nil.
2. 只画一层nil,即没有子结点但endlevel >= level的时候也入队RBTnode(-1)。再一层的时候当前层level会大于没有+1的endlevel。
3. RBTnode(-1)，在空的地方添加，以构造完全二叉树。画图的时候（-1）就不显示。

只能到九层了

第八层就重叠了，还特殊处理了才行。还好，可以从任意结点开始画。

从任意结点画

从31开始画：

>>> rb.draw(rb.root.right.right)

‘31’开始画的红黑树

观止

所见即所得