ノードの深さをソートするソート述語

Question

私はノードのリストを持っています。各ノードは1つまたは複数のツリーに属しています。 （彼らは必ずしも共通の祖先を共有しているわけではありません）

深度優先検索を実行するときに同じ順序でノードをソートしたいと思います。

私は、木のルートを一緒にソートするための述語と、共通の親の子を一緒にソートする別の述語を持っているとしましょう。各ノードには、親アクセサーと子列挙子があります。パフォーマンス上の理由から（可能であれば）Children列挙体の使用を避けたい。

ソート関数に渡す述部の擬似コード（ノード1がノード2より小さい場合、述部はブール値を返します）。

Answer 1

その根。たとえば、ファイルシステムでは、ファイルのパスは次のようになります。c：\ directory \ file.txt（ "C："、 "directory"、および "file.txt"は親ノードです）

単純な文字列比較のように、述語はパスを単に比較する必要があります。パスは文字列である必要はありません。パス比較関数は、ルート要素を1つずつ比較して、ルート要素が異なるとすぐに戻ります。

結果の並べ替えは、深さ優先検索と同じです。

Answer 2

ノードに役立つ情報を保存する必要があるので、述語は接続されていないノードのペアから先行ノードを選択できます。

ここで私の試み（非常に賢いか、でも、動作していないかもしれない）です：、ノードについて

からのパスを返す関数を持っている：私は簡単な作業溶液を見つけ

import java.util.ArrayList; 
import java.util.Collections; 
import java.util.List; 

/** 
* 
*/ 
public class SortingTree { 

    private static class Node implements Comparable<Node> { 
     private final String data; 
     private Node p, l, r; 

     private int ordinal = 0; 

     public Node(String data) { 
      this.data = data; 
     } 

     public Node setLeft(Node n) { 
      n.ordinal = ordinal + 1; 
      if (ordinal == 0) 
       n.ordinal = 2; 
      else 
       n.ordinal = ordinal + 2; 
      n.p = this; 
      return n; 
     } 

     public Node setRight(Node n) { 
      if (ordinal == 0) 
       n.ordinal = 1; 
      else 
       n.ordinal = ordinal + 4; 
      n.p = this; 
      return n; 
     } 

     public String toString() { 
      return data; 
     } 


     public int compareTo(Node o) { 
      // check if one of args is root 
      if (p == null && o.p != null) return -1; 
      if (p != null && o.p == null) return 1; 
      if (p == null && o.p == null) return 0; 

      // check if one of args is left subtree, while other is right 
      if (ordinal % 2 == 0 && o.ordinal % 2 == 1) return -1; 
      if (ordinal % 2 == 1 && o.ordinal % 2 == 0) return 1; 

      // if ordinals are the same, first element is the one which parent have bigger ordinal 
      if (ordinal == o.ordinal) { 
       return o.p.ordinal - p.ordinal; 
      } 
      return ordinal - o.ordinal; 
     } 
    } 

    public static void main(String[] args) { 
     List<Node> nodes = new ArrayList<Node>(); 

     Node root = new Node("root"); nodes.add(root); 
     Node left = root.setLeft(new Node("A")); nodes.add(left); 
     Node leftLeft = left.setLeft(new Node("C")); nodes.add(leftLeft); nodes.add(leftLeft.setLeft(new Node("D"))); 
     nodes.add(left.setRight(new Node("E"))); 

     Node right = root.setRight(new Node("B")); nodes.add(right); 
     nodes.add(right.setLeft(new Node("F"))); nodes.add(right.setRight(new Node("G"))); 

     Collections.sort(nodes); 
     System.out.println(nodes); 
    } 
}