將二叉樹轉換爲排序數組

繼我以前的question之後，我現在想將二叉樹的值放入排序數組中。將二叉樹轉換爲排序數組

所以，首先我用我的numOfNodeswn函數，計算在我的樹節點的總和，

我根據這個函數的結果創建了一個數組，我開始想，而不是定位最低樹的價值和使得不那麼容易繼任者 功能，我可以簡單地利用這種樹的效用，並作出一種Inorder過程，在它過程中，我可以把正確的值放入我的數組。

我的主要問題是控制變量我 - 這是根據它的指數，我會確切知道在哪裏把正確的值。

（頭是樹的頭）

這是我寫到目前爲止：

public double[] toDoubleArray() { 
    double[] arr = new double[numOfNodeswn(header)]; 
    int i=0; 
    return putvalues(arr, i, header); 
    } 



private double[] putvalues(double[] arr, int i, RBNode t) { 

    if (t!=null){ 
     putvalues (arr, i, t.left); 
     arr[i]=t.value; 
     i++; 
     putvalues (arr, i, t.right);  
} 
    return arr; 

}

來源

2011-04-23 Unknown user

我認爲你需要在二叉樹做一個深度的第一次迭代。將每個條目加載到樹中，並隨着時間增加索引。結果應該是一個排序數組。

來源

2011-04-23 13:50:49 duffymo

謝謝你的評論。通過深入第一次迭代並加載樹，你是什麼意思？通過給定一個二叉樹，我需要做到這一點。你是否建議我在創建樹的過程中創建數組？如果是這樣，我將如何控制數組大小？我沒有關於樹的大小的預先信息。 – 2011-04-23 13:56:59

不，我要說的是，如果你有一棵二叉樹，並且你先深入樹的第一遍，那麼你會得到這些元素的升序。打印出來，看看是否如此。如果是，那麼您可以看到如何將加載替換爲數組以便進行打印操作以獲得所需的結果。您可以輕鬆獲取有關樹中有多少個節點的信息。如果你不把它作爲二叉樹類中的成員變量來維護，那麼先進行深度優先迭代，然後總結出你的計數。 – duffymo 2011-04-23 14:00:03

這正是我想要做的，我的遞歸函數putvalues是去最左邊的節點，但不是打印它，我想把它放到數組中。如果你改變這兩行arr [i] = t.value; i ++; 在打印命令中，您將按照我的意願以排序的方式打印樹，並且我知道我可以簡單地獲取有關節點數量的信息，我做到了。我的問題正是如何控制數組的入口。 – 2011-04-23 14:07:08

對樹進行有序遍歷是正確的。也許不是返回arr，你應該返回一個整數，對應於數組中的第一個打開的點。這似乎是一項家庭作業，所以我不想放棄太多。

來源

2011-04-23 13:57:56

有沒有什麼簡短的方法知道給定數組中的下一個avilable點是什麼，我可以在每次迭代時做一個循環，但我相信有更簡單的方法，不是嗎？ – 2011-04-23 15:47:09

在基本情況下，您有一個葉節點（它將數組擴展一個）。所以，如果你傳入'next_spot'作爲參數，它只會返回'next_spot + 1'。在紙上玩一分鐘，遞歸情況應該很清楚。 – 2011-04-23 18:25:29

將二叉樹轉換爲排序數組

回答

相關問題