用Java从一个数组中构建一棵树形结构（目录表）

Question

用Java从一个数组中构建一棵树形结构（目录表）

4

我有一个字符串数组，其中包含来自HTML标记的文本...

String[] Headers = {"H1", "H1", "H2", "H3", "H3", "H2", "H2", "H3", "H4", "H2", "H2", "H2", "H1", "H2", "H2", "H3", "H4", "H4", "H2" };

我需要将这段内容转化为树形结构。其中，任何Hn都是最近的Hn-1的子级。

ROOT
    H1
    H1
    ...H2
    ......H3
    ......H3
    ...H2
    ...H2
    ......H3
    .........H4
    ...H2
    ...H2
    ...H2
    H1
    ...H2
    ...H2
    ......H3
    .........H4
    .........H4
    ...H2

这似乎应该使用递归完成，而且当我看到解决方案时，我会为自己没有早些想到而后悔。有人能给我一个解决方案吗？

更新：因此，我尝试了几个变量的递归，但完全没有运气。事实证明，我使这个问题变得比必须的更难。

由于出现了一个测试用例，

String [] Headers = {"H1"，“H1”，“H3”，“H3”，“H5”，“H4”，“H4”，“H4”};

我对bcorso的答案进行了微小的修改，以下是我的最终版本：

private void addChildren(TocItem root, Elements headers) {
    if(headers == null || headers.size() == 0) return;

    Map<Integer, TocItem> mostRecent = new HashMap<Integer, TocItem>(headers.size());

    int startLevel = getTagLevel(headers.get(0)) - 1;
    mostRecent.put(startLevel, root);

    for(int i = 0; i < headers.size(); i++) {
        Element htag = headers.get(i);
        int level = getTagLevel(htag);
        TocItem next = new TocItem(htag, level);

        int offset = 1;
        TocItem parent =  mostRecent.get(level - offset);
        while(parent == null && offset < level) {
            offset++;
            parent = mostRecent.get(level - offset);
        }
        if(parent != null) {
            parent.addChild(next);
        }
        mostRecent.put(level, next);
    } 
}

- kasdega

1

你从哪里得到这个问题的？ - Erran Morad

一个栈和一个for循环就足以构建树了。现在你能试一下吗？ - cherouvim

1

@BoratSagdiyev 这来自我正在开发的项目...我正在传入一堆HTML，然后使用Jsoup进行解析，并且需要将所有标题转换为目录。我遇到的问题是当从h4返回到h2或h1时。 - kasdega

@kasdega 除了我的回答之外，你应该使用一个适当的DOM库，而不是从头开始创建一个解决方案。 - etherous

@kasdega，如果您想看一下，我已经添加了一个非常简单易懂的答案。 - bcorso

2个回答

4

这里是在 Ideone 上的工作示例，代码如下:

public static class Node{
    int level;
    List<Node> children = new ArrayList<Node>();
    Node(int level){ this.level = level;}
}

public static void main (String[] args) throws java.lang.Exception{
    String[] h = {"H1", "H1", "H2", "H3", "H3", "H5", "H2", "H2", "H3", "H4",
                  "H2", "H2", "H2", "H1", "H2", "H2", "H3","H4", "H4", "H2"};
                        
    Node[] mostRecent = new Node[6];                      // 5 headers + 1 root tag.
    mostRecent[0] = new Node(0);                          // root tag (level = 0)

    for(int i = 0; i < h.length; i++){
        int level = Integer.parseInt(""+h[i].charAt(1));  // get tag's "level"
        Node n = new Node(level);                         // create Node for tag
        mostRecent[level] = n;                            // update most recent tag
              
        int pLevel = level - 1;                          
        while(mostRecent[pLevel] == null) --pLevel;       // find nearest parent
        mostRecent[pLevel].children.add(n);               // append tag Node to parent
        
        for(int j = 1; j < level; j++)                    // print tag with indention
            System.out.print("\t");
        System.out.println(h[i]);
    } 
}

代码解释：

该代码通过在for循环中简单遍历标题列表，并在数组Node[]中跟踪最近的

、

和

，以O(n)的时间运行。

该数组用于通过使用相应的整数引用其级别来检索标签的最近节点。例如，使用`mostRecent[1]`检索具有最新“H1”标记的节点（注意，元素`0`用作整个文档的根）。

注意：如果需要专门的函数打印树，请参见此Ideone。

- bcorso

没问题，很高兴能帮助到您！ - bcorso

看看我的更新 - 我稍微调整了一下你的代码，以适应这种情况...H3 H3 H5 H4 h4（没有父级h4） - kasdega

@kasdega，你能否更新你的问题示例以包含上述情况？那么如果没有先前的H4，这种情况下H5的父级将是什么？ - bcorso

它会沿着行向下移动到最近的h3，然后是h2，再然后是h1，直到找到一个并使用它，或者找不到任何一个，在这种情况下，它只会将其添加到mostRecent。 - kasdega

你说得对，这与原问题不同，但我认为没关系。你的解决方案非常好。 - kasdega

显示剩余2条评论

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- etherous · Accepted Answer

给你：

class Example
{
    static class Node
    {
        final String name;
        final int indent;
        Collection<Node> children = new LinkedList<> ();

        Node (final String name)
        {
            this.name = name;
            this.indent = Integer.valueOf (name.substring (1));
        }
        Collection<Node> getChildren ()
        {
            return Collections.unmodifiableCollection (this.children);
        }
        void addChild (final Node child)
        {
            this.children.add (child);
        }
        @Override
        public String toString ()
        {
            final StringBuilder sb = new StringBuilder ();
            for (int i = 0; i < this.indent; i++)
                sb.append ("   ");
            sb.append (this.name).append ('\n');
            for (final Node node : this.children)
                sb.append (node.toString ());
            return sb.toString ();
        }
    }

    List<Node> contents = new LinkedList<> ();
    ArrayList<Node> stack = new ArrayList<> ();

    public void add (final String[] headers)
    {
        for (final String h : headers)
        {
            final int n = Integer.valueOf (h.substring (1));
            final Node node = new Node (h);

            while (this.stack.size () > n - 1)
                this.stack.remove (this.stack.size () - 1);

            if (n == 1)
            {
                this.contents.add (node);
                this.stack.add (node);
            }
            else
            {
                this.stack.get (n - 2).addChild (node);

                if (this.stack.size () < n)
                {
                    assert (this.stack.size () == n - 1);
                    this.stack.add (node);
                }
            }
        }
        this.stack.clear ();
    }

    @Override
    public String toString ()
    {
        final StringBuilder sb = new StringBuilder ();
        for (final Node node : this.contents)
            sb.append (node.toString ());
        return sb.toString ();
    }
}

使用方法:

    final Example ex = new Example ();
    ex.add (new String[] {"H1", "H1", "H2", "H3", "H3", "H2", "H2", "H3", "H4", "H2", "H2",
            "H2", "H1", "H2", "H2", "H3", "H4", "H4", "H2"});
    System.out.println (ex);