二叉树遍历时跳过节点

Question

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

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

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

更新

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

• MyArch TreeIter - 通用（带有适配器类）树遍历，具有子跳过和动态最大遍历深度
• Phylosoft Forester - 使用 getAllExternalDescendants 和 Newick 到 XML 转换器的树实现

Answer 1

如果跳过所有子节点不仅意味着直系后代，还意味着它们的整个子树，则可以执行以下操作：

public void traverse(Node n){
    if (n==null)
        return;
    doSomethingWith(n);
    if (!conditionIsMet(n)){
        traverse(n.left);
        traverse(n.right);
    }
}

Answer 2

第一部分很简单：

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);
    }
}

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