Пропускать узлы при обходе бинарного дерева

Question

Мне нужно пройти через двоичное дерево, пропустив дочерние элементы любого узла, для которого выполняется условие.

Это реализует подход с кластеризацией по дереву; листья поддерева считаются кластером, когда они все вместе удовлетворяют условию.

Похоже, что для начала нужно пройти предварительный заказ, но я не уверен, как изменить алгоритм, чтобы пропустить все дочерние элементы текущего узла.

Обновление

В дополнение к двум (правильным) ответам ниже можно использовать следующие библиотеки Java:

• MyArch TreeIter - Общий (с классом адаптера) обход дерева, с пропуском дочернего элемента и динамической максимальной глубиной обхода
• Phylosoft Forester - реализация дерева с getAllExternalDescendants и конвертером Newick-to-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);
    }
}

вторая часть: «... листья поддерева считаются кластером, когда они в совокупности удовлетворяют условию ...» трудно. вам нужно будет проверить все листья узла, чтобы убедиться, что они удовлетворяют условию пропуска.