无法围绕填充n-ary树包装我的头

Question

我正在做一个家庭作业项目，我从文件中读取连接工作站的列表，并以格式创建hashmap（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 

Answer 1

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

作出这样的发现一个节点的每一个孩子的功能，并呼吁每一个孩子这样的功能：

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将从根开始创建树。

P.S.我正在写这个，我没有尝试我的代码，而且我的Java有点生疏，所以你可能会期望它包含语法错误（就像我已经将所有的字符串以小s修改为大写S刚才）。

---

编辑：

它是能够找出一个递归问题你自己，如果你有作为一个程序员的计划非常重要。有关如何找出递归的一些帮助。

1. 有一些问题（如你的）闻起来像递归。他们是关于在多个方向深入的算法，并且你只是无法通过一个简单的循环来完成它。或者当你尝试构建一些可以包含同一事物的多个实例的东西时，等等。但要小心。如果您使用的是imperative语言（大多数语言，除了declarative，例如Erlang，Prolog等）（其中递归既是面包又是黄油）编程，递归往往会相当昂贵。如果你能想到一个产生相同结果但不递归的算法，它通常更便宜。
2. 如果您确定问题需要递归，那就试试吧：尝试找到一个递归的构建块。在你的情况下，它是“创建一个节点，并将它的所有子节点添加到它”。子节点应该包含他们的子节点，所以当你添加子节点时，你在每个节点上调用相同的步骤（该步骤是查找并添加它们的子节点）。
3. 我们准备好了吗？在处理递归问题时，我通常会觉得即使一切都很完美，还是有一些东西可以做。这是因为你不会从头到尾写出算法，而是以一种奇怪的不自然的顺序。在你的情况下，我们远未准备好。
4. 为什么它不是无限的？在处理递归时，可以非常容易地调用自己的函数，因此它是一个stack overflow。我们需要找到函数的边界。在你的情况下，如果一个节点没有更多的子节点，递归会结束。但是请等待：如果连接是双向的，两个节点将互为孩子，所以每个节点都有一个孩子！不知何故，我们需要停止将节点添加到树中！我能想到的最直接的解决方案是记住之前添加了哪些节点，并且只添加节点，如果尚未添加节点。节点列表是有限的，所以我们最终将耗尽新节点。如果的关键字是。如果在每次递归中都应该有一个。应该有一个递归停止的分支。
5. 我的算法是什么？当你觉得你到了某个地方时，停下来，试着想想你的算法正在做什么。它将如何开始？在开始递归之前，有时需要写几行初始化。在你的情况下，我需要创建根，创建一个字符串列表，并在调用递归之前将根的名称添加到列表中。确保你的算法有一切开始。还要确保它在你想要的时候结束。确保你的条件是在正确的地方。试着想一些简单的例子。

至少这是我如何做到的（也是在回答这个时做的:)）。