c - 导航基本二叉树

Question

所以我需要为我的应用程序创建一个基本的二叉树，但我在概念化如何“导航”时遇到了麻烦，即使在生成过程中也是如此。

当然每个节点都有一个地址，并通向另外两个节点，这两个节点分别具有正值和负值。我的问题是，如果我想使用循环创建树，我该怎么做？在第一次迭代中将有两个节点，在第三次迭代中将有四个，依此类推 - 我如何在推进循环之前遍历它们的每个地址？

    for(int i=1;i<=5;i++){
        (*currentAddress).value = i;
        (*currentAddress).positive = i;
        (*currentAddress).negative = i*-1;
        //update current address
    }

我是否必须在每次迭代中都使用 BFS 并一直添加节点直到创建 (2^n-1) 个节点？

Answer 1

您实际上需要左右指针，对吧？然后你可能想使用递归。例如(用一些随机的语言):

function Node* MakeNode(value, limit) {
    Node* node = new Node();
    (*node).value = value;
    // don't create any more children once we get to the depth limit.
    if (value < limit) {
        (*node).positive = MakeNode(value + 1);
        (*node).negative = MakeNode(value - 1);
    }
    return node;
}

// create a 5 deep tree
MakeNode(0, 5);