我正在使用詞彙樹，k-ary樹數據結構，其深度爲L，這是迭代運行分層結構k-means聚類的結果。這是一種不平衡的結構，因爲當羣集中分配的數據點數量小於羣集數量時，羣集過程可能會停止。如何在矩陣中存儲非平衡樹
我的問題是，我需要以矩陣格式存儲這棵樹。
我想過簡單地將其存儲在寬度優先的順序中，但是如果實際節點數量（例如n）與平衡樹中理論的節點數量之間的差異增加，則內存浪費可能太高，是：
n << (1-k^L)/(1-k)
是否有任何方式有效地存儲矩陣形式的不平衡樹，而不浪費內存或浪費較少的可能性？
看起來似乎很難不浪費任何空間。然而，如果葉子的空間總是被分配（在某些情況下是有用的），則只需要O（N log_k N）個空間或O（k N log_k N），其中N是樹中的元素。成本是訪問元素需要O（log_k N）。
確切的實現是相當可變的，因爲它取決於許多因素。這個想法是簡單地將平衡二叉樹的表示概括爲一個數組，將其作爲一個不平衡的n元樹作爲矩陣工作。這是通過讓矩陣單元充當節點來完成的。包含在節點中的信息可以位於具有數據結構的單個單元中，也可以分佈在接下來的幾個單元中。主要的是每個節點必須包含特定節點的信息以及它所擁有的任何子節點的位置信息。然後使用增量指針來追蹤兒童下一個空閒位置的位置。總體而言，它只是一個小於或等於r * c元素的數組，它已被分解爲r行和c列的矩陣。列表列表可能更有用，因爲行L將包含深度爲L的節點。否則，在那裏沒有多大用處。