概述
四叉樹（quad-tree）是一種數據結構，是一種每個節點最多有四個子樹的數據結構。
四叉樹是在二維圖片中定位像素的唯一適合的算法。因為二維空間（圖經常被描述的方式）中，平面像素可以重複的被分為四部分，樹的深度由圖片、計算機記憶體和圖形的複雜度決定。
四叉樹可以用來在資料庫中放置和定位檔案（稱作記錄或鍵）。這一算法通過不停的把要查找的記錄分成4部分來進行匹配查找直到僅剩下一條記錄為止。
特點
•可分解成為各自的區塊
•每個區塊都有節點容量。當節點達到最大容量時，節點分裂
•樹狀數據結構依造四元樹法加以區分
形態
四元樹可以用他們數據形態的表示法來作分類，數據形態的項目有：區域、點、直線及曲線。四元樹也可以進行分類，不管樹的形態是否獨立於已處理過的排秩數據。一些四元樹的形態如下所示 ：
四元樹區塊
四元樹區塊表示為空間的分區，即在二維上分區塊為四組相同的象限、次象限等，且每個葉節點包含有關特殊次區塊的數據。樹里的每個節點不是正好有4個子節點，就是沒有子節點(為一個樹葉節點)。四元樹區塊不是嚴格的一顆'樹' - 且位置的次分區與數據無關。他們是比較精確一些稱為'單詞查找樹'.
在一個深度為n的四元樹區塊中可以用來表示一個視頻包含有2× 2的像素，每個像素的值為0或1。根節點表示全部視頻區塊。假如像素在任何區塊不是全部為0或1，那就可以進行畫分。在這個套用中，每個葉節點代表一個段落的像素、段落像素裡面包含全部為零或全部為一的組合。
四元樹區塊也可以用為一種數據區塊上不同變化解析的表達法。比如，溫度在一個區塊中可以存儲為一個四元樹，而樹葉節點存儲著平均溫度涵蓋到它所擁有的次區塊。
假如四元樹區塊被用來表達一組點數據(諸如一組城市的經緯度)，區塊就進行次分區直到每個葉節點包含最多一個單點。
點四元樹
點四元樹修改自二叉樹用來表示二維的點數據。點四元樹與四元樹都有共同的特點，不過於次分區的中心總是在一點時、點四元樹視為一真樹(true tree)。樹的形態根據編過序的數據而定。在比較二維規律數據點上是相當有效率的，經常運作在O(log n)的時間複雜度內。
點四元樹的節點結構
點四元樹的節點類似於二叉樹的節點，它們之間的主要差別在於點四元樹有4個指針(每一個象限一個指針)、而一般二叉樹只有2個指針(左指針及右指針)。點四元樹的鍵值也是經常被分解為兩部分，如在直角坐標上的 x 及 y 值。因此，一個節點包含下列信息：
•4個指針(Pointer)：quad[‘NW’](西北)、quad[‘NE’](東北)、quad[‘SW’](西南)、及quad[‘SE’](東南)。
•點；含有如下項目：
•鍵值；通常以直角作標(x, y)值來表示。
•值；比如是"名字"。
邊四元樹
邊四元樹是專門用來存儲直線而不是點。曲線能分區每格到很接近精細的解析度。如此能產生極度的不平衡樹，而此不平衡樹可能推翻索引的使用目的。
種類
1.點四叉樹（Point Quadtree）
點四叉樹與KD樹相似，兩者的差別是在點四叉樹中，空間被分割成四個矩形。四個不同的多邊形分別是：SW、NW、SE、NE。其搜尋過程和KD樹相似，當一個點包含在搜尋範圍內時被記錄下來，當一個子樹和搜尋範圍有交疊時它將被穿過。
2.PR四叉樹(Point Region Quadtree)
PR四叉樹是點四叉樹的一個變種，它不使用數據集中的點來分割空間。在PR四叉樹中，每次分割空間時，都是將一個正方形分成四個相等的子正方形，依次進行，直到每個正方形的內容不超過所給定的桶量（比如一個對象）為止。
3.MX四叉樹
空間被分割成四個矩形。四個不同的多邊形分別是：SW、NW、SE、NE。每次分割空間時，都是將一個正方形分成四個相等的子正方形，依次進行，直到每個正方形的內容不超過所給定的桶量（比如一個對象）為止。
所有的數據都處在四叉樹的同一個深度，多個點可以由一個指針聯接。
4.基於固定格線劃分的四叉樹索引
在四叉樹中，空間要素標識記錄在其外包絡矩形所覆蓋的每一個葉結點中，但是，當同一父親的四個兄弟結點都要記錄該空間要素標識時，則只將該空間要素標識記錄在該父親結點上，並按這一規則向上層推進。
5.線性可排序四叉樹索引
首先將四叉樹分解為二叉樹，即在父結點層與子結點層之間插入一層虛結點，虛結點不用來記錄空間要素，然後按照中序遍歷樹的順序對結點進行編碼，包括加入的虛結點 。
套用
•圖像表示法
•空間索引(Spatial index)。
•在二維的有效率之碰撞偵測(collision detection)。
•地形數據的隱藏面決定(Hidden surface determination)。
•存儲分散數據，諸如電子表格(spreadsheet)、或著一些矩陣計算的格式化信息。
•多維場的解法。(計算流體力學,電磁學)
•生命遊戲模擬程式 。
