Построение бинарного дерева путем применения функций к родителю

Question

У меня есть номер «X».У меня есть две функции F (X) и G (X).Теперь я хочу построить двоичное дерево с X в качестве родительского узла и f (X) в качестве левого дочернего элемента, а g (X) в качестве правого дочернего элемента и продолжить этот процесс на всех дочерних узлах и завершить работу, если я найду элемент, равныйк X в обоих дочерних поддеревьях.Как я могу это реализовать?

Answer 1

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

public boolean myFunc(int x){
    // BFS on left subtree ///////////////////////////////////
    boolean ltreeContainsX = false;
    int dx = f(x); // f should be defined somewhere
    if(dx == x){
        ltreeContainsX = true;
    }else{
        ArrayDeque<Integer> q = new ArrayDeque<Integer>();
    q.push(dx);
    while(q.size()!=0){
        int val = q.pop();
        int fval = f(val);
        q.push(fval);
        if(fval == x){
            lTreeContainsX = true;
            break;
        }
        int gval = g(val);
        q.push(gval);
        if(gval == x){
            lTreeContainsX = true;
            break;
        }
    }
    }
    // BFS on right subtree ///////////////////////////////////
    // ... do the same as the above code snippet, but this time,
    // you will push g(x) to an empty queue first and then proceed
    // find the boolean value called rtreeContainsX

    return ltreeContainsX && rtreeContainsX;
}