java - 用两个函数填充二叉树

Question

关闭。此题需要 details or clarity 。目前不接受答案。

---

想要改进这个问题吗？通过 editing this post 添加详细信息并澄清问题.

已关闭 9 年前。

Improve this question

我需要在java中实现一个二叉树，其中右节点的值使用function1()计算，该函数将父节点的父节点和父节点的父节点作为输入，左节点的值使用function2()计算它将父节点作为输入。 (对于前两个子节点，parent和parent的父节点值是预先确定的)这些节点填充有各自函数的返回值，直到其中一个节点具有程序正在查找的值。如果函数在某个时刻产生所需的值，我们需要打印到该节点的路径，即函数的哪个顺序产生所需的值。如果用给定的函数无法获得该值，那么我们打印出“false”

您能告诉我实现该算法的最佳方法吗？

编辑:让我们假设:1. 函数1是:

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"

Answer 1

Breadth-first search 。这是一个示例:

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 。 (假设root的值为正)