두 함수로 이진 트리 채우기

Question

Java에서 이진 트리를 구현해야합니다. 오른쪽 노드의 값은 부모 노드의 부모 및 부모를 입력으로 사용하고 function1()은 왼쪽 노드의 값 노드는 부모 노드를 입력으로 사용하는 function2()로 계산됩니다. (첫 번째 두 개의 자식 노드에 대해 부모 노드 값의 부모 및 부모는 미리 결정됩니다.) 노드 중 하나가 프로그램에서 찾고자하는 값을 가질 때까지 노드는 해당 함수의 반환 값으로 채워집니다. 함수가 어떤 지점에서 원하는 값을 생성한다면, 그 노드에 대한 경로, 즉 원하는 순서로 함수의 순서가 원하는 값을 생성해야합니다. 주어진 함수로 값을 얻지 못하면 "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합니다. 당신은 쉽고 간단한 작업입니다 Node를 구현해야

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; 
} 

:이 샘플입니다.

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입니다. (루트 값이 양수라고 가정하십시오)