동등한 하위 트리

Question

두 개의 나무가 있습니다. 트리 노드는 다음과 같이 정의됩니다.

class Node{ 
    String treeId; 
    String type;  //Each node has type which has fixed value. For example, its color: RED, BLANK, GREEN 
    Set<Node> children; 
    String ref;  //The ref is a string and allowed value are "0", "1",..."10". The value is null if it is not leaf. 
}; 

리프의 경우, 자식 세트는 비어 있습니다.

두 개의 주어진 트리에 대해 동등한 substree를 식별하는 방법이 기존에 효율적인 작업이 있는지 궁금합니다. 등가는 다음과 같이 정의됩니다.

1) Both subtree leaves are setsets leaves of original tree. 
2) Both subtrees leaves have same ref value. 
3) for non-leaves node, the equivalent refers to both node have same type and equivalent children. 

감사합니다. 이 문제를 해결하는 Java 라이브러리가 있으면 더 좋을 것입니다.

---

입력은 두 개의 트리 루트이고 출력은 동등한 하위 트리의 루트 인 노드입니다. 나무의 높이는 100 ~ 500 개가 넘습니다.

---

내가 지금 한 것은 노드 클래스에 대한 새 필드를 추가 한 것입니다.

class Cache{ 
    Map<String, Set<String>> map = new LinkedHashMap<String, Set<Str>>(); 
} 

값이이 노드 ID의이 노드가 도달 할 수있는 참조 집합 인 동안 노드의 키입니다. 노드가 초기화되면 캐시가 시작됩니다.

isEquivalent 비교 단계에서 두 루트의 참조 집합간에 중첩이 있는지 확인하십시오. 없는 경우는 false를 리턴합니다.

이렇게하면 비교 공간을 줄일 수 있다고 생각합니다.

Answer 1

how to identify equivalent substree for two given tree.과 (과) 일치하지 않으므로 1) Both subtree leaves are leaves of original tree. 요구 사항에 대해 확실하지 않습니다. 그렇지 않으면 재귀 적 방법은 다른 두 조건을 처리 할 수 ​​있어야합니다. haveSameOriginalTree(r1, r2) 메서드는 이해할 수없는 첫 번째 조건을 충족시키기 위해 구현 될 수 있습니다. r1 및 r2은 동등성을 검사해야하는 두 개의 하위 트리의 근원입니다.

bool areEquivalent(Node r1, Node r2) 
{ 
    if(r1.children == null && r2.children == null) 
    { 
     return (haveSameOriginalTree(r1, r2) && (r1.ref == r2.ref)); 
    } 
    if((r1.children == null && r2.children != null) || (r1.children != null && r2.children == null)) 
    { 
     return false; 
    } 
    // if here then both must be non-leaf nodes 
    if(r1.type != r2.type) 
    { 
     return false; 
    } 
    if(r1.children.getCount() != r2.children.getCount()) // not sure of correct syntax for Java Sets 
    { 
     return false; 
    } 
    for(int i=0; i<r1.children.getCount(); i++) 
    { 
     if(!areEquivalent(r1.children[i], r2.children[i])) // again please correct the syntax for Sets 
     { 
      return false; 
     } 
    } 

    return true; 
} 

내 생각을 알려주세요.

업데이트 여기

는 상기 용액의 반복 된 버전이다. 함수의 호출 스택에 푸시되기보다는 힙에 할당 된 스택 데이터 구조를 사용하므로 재귀 적으로는 많이 다르지 않지만 여전히 우수합니다. 또한, 우리는 단지 Node (전체 객체를 복사하는 것이 아니라)에 대한 참조를 보유하기 때문에, 추가 메모리 오버 헤드 의 경우가 아니라면 이미 원본 트리를 메모리에로드하고 있습니다.

bool areEquivalent(Node r1, Node r2) 
{ 
    Stack<Node> s1 = new Stack<Node>(); 
    Stack<Node> s2 = new Stack<Node>(); 
    Node n1, n2; 

    s1.Push(r1); 
    s2.Push(r2); 
    while(true) // Need a better check 
    { 
     if(s1.getCount() != s2.getCount()) 
     { 
      return false; 
     } 
     if(s1.getCount() == 0) // if both stacks are empty then we've traversed both trees without failure. 
     { 
      return true; 
     } 
     n1 = s1.Pop(); 
     n2 = s2.Pop(); 
     if(!areEquivalentNodes(n1, n2)) 
     { 
      return false; 
     } 
     foreach(Node child in n1.children) 
     { 
      s1.Push(child); 
     } 
     foreach(Node child in n2.children) 
     { 
      s2.Push(child); 
     } 
    } 
} 

// only checks the two nodes are equivalent. their childrens' equivalence will be handled by other calls to this method. 
bool areEquivalentNodes(Node n1, Node n2) 
{ 
    if(n1.children.getCount() != n2.children.getCount()) 
    { 
     return false; 
    } 
    if(n1.children.getCount() == 0) // if both are leaf nodes... 
    { 
     if(n1.ref != n2.ref) 
     { 
      return false; 
     } 
    } 
    else // both are non-leaf 
    { 
     if(n1.type != n2.type) 
     { 
      return false; 
     } 
     // the condition that children of non-leaf nodes be equivalent will be covered by subsequent calls this method... 
    } 

    return true; 
} 

두 솔루션 모두 동일한 순서로 두 개의 해당 노드가 있다고 가정하십시오. children이 주문되지 않은 경우 위 코드를 호출하기 전에 정렬해야합니다.

더 나은지 알려주세요.