《树的遍历》（一文读懂《最强大脑》最强选手于湛的空间辨别术）
上周，我看了最新一期《最强大脑》
里面提到了“树的遍历”
这本来是数据结构术语
但于湛用来判断空间
由此，VRLAND为大家做了期专题
关于“树的遍历”
先看下短片，了解下于湛
https://v.qq.com/txp/iframe/player.html?vid=h0366tipi8s&width=500&height=375&auto=0
《树的遍历》
文/璞聿
永远不会迷路的视觉空间能力
最新的一期《最强大脑》节目里，一位选手挑战的“一眼辨山”令我印象深刻。选手通过观察嘉宾挑选的三张庐山的局部照片，成功的从庐山的等高线图上找到拍摄该照片的位置和角度。
在采访中，该选手表示他从小对空间几何非常痴迷，他说，在他的眼里世界就像很多结点和线条连成一棵树的形状，想知道从A处走到B处的路径，只需要在“树”上找到A点走到B点的路径，也就是说他在现实空间中走过的路在他的脑海里是对树结点和叶结点的遍历。
只要给他时间，他就可以在脑海中找到唯一正确的那条路，所以他可能永远都不会有迷路的体验。
庐山等高线图
简单的来解释就是，只要知道一些数据，他就可以在脑海里可以轻易地建立一个立体的地图，只是这个地图是用他自己的方式建立的，也只有他自己可以看懂啦。
在认知心理学上，我们称这种能力为视觉空间能力，你可以想象一下你面前有一个圆锥体，然后再想象俯视、平视和仰视能过够看到的形状，这就是简单的视觉空间能力。
这种能力我们每个人生来都有，只是我们本身没有于湛这么强大的天赋，也不曾接受过于湛经历过的巨量训练，因此完全无法想象出庐山这个长达25千米，宽10千米的巨大模型在脑海里旋转以后，不同的角度是什么样子。
圆锥的三视图
在计算机世界里，树的结构，树的思想在各大领域都发挥着巨大的作用，无论是数据存储还是二维、三维图像的定位识别都有着。
从只能识别0和1的计算机到现在可以感知空间的人工智能，一切技术都有树的影子。
从游戏到树形图
迷尼游戏板
在很早以前，人们就发明了一个叫做“迷尼游戏板”的骗局。如下图所示，在一块倾斜放置的等腰三角形的木板上钉上八行铁钉，自上而下每一行多一钉一颗铁钉，两个铁钉之间的间距刚刚好可以让一个金属小球通过（如图所示）。
摆摊的人定下的游戏规则是：
玩游戏的人从木板的顶部放入一球，收费2元，让小球自由落下，如果落入①②③④号球槽，分别奖励4元，2元，0元和-2元。
在这个游戏里，小球在下落的过程中每遇到一颗钉子就有50%的概率向左边落下，也有50%的概率向右边落下，然后掉落至新的一层再遇到另一颗钉子，最终落在某个凹槽中。
因此我们可以将小球碰到的铁钉用线连接起来，然后找到所有可能的路线和能够到达①号球槽的路线，这样我们就可以得出玩家可以赢钱的概率，计算的结果是，玩家能够赢到钱的概率仅仅只有1.56%。
树
咳咳，我们是一个做VR的号，回归正题。大家可以想象一下，将小球走过的点用线连接起来，像不像一棵树！
在这个游戏中，小球只能够向左或者向右滚动，也就是从一个结点最多有两条路径可以向下延伸，我们将这种一个结点只有两个分支的树称作二叉树。
二叉树是最简单的树，也是最常用的树，在很多领域都有广泛的使用。
我们可以通过了解二叉树的特点来了解更加高级的树型结构。
今天我们想给大家介绍主要是计算机世界的基础二叉树，广泛应用于图像处理图像处理、空间数据索引、2D中的快速碰撞检测、存储稀疏数据等领域的四叉树和主要应用于3D图形处理的八叉树。
比如说，通过了解二叉树的遍历，我们来看一看于湛观察世界的遍历法。
从下图我们可以看到，一棵最简单的树只包含三个结点，我们分别用前序遍历、中序遍历和后序遍历来看得到的结果是什么。
前序遍历：先遍历根节点，再遍历左子树，在遍历右子树
中序遍历：先遍历左子树，再遍历根节点，再遍历右子树
后序遍历：先遍历左子树，再遍历右子树，再遍历根节点
实际上“前序”“中序”和“后序”是根在遍历过程中的次序，从左往右遍历的大方向是不变的。
树的遍历
如上图所示，前序遍历得到的结果是ABC，中序遍历得到的结果是BAC，后序遍历得到的结果是ABC。
在一个最简单的，只有一个根节点和两个叶节点的二叉树中，我们可以直观的看到三种遍历方式依次到达每一个节点的不同路径。
如果是更复杂的二叉树，用这三种遍历方法也可以得到唯一的一个所有结点的排列。
从这里我们可以看出，二叉树的遍历就是没有重复的去看到每一个结点的信息，这样既可以保证对数据完整的读取，也能够提高读取效率（因为不可能有重复）。
树既不是一种实体的数据，也不是一个实际存在的结构，树的本质是一种逻辑结构，树的作用是优化计算机对数据查询。
二叉树在自然界中也有直观的体现，根据二叉树的定义——每个节点最多有两个分支的树——进行判断，自然界里大部分的树都属于二叉树：对于叶互生的植物类群，所有分岔的地方，全部都是二分枝。
所以，没有特殊情况，所有互生叶的植物，分支类型，都是二叉树。
而一旦违背这个逻辑，就是不成立的空间。
自然界中的树枝生长图
另外，自然界中还有一种特别的植物，它们可以称为满二叉树。
一般的植物分支是由老枝+新枝组成，新生的枝条也不如老枝粗壮，对应二叉树中的定义，也就是每个左右子节点互不成镜像，差异较大。
满二叉树则是一棵每一个双亲节点都有两个子节点的树，其性质之一是每一个左右子节点互成镜像。
也就是说，自然界中那些类似“满二叉树”的植物，每一次分支的左右分支是一样大的。
这类植物在二叉分支的时候，直接一分为二，同时产生两个顶端分生组织，并且这两个新生部分的生长速度几乎相同。
这类特殊的植物常见于早期发展出的藻类、苔藓和蕨类等植物类群中，有不少古生物化石就体现了这样的形态。
自然界中的满二叉树
计算机世界的数据和现实世界的树如此相似，游戏开发者首先就利用树形结构来模拟现实世界中树的肉体运动，他们创造了一种名为Verlet的物理算法来模拟树的物理运动，实现大规模的树群效果。
这种算法中树的形态就是二叉树的形式。
对一棵树来说，它所拥有的数据类型主要有两种：节点和约束。
节点用于表述树形结构的分叉点，
约束则表示点与点之间的关系。
我们把外来的碰撞的物体用一个半径为R的圆来表示，把每一个叶子节点用半径为S的圆来表示，碰撞的过程就是检测S和之间是否发生了叠加，产生了叠加就相当于产生了碰撞。
Verlet的物理算法
在游戏世界里，树也有着相当重要的作用。
对人类来说，想在一张照片上找到一个点非常容易，如果机器想做到这一点就比较难了。因为在电脑的世界里，我们看见的图片只是一堆按顺序排列的数据。
在2D的游戏中，我们要实现互动就必须要检测碰撞，人类可以观察到的，比如超级马里奥中马里奥跳起来用头碰到砖块，怎么样才能让机器知道马里奥的头碰到了砖块呢，这时候就需要用到四叉树了。
二叉树是每一个节点有两个分支，那么四叉树就是一个节点最多可以有四个分支的树。
满四叉树
从左图我们可以很自然的联想到，一棵四叉树可以把一个正方形的二维空间无限细分。计算机在检测有没有马里奥有砖头有没有相碰时，实际上是检测砖头的区域，马里奥头部的数据有没有和砖头的数据相重叠，如果采取逐一对比的方法，那么这个过程就过于复杂，每一次检测碰撞都要和图像上所有的数据对比，效率太低。
而采用了四叉树的结构对一个图像进行划分以后，每一次对比都可以把一个图像划分为四个区域，每次都和四个大的部分做匹配。
这样就大大减少了电脑计算的次数。
四叉树划分平面空间
那么，八叉树（Octree）自然是三维空间划分的数据结构之一，它用来加速空间查询。八叉树是一个节点最多有八个分支的树，在游戏一般具有一下作用：
加速用于可见性判断的视锥裁剪（view frustum culling）。
加速射线投射（ray casting） ，如用作视线判断或枪击判定。
邻近查询（proximity query），如查询玩家角色某半径范围内的敌方NPC。
碰撞检测的粗略阶段（broad phase），找出潜在可能碰撞的物体对。
总括而言，前3个应用都是加速一些形状（frustum、ray、proximity shape如球体）的相交测试（intersection test）。
类似于四叉树对二维空间不断分割正方形的划分，八叉树的空间划分方式是，把一个立方体分割为八个小立法体，然后递归地分割小立方体。
八叉树对立体空间的划分
八叉树的数据结构
机器和人类逻辑的差别——AI没有想象力
所以，AI眼中的视觉世界就是很多纵横交错的树，和人类有着本质的差别。
在机器的眼里，对一个事物并没有具体的概念，只是一堆数据的集合。
所以计算机视觉领域的李飞飞教授在2017年未来论坛年会上说，“人类社会目前还处于‘失明’的状态！ ”
虽然目前每一分钟都有无数的图像和视频的产生和储存，但是记录这一切的计算机并不知道这些代表什么。
人眼从任何角度观察一棵树，都能够判断这是不是一棵树，机器却不可以，机器只能够通过“树=树叶+树干”这种类似的算法来判断它看见的树是不是一棵树。
简而言之，就是AI没有联想和想象力。
今天内容到此，我是小日
……
VRLAND：中国首个VR娱乐自媒体
小日的店：服务高智商人群的潮店
允许我，用未来的语境和你说话
“VR，就是这世界所有的一切”
“唯有宇宙和人类的愚蠢是永恒的”
#我身在 当时你 幻想的 未来里#
商务合作、创投活动、行业报道、新人加入
请发联系邮箱：594567450@QQ.COM
点“阅读原文”，进入我们的科技商店