1

我需要遍历二叉树，跳过满足条件的任何节点的子节点。

这实现了树引导的聚类方法；当子树的叶子共同满足条件时，它们被认为是一个簇。

似乎开始的地方是预购遍历，但我不确定如何修改算法以跳过当前节点的所有子节点。

更新

除了以下两个（正确）答案之外，还可以使用以下 Java 库：

  • MyArch TreeIter - 通用（带有适配器类）树遍历，带有子跳过和动态最大遍历深度
  • Phylosoft ForestergetAllExternalDescendants - 带有Newick-to-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);
    }
}

第二部分：“......当子树的叶子集体满足条件时，它们被认为是一个簇......”很难。您需要检查节点的所有叶子以查看它们是否满足跳过条件。

于 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 回答