如何在内存中表示二叉树

Question

我有这样的结构，被描述为“二叉树”。让我们看看一张图：

这是在内存中表示这种最好的方法吗？只是为了澄清，不是一个简单的二叉树，因为节点N4既是N1的左子节点又是N2的右子节点，N7和N8发生了相同的共享，等等......我需要一个构建算法，它很容易避免复制这样的节点，但只是参考它们。

UPDATE 我们很多人不符合“二叉树deefinition”同意，但来自金融（expecially衍生产品定价）这个卡梅斯看看这里：http://http.developer.nvidia.com/GPUGems2/gpugems2_chapter45.html例如。所以我使用了“Domain acceted definition”。

Answer 1

您可以按级别生成结构级别。在每次迭代中，创建一个级别的节点，将它们放在一个数组中，并将之前的级别连接到它们。像这样（C＃）：

Node GenerateStructure(int levels) 
{ 
    Node root = null; 

    Node[] previous = null; 

    for (int level = 1; level <= levels; level++) 
    { 
     int count = level; 

     var current = new Node[count]; 

     for (int i = 0; i < count; i++) 
      current[i] = new Node(); 

     if (level == 1) 
      root = current[0]; 

     for (int i = 0; i < count - 1; i++) 
     { 
      previous[i].Left = current[i]; 
      previous[i].Right = current[i + 1]; 
     } 

     previous = current; 
    } 

    return root; 
} 

整个结构需要O（N^2）存储器，其中N为级的个数。这种方法需要两个阵列的O（N）附加内存。另一种方法是从左到右生成图形，但这也需要O（N）个额外的内存。

时间复杂度显然是O（N^2）。

Answer 2

不止一棵树，其中我会给出一个定义，如'N顶点和N-1边的连通图'，该结构看起来像帕斯卡（或意大利教导的塔尔塔利亚）triangle。因此，具有合适索引的阵列就足够了。

施工细节取决于您的数据输入：请给出一些更多的提示。