查找二叉樹中的所有子樹

我需要將二叉樹的所有子樹存儲到一個頂點列表數組中，其中列表數組中的每個列表都存儲根頂點和所有根的後代頂點）。遞歸遍歷可能是最好的（？）。查找二叉樹中的所有子樹

因此，如果我們有

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

查找二叉樹中的所有子樹

回答

相關問題