代码之家 › 专栏 › 技术社区 › EliteTUM

将任意节点及其子节点作为树中的子节点移动。hh小时

appendchild children parent-child tree c++

EliteTUM · 技术社区 · 7 年前

我正在使用 tree.hh 实施我有一个简单的“树”,如下所示(a、B和C是没有父母的兄弟姐妹,B1是B的孩子):

A
B
  B1
C

现在,我想将C“移动”为B的孩子。我尝试了以下最小的示例,但没有找到使用树hh小时 .

我找到的唯一解决方案是:

从C及其子树中提取一个子树(将其从原始树中删除)
将C的子树作为子树附加到所需的新父树B

See code on pastebin.com

#include <iostream>
#include "tree.hh"
#include "tree_util.hh"

void print_tree(const tree<std::string>& tr)
{
    tree<std::string>::pre_order_iterator it = tr.begin();
    tree<std::string>::pre_order_iterator end = tr.end();
    if(!tr.is_valid(it)) return;
    int rootdepth=tr.depth(it);
    std::cout << "-----" << std::endl;
    while(it!=end) {
        for(int i=0; i<tr.depth(it)-rootdepth; ++i)
            std::cout << "  ";
        std::cout << (*it) << std::endl << std::flush;
        ++it;
        }
    std::cout << "-----" << std::endl;
}

int main(int, char **)
{
    tree<std::string> my_tree;

    tree<std::string>::iterator iA = my_tree.insert(my_tree.end(), "A");
    tree<std::string>::iterator iB = my_tree.insert(my_tree.end(), "B");
    tree<std::string>::iterator iB1 = my_tree.append_child(iB, "B1");
    tree<std::string>::iterator iC = my_tree.insert(my_tree.end(), "C");        
    print_tree(my_tree);

    // this makes a copy of "C" --> not what I want
    auto iC_append = my_tree.append_child(iB, iC);
    print_tree(my_tree);
    my_tree.erase(iC_append);

    // this extracts "C" into a separate tree and then appends the tree as child to "B"
    tree<std::string> sub_tree = my_tree.move_out(iC);
    my_tree.move_in_as_nth_child(iB, my_tree.number_of_children(iB), sub_tree);
    print_tree(my_tree);
}

我怀疑这是可能的最简单的解决方案。你知道我做错了什么吗?

谢谢

干杯乔纳森

2 回复 | 直到 7 年前

Kasper Peeters 7 年前

使用 move_after ,如中所示

my_tree.move_after(iB1, iC);

这会将节点移动到 iC (以及任何子女,如果有)成为 B .

EliteTUM 7 年前

这花了一些时间,但我想我找到了一个——至少是可行的,或多或少是可靠的——答案。

我首先将一个空的子节点附加到所需的新父节点。然后我使用 ::move_ontop() 使所需的子节点(及其子节点)替换上一步中的空子节点。

因此,我上面的示例现在看起来是这样的(为了测试所有儿童是否也被正确移动,我引入了一个子节点C1作为C的子节点):

#include <iostream>
#include <string>
#include "tree.hh"
#include "tree_util.hh"

void print_tree(const tree<std::string>& tr)
{
    tree<std::string>::pre_order_iterator it = tr.begin();
    tree<std::string>::pre_order_iterator end = tr.end();
    if (!tr.is_valid(it)) return;
    int rootdepth = tr.depth(it);
    std::cout << "-----" << std::endl;
    while (it != end) {
        for (int i = 0; i<tr.depth(it) - rootdepth; ++i)
            std::cout << "  ";
        std::cout << (*it) << std::endl << std::flush;
        ++it;
    }
    std::cout << "-----" << std::endl;
}

int main(int, char **)
{
    tree<std::string> my_tree;

    tree<std::string>::iterator iA = my_tree.insert(my_tree.end(), "A");
    tree<std::string>::iterator iB = my_tree.insert(my_tree.end(), "B");
    tree<std::string>::iterator iB1 = my_tree.append_child(iB, "B1");
    tree<std::string>::iterator iC = my_tree.insert(my_tree.end(), "C");
    tree<std::string>::iterator iC1 = my_tree.append_child(iC, "C1");
    print_tree(my_tree);

    // First append an empty-child to the desired parent...
    auto iNew = my_tree.append_child(iB);
    // ...and then "squash" the empty child with the source child (and sub-children)
    iC = my_tree.move_ontop(iNew, iC);
    print_tree(my_tree);
}

现在的输出符合要求:

-----
A
B
  B1
C
  C1
-----
-----
A
B
  B1
  C
    C1
-----