用八叉樹來表示三維形體，並研究在這種表示下的各種操作及應用是在進入80年代後才比較全面地開展起來的。這種方法，既可以看成是四叉樹方法在三維空間的推廣，也可以認為是用三維體素陣列表示形體方法的一種改進。
八叉樹的邏輯結構如下：
假設要表示的形體v可以放在乙個充分大的正方體c內，c的邊長為2 n，形體v c，它的八叉樹可以用以下的遞迴方法來定義：
八叉樹的每個節點與c的乙個子立方體對應，樹根與c本身相對應，如果v＝c，那麼v的八叉樹僅有樹根，如果v≠c，則將c等分為八個子立方體，每個子立方體與樹根的乙個子節點相對應。只要某個子立方體不是完全空白或完全為v所佔據，就要被八等分（圖2-5-1），從而對應的節點也就有了八個子節點。這樣的遞迴判斷、分割一直要進行到節點所對應的立方體或是完全空白，或是完全為v佔據，或是其大小已是預先定義的體素大小，並且對它與v之交作一定的「捨入」，使體素或認為是空白的，或認為是v佔據的。
如此所生成的八叉樹上的節點可分為三類：
灰節點，它對應的立方體部分地為v所佔據；
白節點，它所對應的立方體中無v的內容；
黑節點，它所對應的立方體全為v所佔據。
後兩類又稱為葉結點。形體v關於c的八叉樹的邏輯結構是這樣的：它是一顆樹，其上的節點要麼是葉節點，要麼就是有八個子節點的灰節點。
根節點與c相對應，其它節點與c的某個子立方體相對應。
因為八叉樹的結構與四叉樹的結構是如此的相似，所以八叉樹的存貯結構方式可以完全沿用四叉樹的有關方法。因而，根據不同的存貯方式，八叉樹也可以分別稱為常規的、線性的、一對八的八叉樹等等。
另外，由於這種方法充分利用了形體在空上的相關性，因此，一般來說，它所占用的存貯空間要比三維體素陣列的少。但是實際上它還是使用了相當多的存貯，這並不是八叉樹的主要優點。這一方法的主要優點在於可以非常方便地實現有廣泛用途的集合運算(例如可以求兩個物體的並、交、差等運算)，而這些恰是其它表示方法比較難以處理或者需要耗費許多計算資源的地方。
不僅如此，由於這種方法的有序性及分層性，因而對顯示精度和速度的平衡、隱線和隱面的消除等，帶來了很大的方便，特別有用。
八叉樹有三種不同的存貯結構，分別是規則方式、線性方式以及一對八方式。相應的八叉樹也分別稱為規則八叉樹、線性八叉樹以及一對八式八叉樹。不同的存貯結構的空間利用率及運算操作的方便性是不同的。
分析表明，一對八式八叉樹優點更多一些。
1、規則八叉樹
規則八叉樹的存貯結構用乙個有九個欄位的記錄來表示樹中的每個結點。其中乙個字段用來描述該結點的特性(在目前假定下，只要描述它是灰、白、黑三類結點中哪一類即可)，其餘的八個字段用來作為存放指向其八個子結點的指標。這是最普遍使用的表示樹形資料的存貯結構方式。
規則八叉樹缺陷較多，最大的問題是指標占用了大量的空間。假定每個指標要用兩個位元組表示，而結點的描述用乙個位元組，那麼存放指標要佔總的存貯量的94％。因此，這種方法雖然十分自然，容易掌握，但在存貯空間的使用率方面不很理想。
2、線性八叉樹
線性八叉樹注重考慮如何提高空間利用率。用某一預先確定的次序遍歷八叉樹(例如以深度第一的方式)，將八叉樹轉換成乙個線性表（圖2-5-2），表的每個元素與乙個結點相對應。對於結點的描述可以豐富一點，例如用適當的方式來說明它是否為葉結點，如果不是葉結點時還可用其八個子結點值的平均值作為非葉結點的值等等。
這樣，可以在記憶體中以緊湊的方式來表示線性表，可以不用指標或者僅用乙個指標表示即可。
線性八叉樹不僅節省存貯空間，對某些運算也較為方便。但是為此付出的代價是喪失了一定的靈活性。例如為了訪問屬於原圖形右下角的子圖形對應的結點，那麼必須先遍歷了其餘七個子圖形對應的所有結點後才能進行；不能方便地以其它遍歷方式對樹的結點進行訪問，導致了許多與此相關的運算效率變低。
因此儘管不少文章討論了這種八叉樹的應用，但是仍很難令人滿意。
3、一對八式的八叉樹
乙個非葉結點有八個子結點，為了確定起見，將它們分別標記為0，1，2，3，4，5，6，7。從上面的介紹可以看到，如果乙個記錄與乙個結點相對應，那麼在這個記錄中描述的是這個結點的八個子結點的特性值。而指標給出的則是該八個子結點所對應記錄的存放處，而且還隱含地假定了這些子結點記錄存放的次序。
也就是說，即使某個記錄是不必要的(例如，該結點已是葉結點)，那麼相應的存貯位置也必須空閒在那裡（圖2-5-3），以保證不會錯誤地訪問到其它同輩結點的記錄。這樣當然會有一定的浪費，除非它是完全的八叉樹，即所有的葉結點均在同一層次出現，而在該層次之上的所有層中的結點均為非葉結點。
為了克服這種缺陷，有兩條途徑可以採納。一是增加計算量，在記錄中增加一定的資訊，使計算工作適當減少或者更方便。
四叉樹編碼(quad-tree code)
四又樹結構的基本思想是將一幅柵格地圖或影象等分為四部分。逐塊檢查其格網屬性值(或灰度)。如果某個子區的所有格網值都具有相同的值。
則這個子區就不再繼續分割，否則還要把這個子區再分割成四個子區。這樣依次地分割，直到每個子塊都只含有相同的屬性值或灰度為止。
四叉樹編碼法有許多有趣的優點：①容易而有效地計算多邊形的數量特徵；②陣列各部分的解析度是可變的，邊界複雜部分四叉樹較高即分級多，解析度也高，而不需表示許多細節的部分則分級少，解析度低，因而既可精確表示圖形結構又可減少存貯量；②柵格到四叉樹及四叉樹到簡單柵格結構的轉換比其它壓縮方法容易；④多邊形中巢狀異類小多邊形的表示較方便。
四叉樹編碼的最大缺點是轉換的不定性，用同一形狀和大小的多邊形可能得出多種不同的四叉樹結構，故不利於形狀分析和模式識別。但因它允許多邊形中巢狀多邊形即所謂「洞」這種結構存在，使越來越多的地理資訊系統工作者都對四叉樹結構很感興趣。上述這些壓縮資料的方法應檢視形的複雜情況合理選用，同時應在系統中備有相應的程式。
另外，使用者的分析目的和分析方法也決定著壓縮方法的選取。
四叉樹結構按其編碼的方法不同又分為常規四叉樹和線性四叉樹。常規四叉樹除了記錄葉結點之外，還要記錄中間結點。結點之間借助指標聯絡，每個結點需要用六個量表達：
四個葉結點指標，乙個父結點指標和乙個結點的屬性或灰度值。這些指標不僅增加了資料貯存量，而且增加了操作的複雜性。常規四叉樹主要在資料索引和圖幅索引等方面應用。
線性四叉樹則只存貯最後葉結點的資訊。包括葉結點的位置、深度和本結點的屬性或灰度值。所謂深度是指處於四叉樹的第幾層上。由深度可推知子區的大小。
線性四叉樹葉結點的編號需要遵循一定的規則，這種編號稱為位址碼，它隱含了葉結點的位置和深度資訊。最常用的位址碼是**制或十進位制的morton碼。
八叉樹結構就是將空間區域不斷地分解為八個同樣大小的子區域(即將乙個六面的立方體再分解為八個相同大小的小立方體)，分解的次數越多，子區域就越小，一直到同—區域的屬性單一為止。按從下而上合併的方式來說，就是將研究區空間先按—定的解析度將三維空間劃分為三維柵格網，然後按規定的順序每次比較3個相鄰的柵格單元，如果其屬性值相同則合併，否則就記盤。依次遞迴運算，直到每個子區域均為單值為止。
八叉樹同樣可分為常規八叉樹和線性八叉樹。常規八叉樹的結點要記錄十個位，即八個指向子結點的指標，—個指向父結點的指標和乙個屬性值(或標識號)。而線性八叉樹則只需要記錄葉結點的位址碼和屬性值。
因此，它的主要優點是，其一節省儲存空間，因為只需對葉結點編碼，節省了大量中間結點的儲存。每個結點的指標也免除了，而從根到某一特定結點的方向和路徑的資訊隱含在定位碼之中，定位碼數字的個位數顯示解析度的高低或分解程度；其次，線性八叉樹可直接定址，通過其座標值則能計算出任何輸入結點的定位碼(稱編碼)，而不必實際建立八叉樹，並且定位碼本身就是座標的另—種形式，不必有意去儲存座標值。若需要的話還能從定位碼中獲取其座標值(稱解碼)；其三，在操作方面，所產生的定位碼容易儲存和執行，容易實現象集合、相加等組合操作。
八叉樹主要用來解決地理資訊系統中的三維問題。
#include ""
#include <>
#include <>
#include <>
#include <>
#include <>
#include ""
vec3 makevec3( double x, double y, double z)
vec3 copyvec3( vec3 src )
octree* make_octree( vec3 min, vec3 max )
void subpoint( octree* o,int oc,vec3 min, vec3 max)
資料結構練習二叉樹
學號 31301374 姓名張一博班級軟體工程1301 一 選擇題 1 按照二叉樹定義，具有3個結點的二叉樹共有 c 種形態。a 3 b 4 c 5d 6 2 具有五層結點的完全二叉樹至少有 d 個結點。a 9 b 15 c 31 d 16 3 以下有關二叉樹的說法正確的是 b a 二叉樹的度為2b...
資料結構試驗 二叉樹
實驗報告名稱 姓名學號專業班級 日期實驗6 二叉樹的建立及遍歷 一 實驗目的 1 學會實現二叉樹結點結構和對二叉樹的基本操作。2 掌握對二叉樹每種操作的具體實現，學會利用遞迴方法編寫對二叉樹這種遞迴資料結構進行處理的演算法。二 實驗要求 1 認真閱讀和掌握和本實驗相關的教材內容。2 編寫完整程式完成...
資料結構二叉樹基本演算法
資料結構實驗報告 實驗四二叉樹儲存結構的應用 實驗內容 二叉樹各種演算法的實現 專業班級 網路工程專業 1002班 組長 賈鑫 2010100234 組員 賈鵬飛 2010100237 鄧桐桐 2010100229 2012年 4月 27日 實驗報告 實驗型別 綜合實驗室 軟體實驗室二一 實驗名稱 ...