缘起 《你被追尾了》中预告了加速碰撞检测的算法——四叉树（for 2D），所以本文就来学习一下....什么是四叉树（Quadtree） 四叉树是一种将一块2D矩形区域（理解为游戏沙盒）分割为更易于管理的子区域的数据结构. 四叉树是二叉树的扩展——将2个子节点变为4个子节点....四叉树的根节点是初始的尚未被划分的一整块2D区域. 在下面所有的图中， 红色的小方块代表物体（例如赛车）. ? 然后，我们将一个物体放入初始的2D区域（即四叉树的根节点） ?...显然，这个数字的大小代表四叉树算法的惰性. 该节点将最终分裂为4（因为是四叉树嘛~）个子节点（子节点记做SR，sub region）. 然后每个物体都将根据它们所处的坐标被划分进某个SR....正如你所见，A、B、C、D 四个物体处在不同的象限，所以绝逼不可能发生碰撞. 这就不需要对这四个物体之间进行昂贵的碰撞检测，从而优化了游戏的性能. 知道了四叉树的思想之后，我们不难给出如下实现.
思路与算法 我们可以使用递归的方法构建出四叉树。 具体地，我们用递归函数 处理给定的矩阵 从 行开始到 行，从 和 列的部分。...我们首先判定这一部分是否均为 或 ，如果是，那么这一部分对应的是一个叶节点，我们构造出对应的叶节点并结束递归；如果不是，那么这一部分对应的是一个非叶节点，我们需要将其分成四个部分：行的分界线为 ，列的分界线为...，根据这两条分界线递归地调用 dfs\text{dfs}dfs 函数得到四个部分对应的树，再将它们对应地挂在非叶节点的四个子节点上。...记 为边长为 的数组需要的时间复杂度，那么「判定这一部分是否均为 或 」需要的时间为 ，在这之后会递归调用 规模为 的子问题，那么有： 以及： 根据主定理，可以得到 。...但如果判定需要的时间达到了渐近紧界 ，那么说明这一部分包含的元素大部分都是相同的，也就是说，有很大概率在深入递归时遇到元素完全相同的一部分，从而提前结束递归。
四叉树 介绍 四元树又称四叉树是一种树状数据结构，在每一个节点上会有四个子区块。四元树常应用于二维空间数据的分析与分类。它将数据区分成为四个象限。...今天要介绍的四叉树可以认为是二叉查找树的高维变体，它适合对有二维属性的数据进行存储和查询，当然四叉树存储的也不一定是二维数据，而是有着二维属性的数据，如有着 x,y 信息的点，用它还可以用来存储线和面数据...分类 四叉树常见的应用有图像处理、空间数据索引、2D中的快速碰撞检测、稀疏数据等，今天我们很纯粹地只介绍它在空间索引方面的应用。...根据其存储内容，四叉树可以分为点四叉树、边四叉树和块四叉树，今天我们实现的是点四叉树。 根据其结构，四叉树分为满四叉树和非满四叉树。...满四叉树在确定好深度后，进行插入操作很快，可是如果用它来存储下图所示数据，我们会发现，四叉树的好多叉都是空的，当然它们会造成内存空间的大量浪费。 ?
四叉树数据结构中，每个内部节点只有四个子节点。此外，每个节点都有两个属性： val：储存叶子结点所代表的区域的值。...四叉树格式： 输出为使用层序遍历后四叉树的序列化形式，其中 null 表示路径终止符，其下面不存在节点。 它与二叉树的序列化非常相似。唯一的区别是节点以列表形式表示 [isLeaf, val] 。...由四叉树所表示的二进制矩阵也已经给出。 如果我们对这两个矩阵进行按位逻辑或运算，则可以得到下面的二进制矩阵，由一个作为结果的四叉树表示。...注意，我们展示的二进制矩阵仅仅是为了更好地说明题意，你无需构造二进制矩阵来获得结果四叉树。...然后求，两棵树各自形成的小格子做逻辑或运算，最终将结果保存到同样的四叉树中并返回。 这个逻辑或运算是当前两棵树相同位置的值的或运算。 题目讲解完毕，那就是怎么来计算了。
输入图像被分成四个象限。根据输入图像中的颜色为每个象限分配一个平均颜色。误差最大的象限被分成四个子象限以细化图像。这个过程重复N次。
昨天的文章讲述了二叉树的先序、中序和后序的遍历方法（递归和非递归）,但是这种遍历方法有什么意义么？...今天来讲讲这些算法可以用来做什么，只要稍加更改，我们就可以得到另外一个功能，只需要仅仅几行代码的修改！ 还记得上篇文章二叉树的分类么？今天我们要来说三种树的分类：完全二叉树、平衡二叉树和搜索二叉树！...平衡二叉树：每个节点的左子树和右子树的高度不能超过1，也就是小于等于1 搜索二叉树：按照中序遍历必定会得到一个有序的数组，也就是当前节点的值要大于左孩子的值，小于右孩子的值。...我们以下面的二叉树为例，其均符合以上的三个类别！ ?...判断二叉树的类别 是否为平衡二叉树 这里面就存在一个套路，因为判断是否为平衡二叉树的规则对于每个节点都是一致的，也就是说当前节点左子树的高度和其右子树的高度高度差不能超过1，这就很显然可以使用一个递归函数来对每个节点进行遍历
题目 四叉树是一种树数据，其中每个结点恰好有四个子结点：topLeft、topRight、bottomLeft 和 bottomRight。...四叉树通常被用来划分一个二维空间，递归地将其细分为四个象限或区域。 我们希望在四叉树中存储 True/False 信息。四叉树用来表示 N * N 的布尔网格。...例如，下面是两个四叉树 A 和 B： A: +-------+-------+ T: true | | | F: false | T | T | |...，该函数根据两个四叉树返回表示这两个四叉树的逻辑或(或并)的四叉树。...建立四叉树（递归） /* // Definition for a QuadTree node. class Node { public: bool val; bool isLeaf;
题目 我们想要使用一棵四叉树来储存一个 N x N 的布尔值网络。网络中每一格的值只会是真或假。树的根结点代表整个网络。对于每个结点, 它将被分等成四个孩子结点直到这个区域内的值都是相同的....val 变量储存叶子结点所代表的区域的值。 你的任务是使用一个四叉树表示给定的网络。下面的例子将有助于你理解这个问题： 给定下面这个8 x 8 网络，我们将这样建立一个对应的四叉树： ?...由上文的定义，它能被这样分割： ? 对应的四叉树应该像下面这样，每个结点由一对 (isLeaf, val) 所代表. 对于非叶子结点，val 可以是任意的，所以使用 * 代替。 ?...提示： N 将小于 1000 且确保是 2 的整次幂。
相同的树 给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。 如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。...另一棵树的子树 给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。...二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。...对称二叉树 给你一个二叉树的根节点 root ， 检查它是否轴对称。 /** * Definition for a binary tree node....if(root==NULL) { return false; } return _isSymmetric(root->left,root->right); } 因为对称二叉树主要看的是根的左子树与右子树之间的差别
让我们一起来探讨js数据结构中的树。这里的树类比现实生活中的树，有树干，树枝，在程序中树是一种数据结构，对于存储需要快速查找的数据非有用，它是一种分层数据的抽象模型。...二叉树和二叉搜索树介绍： 二叉树中的节点最多只能有2个子节点，一个是左侧子节点，一个是右侧子节点，这样定义的好处是有利于我们写出更高效的插入，查找，删除节点的算法。...二叉搜索树是二叉树的一种，但是它只允许你在左侧子节点存储比父节点小的值，但在右侧节点存储比父节点大的值。接下来我们将按照这个思路去实现一个二叉搜索树。 ? 1....(520); tree.insert(521); 插入的结构会按照二叉搜索树的规则去插入，结构类似于上文的第一个树图。...至此，一个二叉搜索树已经实现，但是还存在一个问题，如果树的一遍非常深，将会存在一定的性能问题，为了解决这个问题，我们可以利用AVL树，一种自平衡二叉树，也就是说任何一个节点的左右两侧子树的高度之差最多为
前言 上一篇文章我们学习了搜索二叉树的实现，这篇文章我们来对搜索二叉树进行一个性能分析，并来讲解一下它的应用。 1....二叉搜索树的性能分析 插入和删除操作都必须先查找，所以查找效率就代表了二叉搜索树中各个操作的性能 那大家思考一下，搜索二叉树的查找的时间复杂度是多少？...那这个其实在不同情况下是不一样的： 如果二叉搜索树处于比较平衡的情况（接近完全二叉树），比如这样的 这种情况最坏的查找无非也就查找高度次（那如果结点数量为N，它的高度通常保持在logN的水平）...所以，二叉搜索树的查找的时间复杂度 最优情况下，二叉搜索树趋于平衡，其平均比较次数为： log_2 N ，时间复杂度为O(logN) 最差情况下，二叉搜索树退化为单支树(或者类似单支)，其平均比较次数为...二叉搜索树的应用 2.1 K模型 搜索二叉树的第一个应用是K模型，什么是K模型呢，介绍一下： 其实呢就是一个在不在的问题。
影响时间复杂度的因素即为二叉树的高，为了尽量避免树中每层上只有一个节点的情况，这里引入平衡二叉树。...定义 平衡二叉树也叫自平衡二叉搜索树（Self-Balancing Binary Search Tree），所以其本质也是一颗二叉搜索树，不过为了限制左右子树的高度差，避免出现倾斜树等偏向于线性结构演化的情况...，所以对二叉搜索树中每个节点的左右子树作了限制，左右子树的高度差称之为平衡因子，树中每个节点的平衡因子绝对值不大于 ，此时二叉搜索树称之为平衡二叉树。...情景分析 在执行插入或删除节点操作后，平衡因子绝对值变为大于 的情况，即左右子树的高度差为 或 的情况，可以归纳为如下四种： 左左情况(LL) 情况是指根节点的平衡因子为 ，根节点的左子节点平衡因子为...以 表示高度为 的平衡二叉树的最少节点个数，若二叉树不是空树则有： 根据推导公式可知，平衡二叉树的高度最大为 。当二叉树向完全二叉树靠拢，尽量填满每层上的节点时，树的高度最小，为 。
今天和大家聊的问题叫做 建立四叉树，我们先来看题面： https://leetcode-cn.com/problems/construct-quad-tree/ 示例 解题 https://blog.csdn.net.../zrh_CSDN/article/details/84140253 解题思路： 我们想要使用一棵四叉树来储存一个 N x N 的布尔值网络。...val 变量储存叶子结点所代表的区域的值。 你的任务是使用一个四叉树表示给定的网络。...下面的例子将有助于你理解这个问题： 给定下面这个8 x 8 网络，我们将这样建立一个对应的四叉树： 由上文的定义，它能被这样分割： 对应的四叉树应该像下面这样，每个结点由一对 (isLeaf,...对于非叶子结点，val 可以是任意的，所以使用*代替。 提示： N 将小于 1000 且确保是 2 的整次幂。 如果你想了解更多关于四叉树的知识，你可以参考这个 wiki 页面。
但是我们现在先不讨论那么高深的数据结构，我们先从二叉树的遍历开始： 先来看一下二叉树长什么样子： ?...下面进入正题，二叉树的遍历： 一般来说，二叉树常用的遍历方式有：前序遍历、中序遍历、后序遍历、层序遍历 四种遍历方式，不同的遍历算法，其思想略有不同，我们来看一下这四种遍历方法主要的算法思想： 1、先序遍历二叉树顺序...上图中二叉树的层序遍历结果为：0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 下面给出这四种算法思想的伪代码： 前序遍历： preOrderParse(int n) { if...： /* * 二叉树的四种遍历方式，这里没有采用真实的指针去做， * 而是采用数组下标去模拟指针，是一种更加方便快速的方法 */ #include #include <queue...我们和上面的结果对比一下，完全符合，OK，关于二叉树的四种遍历算法就完成了，希望能帮到你。 如果博客中有什么不正确的地方，还请多多指点，如果觉得我写的不错，请点个赞支持我吧。 谢谢观看。。。
首先讲述二叉树算法，二叉树在IT领域应用是非常广泛的，它不仅在游戏开发中，在当前比较火的人工智能上也得到了广泛的应用。...作为使用者，首先要清楚二叉树的特性：它是n(n≥0)个结点的有限集；它的孩子节点做多是2个；它的遍历有先序，中序，后序；它的存储结构分为线性和链式存储等等；还有一种是最优二叉树也称为哈夫曼树，下面开始案例的分享...虽然我们看不到它们的代码实现，但是我们自己可以使用二叉树将其打包成图集，给读者展示利用二叉树实现的UI打成图集的效果图： 下面给读者展示核心代码，首先是创建二叉树，目的是将图片插入到二叉树的结点中，...二叉树另一种形式是－哈夫曼树，哈夫曼树定义：在权为wl，w2，…，wn的n个叶子所构成的所有二叉树中，带权路径长度最小(即代价最小)的二叉树称为最优二叉树或哈夫曼树。...在人工智能中，二叉树使用也是非常广泛的，不同的分支指令对应的是不同的动作等等，在遇到AI方面的问题时可以优先考虑二叉树算法。
前言 二叉树的遍历及应用主要是运用了递归、分治的思想。在这一篇文章，小编将介绍二叉树的前序遍历、中序遍历、后序遍历，求二叉树结点个数、叶节点个数、第K层结点个数、二叉树的深度。...构建二叉树 手搓二叉树的结构 小编简单构建一个二叉树的结构，方便后面的测试 构建的方式比较简单，在树的结构中有当前结点的数据、当前结点的左节点、右节点。除此之外，还需要开辟结点。...有了 前面数据结构的学习，小编认为手搓一个二叉树的结构相对来说简单一些 typedef int Tdatatype; typedef struct Tree { Tdatatype data; struct...left + 1 : right + 1; } 二叉树第K层结点个数 二叉树第k层的节点数=左子树的第k-1层的节点数+右子树第k-1层的节点数。...因为二叉树没有第0层，是从第一层开始的，所以k==1时，返回1。
题目 一道微软以前的面试题，题目大概是，用一张长条纸，将其中一面保持对向自己，将它向上对折一次，展开后会有一个凹的折痕，而对折一次时再向上对折一次，展开后有三条折痕，从上到下为凹凹凸，以此类推，求向上对折...n次展开后从上至下的凹凸顺序。...所以可以用二叉树结构来做这题，对折n次就生成一个高n的满二叉树，头节点为凹，每个左节点为凹，每个右节点为凸，然后来一遍中序遍历打印即可。...value; Node *left = NULL; Node *right = NULL; }; Node *getNode(string value); //根据对折次数返回一颗二叉树...，不需要特意生成二叉树，直接把按中序遍历改一下即可，代码如下： #include using namespace std; //（层数，对折次数也是最大层数，是否打印凹） void
在上一篇文章中一文弄懂二叉树的三种遍历方式，分别从递归和非递归的角度，讲解、分析以及实现了三种遍历方式，今天给大家分享另外一种二叉树的遍历方式**层次遍历**。...层次遍历 所谓层次遍历，顾名思义就是指从二叉树的第一层（根节点）开始，从上至下逐层遍历，在同一层中，则按照从左到右的顺序对节点逐个访问。...图一 二叉树 以上图【图一】中的二叉树为例： 第一层：A 第二层：B C 第三层：D E F G 那么其层次遍历的结果，就是：A B C D E F G 非递归实现 思路： 将根节点放入队列 判断队列是否为空...由于一开始时由于不知道二叉树的深度，不知道有多少层，所以无法实现申请好二维数组的大小，只有在遍历的过程中不断的增加。...我们将使用二叉树的层次遍历方式来求树的高度。代码如下： int Height(TreeNode *root) { if (!
C++实现四叉树（附完整源码） C++实现四叉树 #ifndef __QuardTree__ #define __QuardTree__ #include #include <iostream
题目 思路 代码 题目 输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。...例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。...思路 首先我们看上面的图片，首先数据保证了正确性，那么前序的第一个肯定是root节点，也就是1，那么我们需要在中序遍历中找到1的位置，左边就是这个root的左子树，右边就是root的右子树。...我们可以举个栗子：对根节点的左子树进行解析： 对右子树进行解析： 只需要不断递归即可，当边界左边大于右边的时候，则停止 代码 /** * Definition for binary tree
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
ICP备案
实时音视频
即时通信 IM
对象存储
