将任意节点及其 children 移动为 child in tree.hh

Question

我正在使用 tree.hh 实现。我有一个简单的 "tree"，如下所示（A、B 和 C 是没有 parent 的兄弟姐妹，B1 是 child 到 B）：

A
B
  B1
C

现在我想 "move" C 也成为 B 的 child。我尝试了以下最小示例，但没有找到使用 [=] 中的方法执行此操作的简单方法14=].

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

从 C 及其 children 中提取一个子树（从原始树中删除它）
将 C 的子树作为 child 附加到所需的新 parent 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);
}

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

谢谢！

干杯，乔纳森

Answer 1

花了一些时间，但我想我找到了一个 - 至少可行且或多或少稳健的 - 答案。

我首先将一个空的子节点附加到所需的新父节点。然后我使用 ::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
-----

Answer 2

使用move_after，如

my_tree.move_after(iB1, iC);

这会移动 iC 处的节点（以及任何子节点，如果存在）成为 B 的兄弟节点。

将任意节点及其 children 移动为 child in tree.hh

Move an arbitrary node and its children as child in tree.hh

c++

tree

children

parent-child

appendchild