0

我有一个线性数据结构，其中每个节点都有一个级别。父节点的级别为 1，父节点的子节点的级别为 2，子节点的子节点的节点为 3，另一个父节点的级别为 1。例如下面

<node level=1> //parent node
<node level=2> //child of encountered parent node
<node level=2> //child of encountered parent node
<node level=3> //child of encountered child node
<node level=2> //child of encountered parent node
<node level=1> //parent node
<node level=1> //parent node
<node level=2> //child of encountered parent node
<node level=3> //child of encountered child node
<node level=4> //child of encountered child node
<node level=1> //parent node

本质上我正在尝试建立一个列表。（对其他建议开放），使得列表中的每个元素都是一个父节点，每个父节点都有子节点列表，每个子节点可以有子节点列表等。每个元素都是一个节点和所有属性是一样的。

我已经通过跟踪当前级别尝试了代码，但是我不确定如何正确地将具有子节点的子节点添加回第一个子节点的父节点。我觉得这可能最好通过递归来处理，但我从来没有能够以有序的方式真正实现递归。

4

1 回答 1

0

你不必考虑所有的嵌套。你只需要考虑你在哪里（例如，节点列表中的上一个条目是什么级别）以及下一个条目在哪里。

在这种情况下，解决方案在于读取树的方式。请注意，在作为树输入源的节点列表中，紧跟在父节点之后，下一个节点是子节点。如果某个节点之后的节点不是该节点的子节点（即，如果它的级别不是低一级），则它是前一个节点的祖先之一的子节点。

所以：

  1. 如果第 n 行的级别等于 1 加上第 n-1 行的级别，则第 n 行包含第 n-1 行的子节点。
  2. 否则，从第 n-1 行的节点向上走，直到找到一个比第 n 行的级别低一级的节点。该祖先节点是第 n 行节点的父节点。

您也不必递归地执行此操作。

currLevel = 0;
currNode = root;
do {
   node = read();
   if (somethingRead()) {
      // If this one is one level below the last one, it goes in as a child and we're done
      if (node.level == currNode.level + 1) {
         currNode.addChild(node);
         currNode = node;
      } else {
         // Otherwise this one has to be at a level above this node's child, so back up
         while (node.level >= currNode.level) {
            currNode = currNode.parent(); // check for root left out here ...
         }
         if (node.level == currNode.level + 1) {
            currNode.addChild(node);
            currNode = node;
         } else {
            // handle illegal condition in list
         }
      }
   }
} while (moreNodesToRead());

对您的解决方案的回应

您的解决方案反映了您不愿意使用假节点作为树的根。这是一个可以做出的设计选择。这是我的版本。

我有点担心您如何处理被弄乱的传入数据

  1. 呈现的节点比其前一层多一层。
  2. 显示的第一个节点不在级别 1。
  3. 节点的级别为 0 或更低（不检查以下内容）

另外，我建议您允许currNode在null当前节点应该是根时。从理论上讲，它可能发生在while备份当前节点的循环中，但请注意，在代码中的这一点上，您已经知道新节点的级别高于 1，因此currNode永远不应备份超过级别 1 的节点。如果该假设是错误的，让它生成 NPE 是合理的。

我建议进行以下更改：

Node currNode = null;
List<Root> roots = new ArrayList<Root>();

do {
      Node node = generateNode(nodesList.next());
      if (node.getLevel() == 1) { //implies root level node
         roots.add(node);
         currNode = node;
      } else if (currNode == null) {
         // ... handle misformed input ... first node isn't level 1, ignore it
      } else if (node.getLevel() == currNode.getLevel() + 1) {
         currNode.childrenList.addChild(node);
         node.setParent(currNode);
         currNode = node;
      } else {
         Node savedCurrNode = currNode;
         while (node.getLevel() <= currNode.getLevel()) {
             currNode = currNode.getParent();
         }
         if (node.getLevel() == currNode.getLevel() + 1) {
             currNode.childrenList.addChild(node);
             node.setParent(currNode);
             currNode = node;
         } else {
             // ... handle misformed input ... node level > last node level + 1, ignore it
             currNode = savedCurrNode;
         }

} while (hasMoreNodes(nodesList));

印刷

我对其进行了一些重新排列并更改了一些名称和职责（在评论中列出）。只是从上面详细说明一点，如果根只是一个节点，则根本不需要'printRoots（）'方法。只需在级别设置为 0 的假根节点上调用“printChildren()”即可。但它会在顶部多打印一行。

（如果您缩进输出，它总是更容易阅读。）

警告：未经测试。

/** Print all the root nodes, each with any children it may have */
private void printRoots(List<Node> roots) {

    for (int j = 0; j < roots.size(); j++) {
        Node node = roots.get(j);
        printContents(node, 1);
    }

}

/** Print one node and any children it might have */
private void printContents(Node node, int level) {

    for (int i=1 ; i < level ; ++i) {
        print("    ");
    }
    print(node.toString());
    println();

    printChildren(node, level+1);

}

/** Print each child of the supplied node. Notice how this is just like getting the
 * list of children and calling 'printRoots()'
 *//
private void printChildren(Node node, int level) {

    for (int i = 0; i < node.getChildrenList().size(); i++) {
        Node childNode = node.getChildrenList().get(i);
        printContents(childNode, level);
    }

}
于 2013-03-15T15:07:19.673 回答