0

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

深さ優先探索を実行するときに見つけるのと同じ順序でノードを並べ替えたいと思います。

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

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

4

2 に答える 2

0

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

これが私の（あまり賢くないかもしれないし、あるいはうまくいかないかもしれない）試みです：

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);
    }
}
于 2011-01-26T18:47:30.783 に答える
0

私は簡単に機能する解決策を見つけました：

ノードの場合、ルートからのパスを返す関数があります。たとえば、ファイルシステムでは、ファイルのパスは次のようになります。c：\ directory \ file.txtここで、「C：」、「directory」、および「file.txt」は親ノードです。

述語は、単純な文字列比較と同様に、パスを一緒に比較する必要があります。パスは文字列である必要はありません。パス比較関数は、ルートから開始してパス要素を1つずつ比較し、パス要素が異なるとすぐに戻る必要があります。

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

于 2011-01-27T18:21:37.777 に答える