0

我需要在java中实现一棵二叉树，其中右节点的值是用function1（）计算的，它以父节点的父节点和父节点作为输入，左节点的值是用function2（）计算的，它采用父节点作为输入。（对于前两个子节点，父节点的值和父节点的值是预先确定的）节点被填充各自函数的返回值，直到其中一个节点具有程序正在寻找的值。如果函数在某个点产生期望值，我们需要打印到该节点的路径，即函数产生期望值的顺序。如果使用给定函数无法获得该值，则我们打印出“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：函数2是：

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()and的定义function2()。如果desiredOutput在 的子树中node，则node.value <= desiredOutput。否则，它的子树的价值会越来越大，有一天它的子树没有价值了<= desiredOutput。（假设 root 的值为正）

于 2013-05-23T14:19:04.277 回答