這篇文章主要介紹了C++實(shí)現(xiàn)四叉樹(shù)效果的方法，具有一定借鑒價(jià)值，感興趣的朋友可以參考下，希望大家閱讀完這篇文章之后大有收獲，下面讓小編帶著大家一起了解一下。

創(chuàng)新互聯(lián)建站服務(wù)項(xiàng)目包括噶爾網(wǎng)站建設(shè)、噶爾網(wǎng)站制作、噶爾網(wǎng)頁(yè)制作以及噶爾網(wǎng)絡(luò)營(yíng)銷策劃等。多年來(lái)，我們專注于互聯(lián)網(wǎng)行業(yè)，利用自身積累的技術(shù)優(yōu)勢(shì)、行業(yè)經(jīng)驗(yàn)、深度合作伙伴關(guān)系等，向廣大中小型企業(yè)、政府機(jī)構(gòu)等提供互聯(lián)網(wǎng)行業(yè)的解決方案，噶爾網(wǎng)站推廣取得了明顯的社會(huì)效益與經(jīng)濟(jì)效益。目前，我們服務(wù)的客戶以成都為中心已經(jīng)輻射到噶爾省份的部分城市，未來(lái)相信會(huì)繼續(xù)擴(kuò)大服務(wù)區(qū)域并繼續(xù)獲得客戶的支持與信任！

什么是四叉樹(shù)？

如圖，設(shè)想，

紅框表示地圖，星星表示單位，黃框表現(xiàn)范圍，

要處理地圖中范圍內(nèi)的單位，最直接的做法是篩選所有單位。

通過(guò)上圖可以看到一個(gè)顯而易見(jiàn)的問(wèn)題，大部分單位都不需要被處理。

如果把地圖分成塊，只篩選范圍覆蓋的塊中的單位，這樣就可以減少很多不必要的篩選。

四叉樹(shù)可以有效解決這個(gè)問(wèn)題。

樹(shù)的每一層都把地圖劃分四塊，根據(jù)地圖尺寸來(lái)決定樹(shù)的層數(shù)，層數(shù)越大劃分越細(xì)。

當(dāng)需要對(duì)某一范圍的單位篩選時(shí)，只需要定位到與范圍相交的樹(shù)區(qū)域，再對(duì)其區(qū)域內(nèi)的對(duì)象篩選即可。

四叉樹(shù)的實(shí)現(xiàn)

#pragma once
#include "base.h"
#include "math.h"
template 
class Tree4 {
private:
 struct Pointer {
 Tree4 *LT, *RT, *LB, *RB;
 Pointer() :LT(nullptr), RT(nullptr), LB(nullptr), RB(nullptr)
 { }
 ~Pointer()
 {
  SAFE_DELETE(LT);
  SAFE_DELETE(RT);
  SAFE_DELETE(LB);
  SAFE_DELETE(RB);
 }
 };
public:
 Tree4(const MATH Rect &rect, size_t n = 0): _rect(rect)
 {
 STD queue queue;
 queue.push(this);
 for (auto c = 1; n != 0; --n, c *= 4)
 {
  for (auto i = 0; i != c; ++i)
  {
  auto tree = queue.front();
  tree->Root();
  queue.pop();
  queue.push(tree->_pointer.LT);
  queue.push(tree->_pointer.RT);
  queue.push(tree->_pointer.LB);
  queue.push(tree->_pointer.RB);
  }
 }
 }
 template 
 bool Insert(const Value * value, const Range & range)
 {
 auto tree = Contain(range);
 auto ret = nullptr != tree;
 if (ret) { tree->_values.emplace_back(value); }
 return ret;
 }
 template 
 bool Remove(const Value * value, const Range & range)
 {
 auto tree = Contain(range);
 auto ret = nullptr != tree;
 if (ret) { ret = tree->Remove(value); }
 return ret;
 }
 template 
 bool Match(const Range & range, const STD function & func)
 {
 if (!MATH intersect(_rect, range))
 {
  return true;
 }
 for (auto & value : _values)
 {
  if (!func(const_cast(value)))
  {
  return false;
  }
 }
 auto ret = true;
 if (!IsLeaf())
 {
  if (ret) ret = _pointer.LT->Match(range, func);
  if (ret) ret = _pointer.RT->Match(range, func);
  if (ret) ret = _pointer.LB->Match(range, func);
  if (ret) ret = _pointer.RB->Match(range, func);
 }
 return ret;
 }
 template 
 Tree4 * Contain(const Range & range)
 {
 Tree4 * ret = nullptr;
 if (MATH contain(STD cref(_rect), range))
 {
  if (!IsLeaf())
  {
  if (nullptr == ret) ret = _pointer.LT->Contain(range);
  if (nullptr == ret) ret = _pointer.RT->Contain(range);
  if (nullptr == ret) ret = _pointer.LB->Contain(range);
  if (nullptr == ret) ret = _pointer.RB->Contain(range);
  }
  if (nullptr == ret)
  ret = this;
 }
 return ret;
 }
private:
 void Root()
 {
 _pointer.LT = new Tree4(MATH Rect(_rect.x, _rect.y, _rect.w * 0.5f, _rect.h * 0.5f));
 _pointer.LB = new Tree4(MATH Rect(_rect.x, _rect.y + _rect.h * 0.5f, _rect.w * 0.5f, _rect.h * 0.5f));
 _pointer.RT = new Tree4(MATH Rect(_rect.x + _rect.w * 0.5f, _rect.y, _rect.w * 0.5f, _rect.h * 0.5f));
 _pointer.RB = new Tree4(MATH Rect(_rect.x + _rect.w * 0.5f, _rect.y + _rect.h * 0.5f, _rect.w * 0.5f, _rect.h * 0.5f));
 }
 bool Remove(const Value * value)
 {
 auto iter = STD find(_values.begin(), _values.end(), value);
 auto ret = _values.end() != iter;
 if (ret) { _values.erase(iter); }
 return ret;
 }
 bool IsLeaf()
 {
 return nullptr == _pointer.LT
  || nullptr == _pointer.RT
  || nullptr == _pointer.LB
  || nullptr == _pointer.RB;
 }
 Tree4(const Tree4 &) = delete;
 Tree4(Tree4 &&) = delete;
 Tree4 &operator=(const Tree4 &) = delete;
 Tree4 &operator=(Tree4 &&) = delete;
private:
 MATH Rect _rect;
 Pointer _pointer;
 STD list _values;
};

代碼簡(jiǎn)潔，通俗易懂，承讓。

效果圖

左側(cè)全圖遍歷，右側(cè)四叉樹(shù)遍歷，通過(guò)左上角的開(kāi)銷時(shí)間，差異很明顯。

感謝你能夠認(rèn)真閱讀完這篇文章，希望小編分享的“C++實(shí)現(xiàn)四叉樹(shù)效果的方法”這篇文章對(duì)大家有幫助，同時(shí)也希望大家多多支持創(chuàng)新互聯(lián)建站，關(guān)注創(chuàng)新互聯(lián)網(wǎng)站建設(shè)公司行業(yè)資訊頻道，更多相關(guān)知識(shí)等著你來(lái)學(xué)習(xí)!

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)建站www.cdcxhl.com，海內(nèi)外云服務(wù)器15元起步，三天無(wú)理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國(guó)服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場(chǎng)景需求。

分享文章：C++實(shí)現(xiàn)四叉樹(shù)效果的方法-創(chuàng)新互聯(lián)
轉(zhuǎn)載來(lái)源：http://weahome.cn/article/dcsogs.html