代码之家 › 专栏 › 技术社区 › Kev Luxem

如何动态构建完整的二叉树?

binary-tree tree algorithm c++

Kev Luxem · 技术社区 · 7 年前

两个或没有子项)。代码将用C++实现。我可以用手实现我的树,但正如我所拥有的

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

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

树列表向量(左侧的数字,因此是一维向量):

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)

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

连接到根部/副槽的一侧。括号中的数字是

我的树遵循两条规则:

t1始终连接到根

我现在想做的是创建一个通用算法,用

我的想法是通过给定树大小的开关盒来创建这些树。不幸的是,在这些情况下,我最终得到了很多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语句。

我现在的问题是:你知道如何以更好的方式甚至完全不同的方式实现这个算法吗? 关于这一点的任何建议都是有益的。

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

请参见下面我如何从图形中获取向量:

我合并两个节点的代价函数是C=Node\u A+Node\u B/edgewight。

合并过程:
1.12+6->6.

3.6+24->6.
4.6+9->6.
5.6+22->6.

结果向量(与上述属性相同)和树:

(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

也许还有一种更简单的方法可以从合并过程中构建向量,以便在下一步中获得我的树。

1 回复 | 直到 7 年前

Kev Luxem 7 年前

我最终解决了我的问题(使用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; }
};

// 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;
}

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