이진 트리에서 모든 하위 트리 찾기

Question

이진 트리의 모든 하위 트리를 정점 목록으로 저장해야합니다. 목록 배열의 각 목록에는 루트 정점과 루트의 모든 자손 버텍스가 저장됩니다.). 재귀 순회가 가장 좋습니다 (?).

그래서 우리는

class Vertex { 
    int index; 
    Vertex left; 
    Vertex right; 
    Vertex (int index, Vertex left, Vertex right){...init vars....} 
} 

이 있다면 나는 subtreelist의 루트 정점의 인덱스 루트와 그 하위 정점을 모두 저장하는 ArrayList<ArrayList<Vertex>> subtreeList을 생성해야합니다. 그래서 그것은 subtreeList.get(rootvertex.index).add(root vertex and all its descendents)과 같을 것입니다.

가난한 표현에 대해 유감스럽게 생각합니다. 도움말 감사.

Answer 1

이것이 작동하지 않는지 알려주세요. 개인적으로 Hashtable에 보관할 것이지만 ArrayList에 대한 코드를 만들었습니다.

import java.util.ArrayList; 
import java.util.Hashtable; 

public class Main { 
    private static int index; 

    public static void main(String[] args) { 
     index = 0; 

     /* Create the tree recursively. */ 
     Vertex root = createVertex(4); 

     /* Create a hashtable version of the list you want. */ 
     Hashtable<Integer, ArrayList<Vertex>> map = new Hashtable<Integer, ArrayList<Vertex>>(); 
     fillList(root, map); 

     /* Find the max index. */ 
     int maxIndex = -1; 
     for (int index : map.keySet()) { 
      if (maxIndex < index) { 
       maxIndex = index; 
      } 
     } 

     /* Copy the items over from the hashtable. */ 
     ArrayList<ArrayList<Vertex>> list = new ArrayList<ArrayList<Vertex>>(
       maxIndex + 1); 
     for (int i = 0; i <= maxIndex; i++) { 
      if (map.containsKey(i)) { 
       list.add(map.get(i)); 
      } else { 
       list.add(null); 
      } 
     } 

     /* Print it out. */ 
     for (int i = 0; i < list.size(); i++) { 
      ArrayList<Vertex> descedants = list.get(i); 
      if (descedants != null) { 
       System.out.printf("%d :", i); 
       for (Vertex vertex : descedants) { 
        System.out.printf(" %d", vertex.getIndex()); 
       } 
       System.out.println(); 
      } 
     } 
    } 

    private static void fillList(Vertex vertex, 
      Hashtable<Integer, ArrayList<Vertex>> map) { 
     /* Create the descendants for the current vertex. */ 
     ArrayList<Vertex> descendants = new ArrayList<Vertex>(); 

     /* Add the current vertex to the descendants. */ 
     map.put(vertex.getIndex(), descendants); 
     descendants.add(vertex); 

     /* 
     * Now recursively call this on the left vertex and then, once that's 
     * done, add the left's descendants to this one's descendants. 
     */ 
     Vertex left = vertex.getLeft(); 
     if (left != null) { 
      fillList(left, map); 
      for (Vertex leftDescendant : map.get(left.getIndex())) { 
       descendants.add(leftDescendant); 
      } 
     } 

     /* Do the same with the right. */ 
     Vertex right = vertex.getRight(); 
     if (right != null) { 
      fillList(right, map); 
      for (Vertex rightDescendant : map.get(right.getIndex())) { 
       descendants.add(rightDescendant); 
      } 
     } 
    } 

    /* Creates a balanced binary tree recursively with depth i. */ 
    private static Vertex createVertex(int i) { 
     if (i > 0) { 
      index++; 
      return new Vertex(index, createVertex(i - 1), createVertex(i - 1)); 
     } 

     return null; 
    } 

} 

class Vertex { 

    private Vertex right; 
    private Vertex left; 
    private int index; 

    public Vertex(int index, Vertex left, Vertex right) { 
     this.index = index; 
     this.left = left; 
     this.right = right; 
    } 

    public int getIndex() { 
     return this.index; 
    } 

    public Vertex getLeft() { 
     return this.left; 
    } 

    public Vertex getRight() { 
     return this.right; 
    } 
} 

Answer 2

기존 구현을 검사하려면 항상 jgrapht가 있어야하며 이는 오픈 소스라고 생각합니다.