从祖先矩阵创建二叉树

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