0

Java で二分木を実装する必要があります。右のノードの値は、親ノードの親と親を入力として受け取る function1() で計算され、左のノードの値は、親ノードを入力として。(最初の 2 つの子ノードについては、親と親ノードの値の親が事前に決定されます) ノードの 1 つがプログラムが探している値を持つまで、ノードはそれぞれの関数の戻り値で満たされます。関数がある時点で目的の値を生成する場合、そのノードへのパス、つまり関数が目的の値を生成した順序を出力する必要があります。指定された関数で値を取得できない場合は、「false」を出力します。

このアルゴリズムを実装する最良の方法を教えてください。

編集：次のように仮定しましょう：1. function1は：

int function1(p_node.value, p_node.p_node.value)
{ `return 5*p_node.value+6*p_node.p_node.value;}

2: function2 は:

int function2(p_node.value){
return 5*p_node;}

それで、

node.right_node.value=function1(node.p_node.value, node.p_node.pnode.value)
if(node.right_node.value==desired_output) "print path_to_the_node"
node.left_node.value=function2(node.p_node.value);
if(node.left_node.value==desired_output) "print path_to_the_node"
4

1 に答える 1

1

幅優先検索。これはサンプルです:

void findPath(Node secondChildNode, int desiredOutput){
    Node n = breadthFirstSearch(secondChildNode, desiredOutput);
    if(n == null)
        System.out.println("false");
    else{
        ArrayList<Node> list = new ArrayList<>();
        while(n != null){
            list.add(n);
            n = n.pNode;
        }
        for(int i = list.size() - 1; i >= 0; i--)
            System.out.println(list.get(i).value);
    }
}
Node breadthFirstSearch(Node secondChildNode, int desiredOutput){
    if(!secondChildNode.isPossible())
        return null;
    Queue<Node> q = new LinkedList<Node>();
    q.add(secondChildNode);
    Node t;
    while((t = q.poll()) != null){
        if(t.value == desiredOutput)
            return t;
        Node left = t.createLeftChild();
        if(left.isPossible(desiredOutput))
            q.add(left);
        Node right = t.createRightChild();
        if(right.isPossible(desiredOutput))
            q.add(right);
    }
    return null;
}

を実装する必要がありますNode。これは簡単で簡単な作業です。

class Node{
    Node pNode;
    int value;
    Node(Node pNode, int value){/* ... */}
    Node createLeftChild(){/* ... */}
    Node createRightChild(){/* ... */}
    boolean isPossible(int desiredOutput){
        return value <= desiredOutput;
    }
    /* ...... */
}

function1()これで、との定義がわかりfunction2()ました。desiredOutputが のサブツリーにある場合node、node.value <= desiredOutput. そうしないと、そのサブツリーの値がどんどん大きくなり、ある日、そのサブツリーの値がなくなり<= desiredOutputます。(ルートの値が正であると仮定します)

于 2013-05-23T14:19:04.277 に答える