從祖先矩陣創建二叉樹

Question

問題是如何創建一個二叉樹，因爲它的祖先矩陣。我在http://www.ritambhara.in/build-binary-tree-from-ancestor-matrics/找到了一個很酷的解決方案。問題在於它涉及從矩陣中刪除行和列。現在我該怎麼做？有人可以爲此提出一個僞代碼嗎？或者，有沒有更好的算法可能？

Answer 1

您不必實際刪除行和列。你可以將它們標記爲在一些額外的數組中被刪除，或者你可以使它們全部爲零，我認爲它們實際上是相同的（實際上，你仍然需要知道它們被移除，所以你不選擇它們再次在步驟4.c - 所以，將節點標記爲已刪除應該足夠好）。

這裏是從頁面對僞代碼的修改：

4.b.

used[temp] = true; 
for (i = 0 to N) 
    Sum[i] -= matrix[i][temp]; (aka decrement sum if temp is a predecessor of i) 
    matrix[i][temp] = 0; 

4.c.查找Sum [i] == 0並使用[i] == false的所有行。

Answer 2

這讓我想起使用Doanld克努特實施Dancing Links他Algorithm X
它基本上是循環雙向鏈表的結構。 您可以保持單獨的 總和數組並根據需要刪除行和列進行更新。

其實你不需要單獨維護一個總和數組。
編輯：

我的意思是 -
你可以使用由圓形的二維鏈表的結構。 節點結構會有點像：

struct node{ 
     int val; 
     struct node *left; 
     struct node *right; 
     struct node *down; 
}; 

的最頂層和最左邊的列表是頂點（二叉樹節點值）的標題列表。

如果頂點j是頂點i的祖先，建立一個（空）新節點，使得j列的電流down分配了此新的節點和i's電流left分配了此新節點。
注：結構可以通過掃描祖先矩陣的每一行從左向右和插入行從0到N被容易地構建（假設N是沒有頂點在這裏）

我借用了Image1和Image2的這些圖片來給出一個網格的概念。儘管第二張圖片丟失了最左邊的標題。

如果N是否定的。頂點。祖先矩陣中的條目（如果樹歪斜）或平均O(NlogN)條目可能更差。

要搜索當前根：O(N)
假設虛節點，開始時，線性掃描最左邊的標頭，並選擇一個節點與node->down->right == node->down。

要刪除這個頂點的信息：O(N)
刪除行：O(1)

node->down = node->down->down; 

刪除列：O(N)
轉到相應的列 - 說（P）：

node* q = p; 
while(q->down != p){ 
    q->down->left->right = q->down->right; 
    q->down->right->left = q->down->left; 
    q = q->down; 
} 

發現當前Root後，您可以將其分配給其父節點，並將它們插入隊列以按照該鏈接處理的下一級別進行處理。

總體時間複雜度：N +（N-1）+（N-2）+ .... = O(N^2)。
最壞情況空間複雜度O(N^2)

雖然有來自你已經有解決方案的漸近運行時沒有大的起色。我認爲這是值得一提的，因爲這種結構對於存儲稀疏矩陣和定義諸如乘法的操作特別有用，或者如果您正在使用一些回溯算法，它們刪除行/列和後來的回溯並像Knuth's那樣再次添加它AlgorithmX。

Answer 3

您不必更新矩陣。只要減去當前節點的任何後代的sum數組中的值，並檢查它們中的任何一個是否達到零，這意味着當前noe是最後一個祖先，例如，直接父：

for (i = 0 to N) 
    if matrix[i][temp]==1: 
     Sum[i]=Sum[i]-1 
     if Sum[i]==0: 
     add i as child of temp 
     add i to queue