如何构建一个非递归的二叉树？

我有一个是这样的分层数据：如何构建一个非递归的二叉树？

+----------------------+-------+ 
| name     | depth | 
+----------------------+-------+ 
| ELECTRONICS   |  0 | 
| TELEVISIONS   |  1 | 
| TUBE     |  2 | 
| LCD     |  2 | 
| PLASMA    |  2 | 
| PORTABLE ELECTRONICS |  1 | 
| MP3 PLAYERS   |  2 | 
| FLASH    |  3 | 
| CD PLAYERS   |  2 | 
| 2 WAY RADIOS   |  2 | 
+----------------------+-------+

管，液晶和等离子的电视机孩子。 FLASH是MP3播放器的孩子。 MP3 PLAYERS，CD PLAYERS和2 WAY RADIOS是PORTABLE ELECTRONICS的子公司。你得到演习。

现在，我有一个结构节点，其中包含它的Id和它的孩子，等等，以构建一棵树。就像这样：

struct Node 
{ 
    int id; 
    list<Node*> children; 
}

每个项目由一个ID，这是该行号标识（电子= 0，电视机= 1，等等），那么，谁是的孩子很容易找出节点。

这是我正在尝试构建的树。正如你所看到的，这棵树不是二元的。所以应用递归似乎不是一个容易的想法。如我错了请纠正我。

那么我该怎么做呢？帮帮我！

来源

2012-01-30 Michael Eilers Smith

递归使您可以轻松探索多条路径。因此2个或更多分支使递归成为容易的选择。另一种方法（迭代）要求你手动跟踪你的进度（即做堆栈在递归版本中所做的工作）。但是对于这种情况，递归是不需要的。 – 2012-01-30 06:41:56

您应该使用指向节点的指针，否则您将在每个级别的树中复制数据。

我也建议你使用枚举而不是int id，它使代码更清晰一些。

有使用递归与非二进制树没问题，你只需要而不是调用left/right（或类似）在您的递归函数调用中的每个list<Node*>。

来源

2012-01-30 06:36:33

这很有道理。谢谢！ – 2012-01-30 06:42:48

使用Hash代替列表可能会更好，因为访问时间将是常量，而列表中的O（n）（按定义）。 – 2012-11-08 04:48:30

没有限制，该树应该是二进制的，以便递归地构建它。它既可以用递归方法也可以用非递归方法创建。

对我来说，我会以自顶向下的方式构建树，即在子节点之前创建父节点。我会以某种方式对输入数据进行排序，以使消费呈线性。要添加一个新节点，只需将深度作为参数，然后减小（从根开始下降）直到达到0，这就是节点应该在的位置。当然，该节点的父路径信息是必需的。

来源

2012-01-30 06:33:19 LeleDumbo

我不明白这是如何工作的。你能给我一小段代码吗？ – 2012-01-30 06:37:16

事情是这样的：

int main() 
{ 
    Node flash(FLASH_ID); 
    Node mp3(MP3_ID); 

    mp3.children.push_back(flash); 
    // repeat 
}

来源

2012-01-30 06:47:16

您可以使用一个以上的链接指针。即

struct node 
{ 
int id; 
node *first_child; 
node *second child; 
node *third_child; 
}

在你情况下，最大为3 您可以指向节点与不同的儿童和访问它们。如果少于3个孩子，可以将其设置为NULL。

来源

2013-12-05 11:00:11 user3069721

如何构建一个非递归的二叉树？

回答

相关问题