n 개의 노드를 가진 전체 이진 트리에서 가능한 모든 토폴로지 생성하기

Question

정확하게 n + 1 개의 리프 노드와 n 개의 내부 노드가 있어야하는 전체 이진 트리의 가능한 토폴로지를 모두 만들고 싶습니다.

재귀를 사용하여 트리를 만들고 트리는 이진 검색 트리 나 BST가 아닌 단순한 이진 트리 여야합니다.

이 작업을 위해 알고리즘을 제안하는 것이 좋습니다.

예제 : 리프 노드 4 개와 내부 노드 3 개가있는입니다.

 N     N     N 
    /\    /\     /\ 
    N N    N N    N N 
    /\ /\    /\      /\ 
N N N N   N N     N N 
        /\      /\ 
        N N      N N 

추신 : 사람이 thread에 coproc에 의해 제안 트리 생성 알고리즘을 정교하게 할 수 있다면 simlar thread .IT 도움이 될 것입니다.

미리 감사드립니다.

Answer 1

다음은 주어진 n에 대한 모든 가능성 토폴로지를 생성하는 코드입니다. 전체 이진 트리의 노드 (내부 + 리프 노드)의 총 수는 홀수입니다.

트리가 전체 이진 트리 인 경우 왼쪽 및 오른쪽 하위 트리도 전체 이진 트리입니다. 즉, 좌우 하위 트리 모두 노드 수가 홀수입니다. 오른쪽에 왼쪽에 1 개 노드, 1 뿌리, N-2 :

은 주어진 N의 경우, 우리는이

첫 번째 반복과 같은 완전 이진 트리의 모든 조합을 생성합니다.
두 번째 반복 : 왼쪽에 3 개 노드, 오른쪽에 1 개 루트, n-4 개.
세 번째 반복 : 왼쪽에 5 개의 노드, 오른쪽에 1 개의 루트, n-6. .
.
.
마지막 반복 : n-2 왼쪽 노드, 1 근음, 오른쪽 1 노드

반복 할 때마다 가능한 모든 왼쪽 나무와 오른쪽 나무를 찾습니다. L 전체 나무 왼쪽에 가능하면, R 전체 나무 오른쪽에 가능 - http://ideone.com/Wz2Jhm

- 다음 나무의 총 수는 L의 *의 R이

public void createAllTopologies(int n){ 

    if(n%2 == 0) return; 

    Map<Integer, List<Node>> topologies = new HashMap<Integer, List<Node>>(); 

    topologies.put(1, new ArrayList<Node>()); 
    topologies.get(1).add(new Node(1)); 

    for(int i=3;i<=n;i+=2){ 

     List<Node> list = new ArrayList<Node>(); 

     for(int j=1;j<i;j+=2){ 
      List<Node> left = topologies.get(j); 
      List<Node> right = topologies.get(i-j-1); 
      list.addAll(generateAllCombinations(left,right)); 
     } 
     topologies.put(i, list); 
    } 

    List<Node> result = topologies.get(n); 

    for(int i=0;i<result.size();i++){ 
     printTree(result.get(i),0); 
     System.out.println("-----------------------------"); 
    } 

} 

private List<Node> generateAllCombinations(List<Node> left, List<Node> right) { 

    List<Node> list = new ArrayList<Node>(); 
    for(int i=0;i<left.size();i++){ 
     for(int j=0;j<right.size();j++){ 
      Node nNode = new Node(1); 
      nNode.left = left.get(i).clone(); 
      nNode.right = right.get(j).clone(); 
      list.add(nNode); 
     } 
    } 
    return list; 
} 

/* This prints tree from left to right fashion i.e 
     root at left, 
     leftNode at bottom, 
     rightNode at top 
*/ 

protected void printTree(Node nNode,int pos){ 
     if (nNode==null) { 
      for(int i=0;i<pos;i++) System.out.print("\t"); 
      System.out.println("*"); 
      return; 
     } 
     printTree(nNode.right,pos+1); 
     for(int i=0;i<pos;i++) System.out.print("\t"); 
     System.out.println(nNode.data); 
     printTree(nNode.left,pos+1); 

} 

여기에 코드를 완료하는 데 참조하시기 바랍니다있다