Java - 通过给定的唯一索引号将一棵树附加到另一棵树的分支

Question

我有一个这样的java类，

    class Block{
        private int index;
        private Block left;
        private Block right;

        public int getIndex() {
            return index;
        }

        public Block setIndex(int index) {
            this.index = index;
            return this;
        }

        public Block getLeft() {
            return left;
        }

        public Block setLeft(Block left) {
            this.left = left;
            return this;
        }

        public Block getRight() {
            return right;
        }

        public Block setRight(Block right) {
            this.right = right;
            return this;
        }
    }

然后，我使用 setter 方法创建了两棵这样的树。

    Block tree1 = new Block()
        .setLeft(new Block()
                        .setLeft(new Block())
                        .setRight(new Block())
        )
        .setRight(new Block()
                        .setLeft(new Block())
                        .setRight(new Block())
        );

和，

    Block tree2 = new Block()
        .setRight(new Block()
                .setRight(new Block()
                        .setRight(new Block()
                                .setLeft(new Block())
                                .setLeft(new Block())
                        )
                )
        );

所以，我想要一个像这样的方法，

int blockIndex = 3;
boolean replace = false;//add if new, else do nothing
tree1.appendBlock(blockIndex,tree2,replace);

树应该能够直接创建(如 tree1 和 tree2)，也可以在循环中创建。有任何想法吗？提前致谢!

Answer 1

这里可能的解决方案:

class Block {

    ...

    boolean appendBlock(int atIndex, Block tree, boolean replace) {
        if (left == right == null)
            return false;

        if ((left != null) && (left.index == atIndex) {
            if (replace) 
                setLeft(tree);
        } else
            if ((right != null) && (right.index == atIndex)) {
                if (replace) 
                    setRight(tree);
            } else
                if ((left == null) || !left.appendBlock(atIndex, tree, replace))
                    if ((right == null) || !right.appendBlock(atIndex, tree, replace))
                        return false;

        return true;
    }

    ...

}

用法:

...

replace = false;
if (!tree1.appendBlock(index, tree2, replace))
    throw Exception(String.format("Child node with index %d not found", index));

当 replace = false - 方法搜索具有指定索引的子节点，如果找不到则返回 false。

如果 replace = true，则如果找到具有指定索引的子节点 - 它将替换为指定的 Block 节点。

更新。

要让它在找不到节点时始终抛出异常，可以使用以下技巧:

// define actual searcher function as private util
// it's safe to call it as it's only indicates success with boolean
// result, so no exceptions would be thrown
protected boolean appendBlockIfFound(int atIndex, Block tree, boolean replace) {
    if (left == right == null)
        return false;

    // same code as above in appendBlock() method
    ...

    return true;
}

// ... and the real worker, exposed to the class user (developer)
// will throw exception on error
public void appendBlock(int atIndex, Block tree, boolean replace) {
    if (!appendBlockIfFound(atIndex, tree, replace))
        throw Exception(String.format("Child node with index %d not found", atIndex));
}

更新。 2

非固定数量子节点的搜索器功能:

class Block extends ArrayList<Block> {

    ...

    public Block(int childs) {
        super(childs);
        while (childs > 0)
            add(null);
    }

    private boolean appendBlockIfFound(int atIndex, Block tree, boolean replace) {
        if (size() <= 0)
            return false;

        for (int i = 0; i < size(); i++) {
            Block child = get(i);
            if (child == null)
                continue;
            if (child.index == atIndex) {
                if (replace)
                  set(i, tree);
                return true;
            }
        }

        for (Block child: this)
          if ((child != null) && child.appendBlockIfFound(atIndex, tree, replace))
            return true;

        return false;
    }

    @Override
    public Block set(int index, Block child) {
      super.set(index, child);
      return this;
    }

    ...

}

用法:

class TenBlock extends Block {

    public TenBlock() {
        super(10);
    }

}

...然后:

Block root = new TenBlock();

Block child10 = root.get(9);

root.set(5, (new TenBlock()).set(2, new TenBlock()))
    .set(6, new TenBlock())