查找二叉树中的所有子树

我需要将二叉树的所有子树存储到一个顶点列表数组中，其中列表数组中的每个列表都存储根顶点和所有根的后代顶点）。递归遍历可能是最好的（？）。查找二叉树中的所有子树

因此，如果我们有

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

我需要生成一个ArrayList<ArrayList<Vertex>> subtreeList根顶点的在subtreelist索引存储的根和所有后代顶点。所以这就像subtreeList.get(rootvertex.index).add(root vertex and all its descendents)。

对不起的措辞，我觉得这很难阐明。帮助赞赏。

来源

2012-03-30 comp sci balla

嗯，这听起来像是一个“家庭作业”问题。你有没有考虑过将指针存储到树中分支的每个位置？ – MrGomez 2012-03-30 23:46:54

我试图编写一个迷人的论文，标题为[http://www.cs.cmu.edu/~bryant/pubdir/ieeetc86.pdf](布尔函数操作的基于图形的算法）的算法。简化算法将二元决策图减少为优化形式。 – 2012-03-31 00:08:13

让我知道这是行不通的。我个人会将它保存在一个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; 
    } 
}

来源

2012-03-31 03:59:11

如果你想检查现有的实现，总有jgrapht，我相信它是开源的。

来源

2012-03-31 04:11:39 Matt

查找二叉树中的所有子树

回答

相关问题