1

问题是如何在给定祖先矩阵的情况下创建二叉树。我在http://www.ritambhara.in/build-binary-tree-from-ancestor-matrics/找到了一个很酷的解决方案。问题是它涉及从矩阵中删除行和列。现在我该怎么做？有人可以为此建议一个伪代码吗？或者，有没有更好的算法？

4

3 回答 3

2

您不必实际删除行和列。您可以在某个附加数组中将它们标记为已删除，也可以将它们全部设为零，我认为这实际上是相同的（实际上，您仍然需要知道它们已被删除，因此您不要选择它们再次在步骤 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 和 used[i] == false 的所有行。

于 2012-10-17T08:31:14.157 回答
2

这让我想起了Doanld Knuth 用来实现他的算法 X的Dancing Links ， 它基本上是一个循环双向链表结构。您可以维护一个单独的Sum数组并根据需要删除行和列来更新它。

实际上，您不需要维护单独的Sum数组。
编辑：

我的意思是-
您可以使用由圆形二维链表组成的结构。节点结构有点像：

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


Top-most 和 Left-most List 是顶点（二叉树节点值）的标题列表。

如果 vertexj是 vertex 的祖先i，则构建一个（空）新节点，以便将j列的 currentdown分配给这个新节点，并将i'scurrentleft分配给这个新节点。
注意：结构可以通过从左到右扫描祖先矩阵的每一行并插入从0到N的行来轻松构建。（假设N这里的顶点数）

图片1

图4

我从Image1和Image2中借用了这些图像来了解网格。不过，第二张图片缺少最左侧的标题。

如果N不是。的顶点。祖先矩阵中可能有更糟糕O(N^2)的条目（如果树倾斜）或平均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 一样再次添加它算法 X。

于 2012-10-17T08:49:20.123 回答
0

您不必更新矩阵。只需为当前节点的任何后代递减 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
于 2015-06-03T08:46:45.857 回答