如何拆分树列表的子项

Question

我一直在尝试如何编写TreeList，但失败了，所以我在谷歌上搜索了一个，并没有从中学习。这很有效，但我现在想做的是，但我找不到如何拆分TreeList。我创建了两个例子，但都失败了。程序崩溃了。我使用的是Java，我所基于的TreeList类是http://yet-another-tree-structure.googlecode.com/svn/trunk/java/src/com/tree/.

原始一个

public TreeNode<T> removeAndCreate() {
    TreeNode<T> tn = new TreeNode<T>(data);
    tn.children = children;
    tn.elementsIndex = elementsIndex;
    elementsIndex.remove(this);
    children.remove(this);
    return tn;
}

我正在使用的较新的

public TreeNode<T> split() {
    TreeNode<T> tP = parent;
    while (tP.isRoot() == false) {
        tP = tP.parent;
    }
    TreeNode<T> tn = new TreeNode<T>(data);
    tn.children = children;
    tn.elementsIndex = elementsIndex;
    tP.elementsIndex.remove(this);
    tP.children.remove(this);
    return tn;
}

我感谢你提前给我的帮助。

Answer 1

在查看了您所基于的类和第二次拆分之后，我将假设拆分意味着将有问题的节点从当前树中移除，并返回一个以有问题节点为根的新树。如果这就是你想要的，那么有一些事情需要解决。首先，你的split函数做：

TreeNode<T> tP = parent;
while (tP.isRoot() == false) {
    tP = tP.parent;
}

问题是，如果当前节点（this）没有parent，则会引发Null异常（所以尝试拆分根节点，应该会出现错误）。我想你的意思是：

TreeNode<T> tP = this;

该改变将避免循环访问可能是null的parent。接下来，您需要从parent及以上级别中删除每个级别的所有elementsIndex。然后，您必须从直接parent中删除children（如果您有parent）。

我想你可能正在寻找的代码如下（假设我没有错过什么）：

public TreeNode<T> split() {
    // Create a new root node for the tree we split off
    TreeNode<T> tn = new TreeNode<T>(data);
    tn.children = children;
    tn.elementsIndex = elementsIndex;
    // For each level of the tree above us make sure we remove
    // ourselves from the elementsIndex at EACH LEVEL until we
    // finish at the root.
    TreeNode<T> tP = this;
    while (tP.isRoot() == false) {
        tP = tP.parent;
        tP.elementsIndex.remove(this);
    }
    // If this node has a parent remove this node as one of
    // our parent's children. We aren't the child of any of the
    // levels above our parent
    if (parent != null)
        this.parent.children.remove(this);
    // Return the root of the newly split tree
    return tn;
}