有沒有三維的數據結構？

01-30

比如數組、鏈表是一維，樹是二維，有沒有三維的數據結構，如果有是怎樣的？
補充一下，和一樓的討論讓我對自己的想法更清楚了一點，這裡的維度以"能表示這種數據結構的空間維度下限"來表示，比如線條，它可以存在於1～無窮維中，那認為它是1維的，樹在2～無窮維中，認為它是2維的。

我覺得這個問題下面的答案都跑偏了，

事實上單連通鏈本來就是樹的一種，而數組和單鏈表只是單連通鏈的儲存方式而已。所以根本就不存在什麼一維二維，空間維度是幾何上的定義，和圖一毛錢關係沒有。

如果說數組和單鏈表是一維的，那麼哈希表是幾維的？

能表示這種數據結構的空間維度下限這本來就不是一個良好的定義，絕大多數數據結構都可以用圖來表示，那麼這個問題可以轉換成，能表示這種圖的空間維度下限，是不是覺得怪怪的，圖和空間維度有神馬關係？

如果一定要這樣來說，那麼所有不是平面圖 (圖論)的圖都是三維的，因為他們無法畫在平面上使得所有的邊互不交疊。而且，所有的圖都能在三維上畫出來使得所有的邊互不交疊。

至於樹怎麼變成一維的結構，很多答案看著捉急，，，，，內存本來就是個一維的空間怎麼就存不下樹呢？說白了任何一個圖都可以用一個二元關係來表示，，，，，，，

k-d tree

k維的~ k自選所以你要幾維有幾維哦

應該算是線段樹的擴展所以它的樣子是把k維空間一直分割每次分割出的兩個子空間還是一個k-d tree 於是接著分割... 我給的wiki鏈接里有個3維情況下的圖你可以參考下~

=============== update 2013/7/19 ===============

我似乎有點明白題主的意思了

比如我說的k-d tree, 即使它可以表示100-d, 它自身還是一個tree..

按照"能表示這種數據結構的空間維度下限"來定義的話,tree也是一維的

因為我可以用一個一維的array來表示任意graph... 只要規定按點序存放 array的元素代表某個點出發的邊的終點序號...以-1為結束

那麼 2 3 4 -1 2 3 3-1 -1 1 -1

就代表

這樣一張圖..如果這種表示法賴皮不算數的話。。那數據結構的嵌套可能是你想要的結果

例如樹可以認為是一維鏈表套一維鏈表

那樹套鏈表就是三維數據結構。樹套樹就可以是四維。。！

那麼，內存是幾維的？

有個東西叫做線段樹( Segment tree )，他是對一維線段進行劃分的一種二叉樹 ( Binary tree )。、

那麼將線段樹擴展一下，在一個矩形上不斷的四分象限，就可以得到一個叫做矩形樹( R-tree )的東西，這是一種四叉樹( Quadtree )。

然後再接再厲，將空間不斷的劃分為八個卦限，就得到了一個八叉樹( Octree )。在立體幾何和3D圖像處理中被頻繁使用的一種數據結構。

當然，你還可以順著這個思路將4維空間劃分，不過這個東西已經沒有辦法用幾何意義表述了（因為真實四維空間體在三維空間不能構划出來，三維空間生活的人也不可能感知四維空間的存在）。

以上。

==update==

看了問題補充我反而不能理解了。

為什麼說數組和鏈表是一維呢？因為都是線性的么？那二維數組和十字鏈表算什麼？

為什麼說樹是二維的呢？是因為在紙上可以要畫成一個圖才能表示么？那麼樹其實完全可以表示成鏈的（二叉樹的三種遍歷。n叉樹轉鏈…我忘了叫什麼了。）

那麼你的意思是說「需要畫成二維才能直觀的看得出來的數據結構」的話，O tree就是一個「三維數據結構」，甚至用鏈表記錄的一個分層圖也是一個「三維模型」。