龙空技术网

分形——雪花与上帝的指纹2 :生长之美——生生不息的二叉树

宇宙文明领路人 143

前言:

眼前你们对“二叉树的形状”大概比较注意,大家都需要了解一些“二叉树的形状”的相关资讯。那么小编也在网上收集了一些有关“二叉树的形状””的相关资讯,希望兄弟们能喜欢,各位老铁们快快来学习一下吧!

女士们,先生们,老少爷们儿们!在下张大少。

无边的奇迹源于简单规则的无限重复。

——本华·曼德博(Benoit Mandelbrot)

分形改变了人们观察世界的方式,也改变了艺术家们描绘自然的手法。他们无需再对着错综复杂的现实世界循规蹈矩地精雕细刻,相反,他们清空万物,一切从头开始,满怀着一种试图扮演上帝七天创造万物的冲动和自信。在空白的画布上勾勒自己心中理想的秩序。此时,艺术家俨然就是造物主,再不受传统绘画技术的教条的禁锢。更何况懂分形的艺术家自信已经掌握了数学。正如俗语所云,"众叶成枝,众枝成木,众木成林",他们只需要描绘出一片树叶或是一截树杈,然后反复迭代很多次,就能画成一片森林。故而,分形树一直是分形领域一个的重要话题。

最常见的一种分形树模型是对称二叉树。如下图6.2.1,以长度为1的垂直线段作为树干,顶部分叉成两个分支,每一个分支与树干的延长线所加角度都为θ(0°< θ < 180°),每一个分支的长度都是r (0 < r < 1)。这两个分支又构成了子树的主干,子树又按照同样的规则分成两个更小分支。夹角仍然为θ,4个新分支的长度则都是r^2。根据这个规则不断地添加更小的分支,便得到了对称二叉树。

图6.2.1 对称二叉树模型

显然,在这个模型中,对树的形态起决定性作用的是θ和 r。

我们先把θ固定为45°,改变r的取值。下图6.2.2a-c是r分别取0.5、0.6、0.7,然后迭代10次的情况。可以看到,r=0.5时,树的样子稀稀落落,像棵枯树;r=0.6时,树的形态比较正常;r=0.7时,树显得异常枝繁叶茂。

图6.2.2a θ=45°,r=0.5

图6.2.2b θ=45°,r=0.6

图6.2.2c θ=45°,r=0.7

接下来,我们把r固定0.6,观察θ的改变对二叉树形态的影响。下图6.2.3a-g是θ取不同数值时迭代10次的情况。可以看到,当θ<90°时,树的形态基本正常。当θ≥90°时,树的样子就有些不合常规了。不过,自然界中确实也有些树的树枝是水平生长或向下生长的,比如松树、垂枝梅、龙爪槐……

图6.2.3a θ=30°,r=0.6

图6.2.3b θ=45°,r=0.6

图6.2.3c θ=60°,r=0.6

图6.2.3d θ=90°,r=0.6

图6.2.3e θ=120°,r=0.6

图6.2.3f θ=135°,r=0.6

图6.2.3g θ=150°,r=0.6

想必你已经发现,如果比例因子r太小,树的分支就会稀稀落落,整棵树形如枯木朽株。如果r太大,分支就会彼此重叠,绿盖如阴,遮天蔽日。如果左右两边分支刚好接触且不重叠,这棵树就一定非常特殊。研究表明,对于每个角θ,都有一个唯一的比例因子rsc,使得对称二叉树刚好能够左右接触且不重叠。而如果比例因子rsc又刚好等于黄金比例0.618,那么这棵树就又拥有了极其独特的美学特征,我将之称为"黄金对称二叉树"。计算可知,黄金对称二叉树一共有4种,分别对应于θ为60°、108°、120°和144°,如下图6.2.4。

图6.2.4 四种黄金对称二叉树

如图6.2.5,以θ=60°的黄金对称二叉树的树根为旋转中心,一个逆时针转120°,另一个顺时针转120°。3棵树在树枝尖端相交,整体恰好可以放入一个正三角形中。

图6.2.5

如图6.2.6,仍然是θ=60°的黄金对称二叉树,6个拼在一起,可以放进正六边形之中,6棵树的树根构成了正六边形的顶点。

图6.2.6

108°跟五边形和五角星有不解之缘。如图6.2.7,5棵θ=108°的黄金对称二叉树可以被放置在正五边形内,5棵树彼此接触,但不会重叠。

图6.2.7

如图6.2.8,5棵二叉树也可以被放置在正五边形外侧。按这种方式摆放,一棵树的顶部边缘与相邻树的侧边缘共线。将这五条线延长至彼此相交,便可以得到黄金五角星。

图6.2.8

如图6.2.9~10,θ=120°的黄金对称二叉树与60°类似,同样可以放进正三角形和正六边形中。

图6.2.9

图6.2.10

θ=144°的黄金对称二叉树就比较有意思了,如图6.2.11,以树根为旋转中心,每隔72°放置一棵树,此时它们的树枝尖端恰好彼此相连,形成一片"五角科赫雪花"。

图6.2.11

关于分形树的另一种常见构造是毕达哥拉斯树,从一个正方形开始。构造一个直角等腰三角形,它的斜边是正方形的顶边。沿着这个等腰三角形的另外两边各构造一个正方形。在两个新方块上重复这个构造。图6.2.12是经过10次迭代的家毕达哥拉斯树。这种构造以古希腊数学家毕达哥拉斯命名,因为它的构造验证了毕达哥拉斯定理,即直角三角形两边的正方形面积之和等于直角三角形斜边的正方形面积。

图6.2.12

将毕达哥拉斯树与前文中的对称二叉树构造相比可以发现,尽管两种树的树干不同,但这两棵树的叶子看起来非常相似。

附在正方形的三角形未必仅限于等腰直角三角形,可以是任意角度的直角三角形。下图6.2.13显示了30°、60°、90°的直角三角形迭代10次的结果,树冠明显朝一侧倾斜,同时出现了大大小小很多螺旋。

图6.2.13

现实中的树木也是如此,并不完全左右对称,也并非总是两个分支。如图6.2.14,信手画几根线,迭代若干次之后,一棵足以以假乱真的大树便跃然纸上。当然,你说这是一片树叶亦无不可。

图6.2.14

正如本华·曼德博所言,"无边的奇迹源于简单规则的无限重复",万物的生长密码或许尽在于此。

青山不改,绿水长流,在下告退。

转发随意,转载请联系张大少本尊

标签: #二叉树的形状