2

我想创建一种非递归的方式来创建类似于 -

1
1.1
1.2
1.2.1
1.3
2
2.1  etc etc (these items can be infinitely deep)

我拥有的唯一识别信息是一个两个数字的 ID。第一个 ID 是标识项目的 ID，第二个 ID 标识它属于什么，零始终是文档根。

例如：

123,0
456,123
789,123
777, 789
999, 123
888,0
444,888

会被翻译成——

1
1.1
1.2
1.2.1
1.3
2
2.1

数据是内联读取的。我不知道它之后发生了什么，只知道它前面发生了什么。我相信这应该很简单，但由于某种原因，我很难想出一个有效的解决方案。注意：项目将始终按顺序排列。例如，在获得项目 1.1 之前，我永远不会获得项目 1.2，等等。

4

2 回答 2

0

我的算法是：

  • 当你阅读每一对(x, y)时，插入x一棵树作为y
  • 要打印，请在树上运行深度优先递归。如果您想在没有递归的情况下执行此操作，则可以改用堆栈实现。

当然，这是一个非常笼统的草图 - 就具体实现而言，有很多选择！

于 2012-10-23T19:51:32.507 回答
0

如果项目以正确的顺序出现，堆栈就可以了：

public class Item {
    private int id;
    private int parentId;

    public Item(int id, int parentId) {
        this.id = id;
        this.parentId = parentId;
    }

    public int getId() { return id; }
    public int getParentId() { return parentId; }
}

public class NumberedItem {
    private Item item;
    private int childCount;
    private String number;

    public NumberedItem(Item item, String number) {
        this.item = item;
        this.childCount = 0;
        this.number = number;
    }

    public Item getItem() { return item; }
    public String getNumber() { return number; }

    /* package */ int incrementChildCount() {
        return ++childCount;
    }
}

public NumberedItemIterator implements Iterable<NumberedItem> {
    private Iterator<Item> items;
    private Stack<NumberedItem> numberStack;

    public NumberedItemIterator(Iterable<Item> itemsIterable) {
        items = itemsIterable.iterator();
        numberStack = new Stack<NumberedItem>();
        numberStack.push(new NumberedItem(null, null));
    }

    public boolean hasNext() {
        return items.hasNext();
    }

    public NumberedItem next() {
        Item current = items.next();
        int parentId = current.getParentId();

        NumberedItem parent = null;
        while (!numberStack.empty()) {
            NumberedItem candidate = numberStack.peek();
            if (candidate.getItem().getId() == parentId) {
                parent = candidate;
                break;
            }
            numberStack.pop();
        }

        if (parent == null) throw new RuntimeException("Inconsistent ordering");

        String number = Integer.toString(parent.incrementChildCount());
        if (parent.getNumber() != null) {
            number = parent.getNumber() + "." + number;
        }

        NumberedItem result = new NumberedItem(current, number);

        numberStack.push(result);

        return result;
    }

    public void remove() {
        throw new UnsupportedOperationException();
    }
}
于 2012-10-24T07:35:38.460 回答