c++ - 如何动态构建完整的二叉树？

Question

我目前正在尝试提出一种算法来实现完整的二叉树(二叉树两个或没有 child )动态。代码将在 C++ 中实现。我可以手工实现我的树，但正如我所拥有的我需要 900 棵不同的树来自动执行此操作。在这里我需要一些想法、提示和帮助。

让我们开始解释我在做什么:我从图形合并过程中得到我的树。我根据成本函数合并图中的两个节点。的标签更大的节点将是合并节点的标签(我的图形节点具有空间大小)。所以我最终得到一个包含合并节点的 vector 和新节点的剩余标签(请注意，剩余标签基于节点大小和与票据编号无关)。 vector 中的最后两个条目是合并在一起的第一个节点。下一个更高的条目是合并节点的剩余标签。这将按此顺序继续，直到只有根节点(第一个条目)离开了。

第一个问题是，我的图有不同数量的节点。所以我的合并过程中的树有不同的大小，即我的 vector 有不同的大小。

为了让您了解这是什么样子，请参见以下示例:

treelist vector (左边的数字，所以是一个一维 vector ):

27| root    (0)--> root (27 and 33 are merged, remaining label is 27)
33| right   (1)     
27| left    (2)
27| subroot (3)--> t1   (3 and 27 are merged, remaining label is 27)
27| right   (4)
3 | left    (5)
27| subroot (6) --> t2  (10 and 27 are merged, remaining label is 27)
27| right   (7)
10| left    (8)
27| subroot (9) --> t3  (17 and 27 are merged, remaining label is 27)
27| right   (10)
17| left    (11)
33| subroot (12)--> t4  (31 and 33 are merged, remaining label is 33)
33| right   (13)
31| left    (14)

通过上述 ASCII 格式的树列表 vector 构建的树:

            root
             27
           /    \
       27(t1)   33(t4)
      /   \     /   \
     3  27(t2) 31    33
        /   \ 
      10   27(t3)
            / \
          17   27

同样，我拥有的实际 vector 只是左侧的数字。左/右指的是在其连接到根/子根的一侧。括号内的数字是 vector 中的相对位置。

我的树遵循两条规则:

• t1 始终连接到根
• tk-1 绝不是 tk 的低级连接，例如t1 永远不是 t2 的下层连接

我现在想做的是创建一个通用算法来构建像上面这样的树不同尺寸(最多约 15-20 个)。这里的大小是指内部节点的数量，对于上面的树是 4。

我的想法是/曾经是通过给定树大小的 switch-case 创建这些树。不幸的是，我最终在这些案例中得到了很多 if 语句，对于更高的情况下，它几乎不再是可管理的。

在下面的一般情况下查看我的伪算法(树是自下而上构建的):

PseudoCode: (Note that for building the tree the first insert is the left node and the second is the right node)
switch(treesize)
        case 3: root = vector[0];   //represents root node
                t1 = vector[3];     //represents t1
                t2 = vector[6];     //represents t2
                t3 = vector[9];     //represents t3

                // create node t3 
                t3->insert(vector[11]); t3->insert(vector[10]);

                // create node t2
                if (t3 == vector[8]) {t2->addChild(t3); t2->insert(vector[7]);} 
                if (t3 == vector[7]) {t2->insert(vector[8]); t2->addChild(t3);} 
                else {t2->insert(vector[8]); t2->insert(vector[7]);}            

                // create node t1
                if (t3 == vector[5] && t2 != vector[4]) {t1->addChild(t3); t2->insert(vector[4]);} 
                if (t3 == vector[4] && t2 != vector[5]) {t1->insert(vector[5]); t1->addChild(t3);}
                if (t2 == vector[5] && t3 != vector[4]) {t1->addChild(t2); t1->insert(vector[4]);}
                if (t2 == vector[4] && t3 != vector[5]) {t1->insert(vector[5]); t1->addChild(t2);}
                if (t3 == vector[5] && t2 == vector[4]) { t1->addChild(t3); t1->addChild(t2);}
                if (t2 == vector[5] && t3 == vector[4]) { t1->addChild(t2); t1->addChild(t3);}
                else {t1->insert(vector[5]); t1->insert(vector[4]);}

                // create root (Note that t1 is always connected to the root)
                if (t3 == vector[2]) {root->addChild(t3); root->addChild(t1);}
                if (t2 == vector[2]) {root->addChild(t2); root->addChild(t1);}
                if (t3 == vector[1]) {root->addChild(t1); root->addChild(t3);}
                if (t2 == vector[1]) {root->addChild(t1); root->addChild(t2);}
                if (t1 == vector[2] && (t3 && t2) != vector[1]) {root->addChild(t1); root->insert(vector[1]);
                if (t1 == vector[1] && (t3 && t2) != vector[2]) {root->insert(vector[2]); root->addChild(t1);}


        case 4: root = vector[0];   //represents the root node
                t1 = vector[3];     //represents t1
                t2 = vector[6];     //represents t2
                t3 = vector[9];     //represents t3
                t4 = vector[12];    //represents t4

                // create t4
                t4->insert(vector[14]); t3->insert(vector[13]);

                // create t3
                if (t4 == vector[11]) {t3->addChild(t4); t3->insert(vector[10]);}
                if (t4 == vector[10]) {t3->insert(vector[11]); t3->addChild(t4);}
                else {t3->insert(vector[11]); t3->insert(vector[10]);}

                // create t2
                if (t4 == vector[8] && t3 != vector[7]) {t2->addChild(t4); t2->insert(vector[7]);}
                if (t4 == vector[7] && t3 != vector[8]) {t2->insert(vector[8]); t2->addChild(t4);} 
                if (t3 == vector[8] && t4 != vector[7]) {t2->addChild(t3); t2->insert(vector[7]);}
                if (t3 == vector[7] && t4 != vector[8]) {t2->insert(vector[8]); t2->addChild(t3);}
                if (t4 == vector[8] && t3 == vector[7]) {t2->addChild(t4); t2->addChild(t3);}
                if (t3 == vector[8] && t4 == vector[7]) {t2->addChild(t3); t2->addChild(t4);}
                else {t2->insert(vector[8]); t2->insert(vector[7]);}

                // create t1
                if (t4 == vector[5] && t3 != vector[4] && t2 != vector[4]) {t1->addChild(t4); t1->insert(vector[4]);}
                if (t4 == vector[4] && t3 != vector[5] && t2 != vector[5]) {t1->insert(vector[5]); t1->addChild(t4);} 
                if (t3 == vector[5] && t4 != vector[4] && t2 != vector[4]) {t1->addChild(t3); t1->insert(vector[4]);}
                if (t3 == vector[4] && t4 != vector[5] && t2 != vector[5]) {t1->insert(vector[5]); t1->addChild(t3);}
                if (t2 == vector[5] && t4 != vector[4] && t3 != vector[4]) {t1->addChild(t5); t1->insert(vector[4]);}
                if (t2 == vector[4] && t4 != vector[5] && t3 != vector[5]) {t1->insert(vector[5]); t1->addChild(t2);}
                if (t4 == vector[5] && t3 == vector[4]) {t1->addChild(t4); t1->addChild(t3);}
                if (t4 == vector[5] && t2 == vector[4]) {t1->addChild(t4); t1->addChild(t2);}
                if (t3 == vector[5] && t2 == vector[4]) {t1->addChild(t3); t1->addChild(t2);}
                if (t3 == vector[5] && t4 == vector[4]) {t1->addChild(t3); t1->addChild(t4);}
                if (t2 == vector[5] && t3 == vector[4]) {t1->addChild(t2); t1->addChild(t3);}
                if (t2 == vector[5] && t4 == vector[4]) {t1->addChild(t2); t1->addChild(t4);}

                // create root (Note that t1 is always connected to the root)
                if (t4 == vector[2]) {root->addChild(t4); root->addChild(t1);}
                if (t3 == vector[2]) {root->addChild(t3); root->addChild(t1);}
                if (t2 == vector[2]) {root->addChild(t2); root->addChild(t1);}
                if (t4 == vector[1]) {root->addChild(t1); root->addChild(t4);}
                if (t3 == vector[1]) {root->addChild(t1); root->addChild(t3);}
                if (t2 == vector[1]) {root->addChild(t1); root->addChild(t2);}
                if (t1 == vector[2] && (t4 && t3 && t2) != vector[1]) {root->addChild(t1); root->insert(vector[1]);}
                if (t1 == vector[1] && (t4 && t3 && t2) != vector[2]) {root->insert(vector[2]); root->addChild(t1);}

        case 5: .....

        ....
        ....

正如您所注意到的，对于更高的情况，这将是一团糟。

所以我总是要检查左节点或右节点是否可能连接到子根之一。这实际上会导致所有这些 if 语句。

我现在的问题是:您是否知道如何以更好的方式甚至完全不同的方式实现该算法？对此的任何建议都是有帮助的。

非常感谢您的帮助。

如果有什么不清楚或者我是否应该再举一个例子，请告诉我。

请看下面我是如何从图表中获取 vector 的:

图表:

我合并两个节点的成本函数是 C = Node_A + Node_B/Edgeweight。

合并过程:
1. 12+6 -> 6
2. 24+31 -> 24
3. 6+24 -> 6
4. 6+9 -> 6
5. 6+22 -> 6

结果 vector (与上述相同的属性)和树:

(Note that the first two nodes which merges are the last two entries)
6   --> root                                   root
22                                              6
6                                             /   \
6   --> t1                                 6(t1)   22
9                                          /    \           
6                                        6(t2)   9
6   --> t2                              /   \
24                                    6(t4)  24(t3)
6                                    /   \   /  \
24  --> t3                          6    12 24   31
31 
24
6   --> t4
12
6

也许还有一种更优雅的方法可以从合并过程中构建我的 vector ，以便在下一步中获得我的树。

Answer 1

我终于解决了我的问题(使用 C++)并想在这里展示我的解决方案，以便任何有类似问题的人都能得到一个想法。请注意，这不一定是最佳解决方案，但对我来说效果很好:

首先我创建了一个名为 snode 的节点结构:

struct snode { 
        unsigned int label;
        std::deque<snode*> children;

        snode(const unsigned int& l)                   //! allocates leaf with label l.
                : label(l), children() { }
        snode(const snode& n)
                : label(n.label), children()
                { for (const auto& c : n.children)
                        children.push_back(new snode(*c)); }
        ~snode()
                { for (const auto& c : children) delete c; }
        const std::deque<snode*>& getChildren() const   //! returns children of this node.
                { return children; }
        unsigned int getLabel() const                   //! returns label of this node.
                { return label; }
        bool    isLeaf() const                          //! returns true if node is a leaf.
                { return children.empty(); }
        snode&  insert(const snode& n, const bool before = false)   //! adds child n at the beginning or end of list.
                { if (before) children.push_front(new snode(n));
                  else children.push_back(new snode(n));
                  return *this; }
};

在下一步中，我读入了我的 vector 以创建我的树列表，这是我在原始问题中解释的合并 vector 。此外，我读入了我的树的叶子，即合并过程之前的原始节点:

// create a vector to save merging list 
static uvec treeList()
{   FILE* fp = openFile("mergedlist", "r");
    uvec treelist; unsigned int i = 0;                  
    while ((fscanf(fp, "%d", &i)) != EOF) {                 
        treelist.push_back(i); }                    
    closeFile(fp);
    return treelist;
}


// create a vector to save basin list
static uvec leafList()
{   FILE* fpp = openFile("leaflist", "r");
    uvec leaflist; unsigned int i = 0;                  
    while ((fscanf(fpp, "%d", &i)) != EOF) {                    
        leaflist.push_back(i); }                        
    closeFile(fpp);
    return leaflist;
}

现在我开发了一个函数让我的树动态生长:

static snode* growTree(const uvec& treelist, const uvec& leaflist)
{   std::map<unsigned int,snode*> vn;
    for (unsigned int i = 0; i < leaflist.size(); i++) {    // Loop over all leaves
        unsigned int leaf = leaflist[i];
        vn[leaf] = new snode(leaf); }                   // save leaf nodes and allocate snode
    for (unsigned int j = 0; j < treelist.size();) {    // Loop through all treelist elements
        unsigned int mNode = treelist[j];               // save the current merged node (for j = 0 it's the root, j = 3 is t1...)
        unsigned int rNode = treelist[j+1];             // save the right child of the merged node
        unsigned int lNode = treelist[j+2];             // save the left child of the merged node 
        snode m(mNode); 
        m.insert(*vn[lNode]); m.insert(*vn[rNode]);             
        delete vn[rNode]; 
        delete vn[lNode]; vn[lNode] = new snode(m);
        j = j+3; }                          // counting j+3 to access the next merged node in the treelist vector
    const auto root = vn.begin(); 
    return root->second;
}

感谢所有对我的原始帖子发表评论的人。