將BST轉換爲數組

我已經找遍了，似乎無法找到任何幫助。對於一個學校項目我有一個BST樹，我必須將所有int從樹中放入一個int數組稱爲BSTarray。
這是我到目前爲止有：
將BST轉換爲數組

public int [] toBSTArray() { 
    int size = 20; 
    int [] BSTarray = new int [size]; 
    for(int i = 0; i <size; i++) { 
     makeArray(root); 
     BSTarray[i] = root.getValue(); 
} 

    return BSTarray; 
} 

//helper method called by toBSTArray 
public void makeArray(BinarySearchTreeNode node) { 
    if (node != null) { 
     makeArray(node.getLeft()); 
     makeArray(node.getRight()); 
     // System.out.print(node.getValue() + " "); 
    } 
}

我想應該這個方法要經過樹，並添加發現到在BSTarray不同的索引值，但所有它做的是將相同編號到數組中的所有索引中。我在做遞歸錯誤嗎？

來源

2012-12-13 Gcap

嘗試這種情況：

Integer[] values = extractValues(n).toArray(new Integer[] {});

與該方法的定義：

private static List<Integer> extractValues(Node n) { 
    List<Integer> result = new ArrayList<>(); 
    if (n.getLeft() != null) { 
     result.addAll(extractValues(n.getLeft())); 
    } 

    if (n.getRight() != null) { 
     result.addAll(extractValues(n.getRight())); 
    } 

    result.add(n.getValue()); 

    return result; 
}

我假定一個節點的結構是類似於你的。當然，如果你不以靜態方式使用它，那麼該方法不一定是靜態的。

由於列表轉換，此方法可能不是最有效的，但您不必擔心任何數組大小。如果你真的需要這個函數來返回一個數組，那麼只需將它包裝到另一個函數中，或者讓提出的函數返回一個數組（這將使得在每次返回之前將列表轉換爲數組是必要的）。

關於你的代碼，你遍歷i來填充整個數組（無論你從哪裏知道大小），但總是將該值設置爲根節點的值。這就是爲什麼你總是有相同的價值。你makeArray函數遞歸調用自己，但它不會做任何事情（即使你添加一個系統輸出語句;））

更新：

而對於不使用名單的限制，這裏是另一個版本只使用陣列：

int size = 20; 
int[] results = new int[size]; 
extractValues(n, results, 0);

與方法定義：

private static int extractValues(Node n, int[] results, int index) { 
    if (n.getLeft() != null) { 
     index = extractValues(n.getLeft(), results, index); 
    } 

    if (n.getRight() != null) { 
     index = extractValues(n.getRight(), results, index); 
    } 

    results[index] = n.getValue(); 

    return index + 1; 
}

筆記，那麼結果將在results中。大小必須假定爲大於節點數量，或者必須先通過遍歷樹來計算大小。

來源

2012-12-13 23:24:27

我們不允許使用「列表「 – Gcap

我添加了一個不使用列表的版本，請參閱我的更新。 –

謝謝！我們必須從驅動類中調用它，所以我再次用extractValues（n，results，0）創建了toBSTArray方法;並且我返回數組「結果」，但它最終會打印到控制檯，如下所示：[I @ 66780515 – Gcap

您可以遍歷將元素添加到數組中的樹。例如，使用前序遍歷你有這樣的事情：

void preOrder (BSTNode root){ 

    if(root == null) 
    return; 

    array.add(root.getValue); 

    preOrder(root.leftNode()); 
    preOrder(root.rightNode()); 

}

來源

2012-12-13 23:44:48 Rafael

如何：（您的遞歸不會對數組進行任何更改）

public int [] toBSTArray() { 
    int size = 20; //ASSUMING THIS IS LESS THAN OR EQUAL TO NUMBER OF NODES IN THE TREE 
    int [] BSTarray = new int [size]; 
    makeArray(root, 0, BSTarray); 
    return BSTarray; 
} 

//helper method called by toBSTArray 
public void makeArray(BinarySearchTreeNode node, int i, int [] BSTarray) { 
    if (node != null) { 
     BSTarray[i] = root.getValue(); 
     makeArray(node.getLeft(), 2*i+1, BSTarray); 
     makeArray(node.getRight(), 2*i+2, BSTarray); 
    } 
}

來源

2012-12-13 23:53:08 CEGRD

我收到了makeArray的方法簽名的編譯錯誤，這是說我需要一個標識符後BSTarray – Gcap

將BST轉換爲數組

回答

相關問題