java - 使用对象列表构建树

Question

我的任务是列出 5 本书，每本书包含一个标题和一个评级，然后将它们变成一棵看起来像这样的树:

    //1 1984
    //  2 Animal Farm
    //      3 Crime and Punishment
    //      3 Demons
    //  2 War and Peace

在分层树结构方面，较低的评级优先。

我制作了一个名为 book 的类:

public static class Book {
    protected int rating;
    protected String title;

    public Book (int rating, String title) {
        this.rating = rating;
        this.title = title;
    }
}

然后我创建了一个 Node 类，它将构成树:

public static class Node {
    protected Book book;
    protected List<Node> children;

    public Node(Book book) {
        this.book = book;
        this.children = new ArrayList<>();
    }   
}

我的主要方法是这样的:

    public static void main (String[]args) throws Exception {
    BufferedReader br = new BufferedReader (new InputStreamReader(System.in));
    List<Book> books = new ArrayList<>();
    books.add(new Book(1,"1984"));
    books.add(new Book (2,"Animal Farm"));
    books.add(new Book (3,"Crime and Punishment"));
    books.add(new Book (2,"War and Peace"));
    books.add(new Book (3,"Demons"));

    Node node = createTree(books);

}

最后，这是我遇到最多问题的地方，构建实际的树。它可以简单地包含打印语句，但我对解决此问题的最佳方法感到困惑:

    public static Node createTree(List<Book>books) {

    Node root = new Node (books.get(0));
    root.children.add(root);

    //The first node will be 1984 with a 1 rating. After that I'm not sure what exactly to do next?


    return root;

}

我知道我似乎只是在寻找答案，但实际上我一整天都在构建这个东西，尝试了所有方法，却陷入了死胡同。我知道解决方案可能可以递归解决，但我很难思考它如何再次在 createTree() 方法中工作。任何帮助，将不胜感激。非常感谢。

Answer 1

我对超过 2 个节点的树结构有点陌生。我在想一个 Min-Heap - 一个完整的二叉树，其中每个内部节点的值小于或等于该节点的子节点中的值 - 可能通过操纵树遍历的处理方式来完成同样的事情。

无论如何，假设树可以有超过 2 个叶子，以下解决方案应该对您有所帮助:

---

除了根为空之外，add 方法还需要处理 3 种主要情况:

Case 1:图书评分小于当前节点评分，在当前节点的位置追加新节点，并将当前节点作为叶子添加到新节点。

情况 2:图书评分大于当前节点评分。检查节点是否有叶子，如果没有叶子，我们将书作为叶子添加到当前节点并返回。如果它有叶子，我们输入第一个叶子作为参数并再次调用 add 方法(递归)。

情况 3:图书评分等于当前节点评分。首先，如果被访问的节点是树的根，则将新节点作为叶子添加到索引为 0 的树中。遍历根节点的所有叶子，并将所有不等于书评的叶子添加为叶子改为到新节点。其次，如果它不是根节点，则获取当前节点的父节点并将新节点作为叶子添加到该节点。

---

请注意，每当树需要重新平衡时，叶子都会附加到第一个叶子的叶子上 (leaves.get(0))。其次，第一片叶子是子树的主要持有者。

toString 方法使用预排序迭代并跟踪打印树的深度。

public class Tree {

    private static class Node {
        Book book;
        List<Node> leaves;
        Node parent;

        public Node(Book b, Node p) {
            this.book = b;
            this.leaves = new LinkedList<>();
            this.parent = p;
        }

        @Override
        public String toString() {
            return book.toString();
        }

    }

    private Node root;

    private void swap(Node oldParent, Node newParent) {
        oldParent.leaves.add(newParent);
        newParent.parent = oldParent.parent;
        oldParent.parent = newParent;
        newParent.leaves.add(oldParent);
        oldParent.leaves.remove(newParent);
        if (newParent.parent != null) {
            newParent.parent.leaves.add(0, newParent);
            newParent.parent.leaves.remove(oldParent);
        }
        if (oldParent == root) {
            root = newParent;
            // Handle special scenario when the leaf of the root and the leaf of the the leaf
            // have the same value and then rebalance the leaves.
            if (!oldParent.leaves.isEmpty() && !newParent.leaves.isEmpty()) {
                Node n2 = oldParent.leaves.get(0); 
                Node n1 = newParent.leaves.get(0);
                if (n1.book.rating != n2.book.rating)
                    return;
                root.leaves.add(0, n2);
                n2.parent = root;
                n1.leaves.clear();
            }
        }
    }


    private void add(Node n, Book b) {
        System.out.println("@" + b.toString());
        int prevNodeRating = n.book.rating;
        if (b.rating < prevNodeRating) {
            swap(n, new Node(b, n));
        }
        else if (b.rating > prevNodeRating) {
            if (n.leaves.isEmpty()) {
                Node newNode = new Node(b, n);
                n.leaves.add(newNode);    
            } else {
                add(n.leaves.get(0), b);
                return;
            }
        } 
        else {
            if (n == root) {
                if (!n.leaves.isEmpty() &&  n.leaves.get(0).book.rating == b.rating) {
                    root.leaves.add(new Node(b, n));
                    return;
                } 
                Node newNode = new Node(b, n);
                n.leaves.add(0, newNode);   // set at first position
                Iterator<Node> itr = n.leaves.iterator();
                itr.next(); // skip first;
                while (itr.hasNext()) {
                    Node leaf = itr.next();
                    if (leaf.book.rating >= b.rating) {
                        newNode.leaves.add(leaf);
                        leaf.parent = newNode;
                        itr.remove();
                    } 
                }
            } else {
                n.parent.leaves.add(new Node(b, n.parent));
            }
        }
        System.out.println(toString() + "\n----------------");
    }

    public void add(Book b) {
        if (root == null)
            root = new Node(b, null);
        else add(root, b);
    }

    private void toStringItr(Node n, int lvl, StringBuilder sb) {
        if(n == null) return;                    
        for (int i = 0; i < 3*lvl; i++) {
           sb.append(" ");
        }
        sb.append(n.book.toString()).append("\n");
        n.leaves.forEach((leaf) -> {
            toStringItr(leaf, lvl + 1, sb);
        });

    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        if (root == null)
            return "null";
        toStringItr(root, 0, sb);
        return sb.toString();
    }
}

输入

Tree mt = new Tree();
mt.add(new Book(4,"A"));
mt.add(new Book(3,"B"));
mt.add(new Book(2,"C"));
mt.add(new Book(3,"D"));
mt.add(new Book(1,"E"));
mt.add(new Book(4,"F"));
mt.add(new Book(1,"G"));
mt.add(new Book(2,"H"));
mt.add(new Book(8,"X"));
mt.add(new Book(7,"Y"));
System.out.println(mt.toString());

输出

1, E
   1, G
      2, C
         3, B
            4, A
               7, Y
                  8, X
            4, F
         3, D
      2, H

或者，

1, 1984
   2, Animal Farm
      3, Crime and Punishment
      3, Demons
   2, War and Peace

一步步输出(先root后)

@3, B
3, B
   4, A

----------------
@2, C
2, C
   3, B
      4, A

----------------
@3, D
@3, D
2, C
   3, B
      4, A
   3, D

----------------
@1, E
1, E
   2, C
      3, B
         4, A
      3, D

----------------
@4, F
@4, F
@4, F
@4, F
1, E
   2, C
      3, B
         4, A
         4, F
      3, D

----------------
@1, G
1, E
   1, G
      2, C
         3, B
            4, A
            4, F
         3, D

----------------
@2, H
@2, H
@2, H
1, E
   1, G
      2, C
         3, B
            4, A
            4, F
         3, D
      2, H

----------------
@8, X
@8, X
@8, X
@8, X
@8, X
1, E
   1, G
      2, C
         3, B
            4, A
               8, X
            4, F
         3, D
      2, H

----------------
@7, Y
@7, Y
@7, Y
@7, Y
@7, Y
@7, Y
1, E
   1, G
      2, C
         3, B
            4, A
               7, Y
                  8, X
            4, F
         3, D
      2, H

----------------