1

条件が満たされたノードの子をスキップして、バイナリ ツリーをトラバースする必要があります。

これは、ツリー ガイド クラスタリング アプローチを実装します。サブツリーの葉は、集合的に条件を満たしている場合にクラスターと見なされます。

開始する場所は事前注文トラバーサルのようですが、現在のノードのすべての子をスキップするようにアルゴリズムを変更する方法がわかりません。

アップデート

以下の 2 つの (正しい) 回答に加えて、次の Java ライブラリを使用できます。

  • MyArch TreeIter - 子のスキップと動的最大トラバーサル深度を備えた汎用 (アダプター クラスを使用) ツリー トラバーサル
  • Phylosoft ForestergetAllExternalDescendants - Newick から XML へのコンバーターを使用したツリー実装
4

2 に答える 2

1

最初の部分は簡単です:

class Tree {
    Tree(int data) {
        this.data = data;
    }
    Tree left, right;
    Object object;
    int data;
}
public class Main {
    static void myPreorder(Tree tree) {
        if (tree == null) return;
        if (tree.data > 2) {
            System.out.println("skipping " + tree.data);
            return;
        }
        System.out.println("visiting " + tree.data);
        myPreorder(tree.left);
        myPreorder(tree.right);
    }
    public static void main(String[] args) {
        Tree root = new Tree(1);
        root.left = new Tree(2);
        root.right = new Tree(3);
        root.right.left = new Tree(4);
        root.right.right = new Tree(5);
        myPreorder(root);
    }
}

2 番目の部分: 「 ... サブツリーの葉は、集合的に条件を満たしている場合にクラスターと見なされます。 ...」 は難しいです。ノードのすべてのリーフを調べて、スキップ条件を満たしていることを確認する必要があります。

于 2011-10-30T20:33:29.567 に答える
1

すべての子をスキップすることで、直系の子孫だけでなく、そのサブツリー全体を意味する場合は、次のことができます。

public void traverse(Node n){
    if (n==null)
        return;
    doSomethingWith(n);
    if (!conditionIsMet(n)){
        traverse(n.left);
        traverse(n.right);
    }
}
于 2011-10-30T20:34:02.460 に答える