无法让我的头像填充一棵 n 元树

我正在做一个家庭作业项目，从一个文件中读取连接站的列表，并创建一个格式为(key=String station，value=ArrayList连接站(的哈希图，到目前为止效果不错。

然后，用户可以选择一个家庭站点，在这个点上，我试图创建一个树来表示来自家庭的所有可访问的站点。例如，树可能看起来像：

           HomeStation
           /      
    station1      station2
                /   |     
        station3 station4 station 5

但我无法理解如何将这些站点添加到树上，而不仅仅是根和它的孩子。那么，有人能给我一些关于我应该做什么/看什么的建议吗？

到目前为止我的树节点类：

/**
* TreeNode class 
* Represents a N-ary tree node
* Uses ArrayList to hold the children.
* @author Ásta B. Hansen (11038973)
*
*/
public class TreeNode {
    private String station;
    private TreeNode parent;
    private List<TreeNode> children;
    /**
     * Constructor
     * @param station - the station to be stored in the node
     */
    public TreeNode(String station) {
        this.station = station;
        parent = null;
        children = new ArrayList<TreeNode>(); //Empty list of children  
    }
    /**
     * Sets the station in this node
     * @param station - the station to be stored
     */
    public void setStation(String station) {
        this.station = station;
    }
    /**
     * Returns the station in this node
     * @return station
     */
    public String getStation() {
         return station;
    }
    /**
     * Sets the parent of this node
     * @param parent - the parent node
     */
    public void setParent(TreeNode parent) {
        this.parent = parent;
    }
    /**
     * Returns the parent of this node or null if there is no parent
     * @return parent
     */
    public TreeNode getParent() {
        return parent;
    }
    /**
     * Adds a single child to this node
     * @param newChild - the child node to be added
     */
    public void addChild(TreeNode newChild) {
        children.add(newChild);
        newChild.setParent(this);
    }
    /**
     * Returns a list of the children of this node
     * @return children - the children of the node
     */
    public List<TreeNode> getChildren() {
        return children;
    }
    /**
     * Returns the number of children this node has
     * @return number of children
     */
    public int getNumberOfChildren() {
        return children.size();
    }
    /**
     * Indicates whether this is a leaf node (has no children)
     * @return true if the node has no children 
     */
    public boolean isLeaf() {
        return children.isEmpty();
    }
    /**
     * TODO print preOrder tree
     */
    public void printPreOrder() {
    }
    /**
     * TODO print postOrder tree
     */
    public void printPostOrder() {
    }
}

总的来说：

private static void selectHome() {
    if(network != null) {
        System.out.print("Please enter the name of the home station> ");
        homeStation = scan.next();
        if(!network.hasStation(homeStation)) { //if station does not exist
            System.out.println("There is no station by the name " + homeStation + "n");
            homeStation = null;
        } else {
            //create the tree with homeStation as root
            createTree(homeStation);
        }
    } else {
        System.out.println("You must load a network file before choosing a home station.n");
    }
}
private static void createTree(String homeStation) {
    root = new TreeNode(homeStation); //create root node with home station
    //TODO Construct the tree
    //get list of connecting stations from network (string[])
    //and add the stations as children to the root node
    for(String stationName : network.getConnections(homeStation)) {
        TreeNode child = new TreeNode(stationName);
        root.addChild(child);
        //then for every child of the tree get connecting stations from network
        //and add those as children of the child. 
        //TODO as long as a station doesn't already exist in the tree.
    }   
}

编辑：车站输入文件

Connection: Rame Penlee
Connection: Penlee Rame
Connection: Rame Millbrook
Connection: Millbrook Cawsand
Connection: Cawsand Kingsand
Connection: Kingsand Rame
Connection: Millbrook Treninnow
Connection: Treninnow Millbrook
Connection: Millbrook Antony
Connection: Antony Polbathic
Connection: Polbathic Rame

这是一个基本问题(我猜这一定是一个家庭作业(，我认为一个简单的递归可以帮助你解决它。

制作一个查找节点的每个子节点的函数，并在每个子节点上调用此函数：

private static void addNodesRecursive(TreeNode node) {
    for(String stationName : network.getConnections(node)) {
        TreeNode child = new TreeNode(stationName);
        node.addChild(child);
        addNodesRecursive(child);
    }   
}

只有当我们正在制作的图是DAG时，这才有效。如果图形中有任何循环(即使是双向边(，它也会失败。

它将失败，因为我们还没有存储之前是否向图中添加了节点。父母将与孩子建立联系，反之亦然，他们将作为邻居无限增加。

你可以做的是：列出一个列表，存储添加的内容。

private static void addNodesRecursive(TreeNode node, List<TreeNode> addedList) {
    for(String stationName : network.getConnections(node)) {
        TreeNode child = new TreeNode(stationName);
        node.addChild(child);
        addedList.add(child);
        addNodesRecursive(child, addedList);
    }   
}

只有当新节点还不在addedList上时，才添加它：

private static void addNodesRecursive(TreeNode node, List<String> addedList) {
    for(String stationName : network.getConnections(node)) {
        if (!addedList.contains(stationName)) {
            TreeNode child = new TreeNode(stationName);
            node.addChild(child);
            addedList.add(child);
            addNodesRecursive(child, addedList);
        }
    }   
}

你只需要在根节点上调用它，所以你的createTree将是：

private static void createTree(String homeStation) {
    root = new TreeNode(homeStation);
    List<String> addedList = new ArrayList<String>();
    addedList.add(homeStation);
    addNodesRecursive(root, addedList);
}

BAM你完了。调用createTree将创建从根开始的树。

附言：我是在写这篇文章的，我没有尝试我的代码，而且我的Java有点生疏，所以你可能会认为它包含语法错误(就像我刚才用小写S将所有字符串更正为大写S一样(。

编辑：

如果你有成为程序员的计划，那么能够自己解决递归问题是非常重要的。关于如何计算递归的一些帮助。

有些问题(像您的问题(闻起来像递归它们是关于深入多个方向的算法节奏，你无法通过简单的循环来完成它。或者当你试图构建一个可以包含同一事物的多个实例的东西时，等等。不过要小心。如果您使用命令式语言编程(大多数语言，除了一些声明性语言，如Erlang、Prolog等……其中递归既是面包也是黄油(，递归往往非常昂贵。如果你能想到一种产生相同结果但不是递归的算法，它通常更便宜
如果你决定这个问题需要递归，那么就去做：试着找到递归的构建块在您的案例中，它是"创建一个节点并将其所有子节点添加到其中"。子节点应该包含其子节点，因此当添加子节点时，您会对每个子节点调用相同的步骤(该步骤是查找和添加其子节点(
我们准备好了吗在处理递归问题时，我通常觉得即使一切都很完美，也必须有事情要做。这是因为你不是从开始到结束都写算法节奏，而是以一种奇怪的、不自然的顺序。就你的情况而言，我们还远远没有准备好
为什么它不是无限的在处理递归时，很容易使函数无限调用自己，从而导致堆栈溢出。我们需要找到函数的边界。在您的情况下，如果一个节点没有更多的子节点，则递归将结束。但是等一下：如果连接是双向的，那么两个节点将是彼此的子节点，所以每个节点都将有一个子节点！不知怎么的，我们需要停止向树中添加节点！我能想到的最简单的解决方案是记住之前添加了哪些节点，并且只有在尚未添加的情况下才添加节点。节点列表是有限的，所以我们最终会用完新的节点。如果，则关键字为。在每个递归中都应该有一个if。并且应该有一个条件分支，递归停止
我的算法正在做什么当你觉得自己有所进展时，停下来，试着思考一下你的算法节奏目前在做什么。它将如何开始？在某些情况下，您需要在开始递归之前编写几行初始化。在您的情况下，我需要创建根，创建一个字符串列表，并在调用递归之前将根的名称添加到列表中。确保你的算法节奏有一切可以开始。还要确保它在你想要的时候结束。确保你的条件在正确的地方。试着通过简单的例子来思考

至少我是这样做的(在回答这个问题时也是这样做的：(。

相关内容

最新更新

热门标签：