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 つ下のレベルでない場合)、それは前のノードの祖先のいずれかの子です。

そう：

  1. 行 n のレベルが行 n-1 のレベルに 1 を加えた値に等しい場合、行 n は行 n-1 の子を保持します。
  2. それ以外の場合は、行 n-1 のノードから、行 n のレベルよりもレベルが 1 低いノードが見つかるまで、ツリーを上に移動します。その祖先ノードは、行 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. その前のノードよりも 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()」を呼び出すだけです。ただし、上部に余分な行が 1 行出力されます。

(出力をインデントすると常に読みやすくなります。)

警告: テストされていません。

/** 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 に答える