java - 如何创建叶节点然后构建树

Question

我已经按升序排列了一个整数优先级队列。

我现在需要按升序为该优先级队列中的每个术语创建一个叶节点。然后，我需要使用这些叶节点来创建一棵树，方法是获取前两项的总和并将它们替换为它们的总和的叶节点，依此类推。

例如，如果叶子节点是{1, 2, 3, 4, 5}，那么，由于1 + 2 = 3，新的叶子节点集合应该是{3, 3, 4, 5}，其中 3 分别有左 child 1 和右 child 2。那么，从 3 + 3 + 6 开始，新的叶子节点集合应该是 {4, 5, 6}，其中 6 的左子节点和右子节点分别为 3 和 3。那么，由于 4 + 5 = 9，新的叶节点集应该是 {6, 9}，其中 9 的左子节点和右子节点分别为 4 和 5。那么，由于 6 + 9 = 15，新的叶子节点集应该是 {15}，其中 15 的左子节点和右子节点分别为 6 和 9。

请帮助我了解如何在 Java 中解决这个问题。谢谢。

Answer 1

Java 是一种 OOP 语言，这意味着您必须编写“配方”(称为类)才能创建事物(叶节点、树、任何东西......)。

树的标准方法如下:

class Tree{

    class LeafNode{

        LeafNode children[];
        String data;        //data could be any Object or Generic

        LeafNode(int childrenNumber, String d){
            data = d;
            children = new LeafNode[childrenNumber];
        }
    }


  LeafNode root;

/*
 *  There can be the class Tree Constructor and put-get functions
 */

}

您提到的 leaf-sum 习惯用法可以在 put 方法中实现。