沒有指針的遞歸結構？（霍夫曼）

我所定義的二進制樹是這樣的：沒有指針的遞歸結構？（霍夫曼）

struct btree { 
    int x; 
    btree* left_child = nullptr; 
    btree* right_child = nullptr; 
};

然後，我有浮標（prob_distr）的矢量和我將每個浮動成葉和我把所有的葉子成一個優先級隊列（與一個自定義的排序功能，但這裏沒關係）。

auto comp = [] (btree &a, btree &b) -> bool { return a.x > b.x; }; 
priority_queue<btree, vector<btree>, decltype(comp)> q(comp); 

for(auto t: prob_distr) 
{ 
    btree leaf; 
    leaf.x = t; 
    q.push(leaf); 
}

對於Huffman算法，我然後循環所述優先級隊列中，直到它只有1個元件左：我走2個節點在頂部從隊列中，創建與這兩個節點作爲新的節點孩子們，我把這些新節點放入隊列中。

while(q.size() >= 2) 
{ 
    btree left = q.top(); q.pop(); 
    btree right = q.top(); q.pop(); 

    btree root; 
    root.x = left.x + right.x; 
    root.left_child = &left; 
    root.right_child = &right; 

    q.push(root); 
}

的問題是，我有一個指針到left和right二叉樹，並走出去while循環的時候，這些樹將被刪除。然後我有指針指向什麼。有沒有什麼辦法可以解決這個問題，例如，通過一個存儲子樹的結構而不僅僅是指針，或者通過將結點存儲在其他地方而沒有太複雜的結構？

來源

2017-02-20 Jeremy

有沒有辦法解決這個問題。不，你不能沒有指針的遞歸結構。你需要正確處理指針，這是一個很難的要求，這是沒有辦法的。 –

當'left'是局部變量時，指定'root.left_child =＆left'是錯誤的。你應該做一些像'btree * left = new btree（q.top（））'。然後，你可以分配'root.left_child = left'。 'right'也一樣。 –

您需要在這裏使用指針，因爲在編譯時必須知道結構的大小。如果你將struct本身作爲成員變量，則內存需求將遞歸地轉換爲無窮大。您需要動態分配內存new。分配給new的內存將被分配，直到通過使用delete明確釋放內存爲止。只要寫

root.left_child = new btree(left); 
root.right_child = new btree(right);

前面已經說了，你還需要使用delete釋放孩子們的記憶。注意不要複製未被刪除的子項，也不要刪除在其他地方仍在使用的子項。考慮使用智能指針。

來源

2017-02-20 10:27:13

也許還會說他爲什麼需要動態分配？ – Drax

@Drax感謝您的評論。回答編輯。 –

這個答案會受益於智能指針。你不需要使用'delete'。這也將消除指定的風險。 – MSalters

沒有指針的遞歸結構？ （霍夫曼）

回答

相關問題

沒有指針的遞歸結構？（霍夫曼）