数据结构——四叉树

这篇具有很好参考价值的文章主要介绍了数据结构——四叉树。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

四叉树(Quadtree)是一种用于表示和管理二维空间的树状数据结构。它将二维空间递归地分割成四个象限,每个象限可以继续分割,以实现对空间的更精细的划分。四叉树通常用于解决空间搜索和查询问题,例如碰撞检测、图像压缩、地理信息系统等领域。
四叉树,数据结构,数据结构,java,数据库
特别适合大规模的广阔室外场景管理。一般来说如果游戏场景是基于地形的(甚至没有高度)(如城市、平原、2D场景),那么适合用四叉树来管理。而如果游戏场景在高度轴上也有大量物体需要管理(如太空、高山),那么适合用八叉树来管理。文章来源地址https://www.toymoban.com/news/detail-731941.html

#include <iostream>

// 定义二维点的结构体
struct Point {
    float x;
    float y;
    Point(float _x, float _y) : x(_x), y(_y) {}
};

// 定义四叉树节点
struct QuadTreeNode {
    Point point;
    QuadTreeNode* topLeft;
    QuadTreeNode* topRight;
    QuadTreeNode* bottomLeft;
    QuadTreeNode* bottomRight;

    QuadTreeNode(Point _point) : point(_point), topLeft(nullptr), topRight(nullptr), bottomLeft(nullptr), bottomRight(nullptr) {}
};

class QuadTree {
private:
    QuadTreeNode* root;
    int maxDepth; // 最大深度

    // 在指定深度下递归插入节点
    QuadTreeNode* insert(QuadTreeNode* node, Point point, int depth) {
        if (node == nullptr) {
            return new QuadTreeNode(point);
        }

        // 根据点的位置选择象限
        if (point.x < node->point.x && point.y < node->point.y) {
            node->bottomLeft = insert(node->bottomLeft, point, depth + 1);
        } else if (point.x >= node->point.x && point.y < node->point.y) {
            node->bottomRight = insert(node->bottomRight, point, depth + 1);
        } else if (point.x < node->point.x && point.y >= node->point.y) {
            node->topLeft = insert(node->topLeft, point, depth + 1);
        } else {
            node->topRight = insert(node->topRight, point, depth + 1);
        }

        return node;
    }

    // 在指定深度下递归搜索节点
    bool search(QuadTreeNode* node, Point point, int depth) {
        if (node == nullptr) {
            return false;
        }

        if (node->point.x == point.x && node->point.y == point.y) {
            return true;
        }

        // 根据点的位置选择象限
        if (point.x < node->point.x && point.y < node->point.y) {
            return search(node->bottomLeft, point, depth + 1);
        } else if (point.x >= node->point.x && point.y < node->point.y) {
            return search(node->bottomRight, point, depth + 1);
        } else if (point.x < node->point.x && point.y >= node->point.y) {
            return search(node->topLeft, point, depth + 1);
        } else {
            return search(node->topRight, point, depth + 1);
        }
    }

public:
    QuadTree(float minX, float minY, float maxX, float maxY, int depth) : root(nullptr), maxDepth(depth) {}

    // 插入一个点
    void insert(Point point) {
        root = insert(root, point, 0);
    }

    // 搜索一个点是否存在
    bool search(Point point) {
        return search(root, point, 0);
    }
};

int main() {
    QuadTree quadtree(0.0f, 0.0f, 100.0f, 100.0f, 4); // 创建四叉树,定义边界和最大深度

    Point point1(10.0f, 20.0f);
    Point point2(80.0f, 90.0f);

    quadtree.insert(point1); // 插入点1
    quadtree.insert(point2); // 插入点2

    Point searchPoint(80.0f, 90.0f);
    bool found = quadtree.search(searchPoint); // 搜索点2
    if (found) {
        std::cout << "Point found in the quadtree." << std::endl;
    } else {
        std::cout << "Point not found in the quadtree." << std::endl;
    }

    return 0;
}

到了这里,关于数据结构——四叉树的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【java数据结构-二叉树(上)】

    🔥个人主页: 努力学编程’ 🔥内容管理: java数据结构 hello,今天带大家学习 数据结构 中非常重要的一个知识点 二叉树 ,二叉树主体的实现使用的是递归的知识,通过二叉树我们可以更好的理解递归的应用。今天就带大家学习一下二叉树的一些知识。 概念 : 树是一种非

    2024年04月08日
    浏览(42)
  • 数据结构(Java实现)-二叉树(上)

    树型结构 树是一种非线性的数据结构,它是由n(n=0)个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。 有一个特殊的结点,称为根结点,根结点没有前驱结点 除根结点外,其余结点被分成M(M 0)个互不

    2024年02月11日
    浏览(47)
  • 数据结构(Java实现)-二叉树(下)

    获取二叉树的高度 检测值为value的元素是否存在(前序遍历) 层序遍历 判断一棵树是不是完全二叉树 获取节点的路径 二叉树的最近公共祖先

    2024年02月10日
    浏览(44)
  • 【Java 数据结构】树和二叉树

    篮球哥温馨提示:编程的同时不要忘记锻炼哦! 目录 1、什么是树? 1.1 简单认识树  1.2 树的概念  1.3 树的表示形式 2、二叉树 2.1 二叉树的概念 2.2 特殊的二叉树 2.3 二叉树的性质 2.4 二叉树性质相关习题 3、实现二叉树的基本操作 3.1 了解二叉树的存储结构 3.2 简单构造一棵

    2024年01月16日
    浏览(45)
  • 数据结构之二叉树(Java)

    在这里先说明一下,结点和节点其实一样的,无须关注这个。 1. 概念:树是一种非线性的数据结构,它是由n个有限节点组成一个具有层次关系的集合。 如上图所示,把此种数据结构称作树是因为它看起来像一个倒挂的树。  2. 特点 有一个特殊的节点,称为根节点,它是唯一

    2024年02月07日
    浏览(39)
  • Java数据结构——二叉树的遍历

     作者:敲代码の流川枫 博客主页:流川枫的博客 专栏:和我一起学java 语录:Stay hungry stay foolish 工欲善其事必先利其器,给大家介绍一款超牛的斩获大厂offer利器——牛客网 点击注册和我一起刷题 文章目录 1.创建二叉树 2.二叉树的三种遍历方式 3.代码实现遍历 前序遍历

    2024年01月22日
    浏览(49)
  • 【数据结构】用Java实现一棵二叉树

    目录 前言 1. 创建MyBinaryTree类 2. 从前序与中序遍历序列构造二叉树 3. 从中序与后序遍历序列构造二叉树 4. 用层序遍历验证二叉树是否构建成功 5. 整体代码(构建二叉树、二叉树的基本功能和测试代码) 6. 测试结果 前面两篇文章已经给出了如何构建二叉树以及如何实现基本

    2024年02月11日
    浏览(45)
  • Java 【数据结构】 二叉树(Binary_Tree)【神装】

        登神长阶  第五神装 二叉树 Binary-Tree 目录  🎷一.树形结构 🪗1.概念 🎸2.具体应用 🎹 二.二叉树(Binary Tree) 🎺1.概念  🎻2.表现形式 🪕3.特殊类型 🥁3.1完全二叉树(Complete Binary Tree) 🪘3.2满二叉树(Full Binary Tree) 🔋4.性质  🪫5.二叉树的遍历 💿5.1前中后序遍历

    2024年04月27日
    浏览(45)
  • Java常见的数据结构:栈、队列、数组、链表、二叉树、二叉查找树、平衡二叉树、红黑树

    数据结构是计算机底层存储、组织数据的方式。是指数据相互之间是以什么方式排列在一起的。 通常情况下,精心选择的数据结构可以带来更高的运行或者存储效率 栈 队列 数组 链表 二叉树 二叉查找树 平衡二叉树 红黑树... 后进先出,先进后出 数据进入栈模型的过程称为

    2024年02月07日
    浏览(46)
  • 【Java数据结构】二叉树的前中后序遍历(递归和非递归)

    二叉树遍历是二叉树的一种重要操作 必须要掌握 二叉树的遍历可以用递归和非递归两种做法来实现 前序遍历的遍历方式是 先根节点 在左节点 在右节点 述这棵树前序遍历的结果是: A B D E C F G 递归的思想就是把问题拆分成一个个小问题来解决 treeNode是一个内部类 具体实现

    2023年04月26日
    浏览(52)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包