創建一個樹形數據結構 - 不同的方法

在通過的過程中，我問了很多關於樹形數據結構的問題，但似乎我沒有在C++中採用正確的方式。創建一個樹形數據結構 - 不同的方法

在我編寫數據結構的方式中，我無法想象如何擁有「結束」或「開始」迭代器。因此，我已經採取了將所有功能作爲成員方法的方法。而不是使用迭代器的標準方法&算法。

現在我的樹結構的目標是：1）儘可能快地將分支從一棵樹移動到另一棵樹。 2）每個分支應該是自己的一棵樹。並且在樹上執行的操作也應該能夠在分支上執行。

我所做的只是創建一個包含矢量的類。 - 矢量內部是這個類的其他對象。示例（我只發佈一個小例子，在這裏，因爲我現在面臨的最大問題是該類實在太大處理）：

template <typename ValTy> 
class Tree { 
private: 
    std::vector<std::unique_ptr<Tree> > subtrees; 
    ValTy value; 
};

正如你可以用這個看到我就可以拿東西出來的subtrees - 並將其用作樹或複製它。但是，由於頂級樹沒有關於有多少個子樹（或多少個級別）的說明，因此不可能聲明「結束迭代器」？而像std :: find（）這樣的算法不會遍歷整個樹（以及它的所有子樹）？

是否有可能利用這些算法可能，同時仍然維持簡單的「分支」結構？

來源

2012-01-17 paul23

您可以通過保留一堆子樹向量的迭代器來迭代這樣的樹。這種向量上的增量意味着最頂層子樹迭代器上的增量，如果最底層迭代器處於末端，則執行清理。

這個向量的end()迭代器只是空棧。

來源

2012-01-17 15:07:46 thiton

等一下，如果我理解正確，頂層有一個樹中每個節點的條目？（樹中的每個節點都是一個新的級別，它包含一個子樹向量，所以最高級別需要爲每個節點添加一個新的子樹 - 迭代器對）。我猜這個「有效」，但不是非常低效？ - 你（重新）移動分支需要迭代到頂層並修改它？ – paul23 2012-01-17 15:16:30

@ paul23：不，* iterator *在樹的每個級別的堆棧上都有一個元素。這需要O（log n）空間來迭代一棵樹，但如果樹中沒有父指針，則無法避免。 – thiton 2012-01-17 15:20:59

正如你所看到的，我可以從子樹中取出一些東西 - 並將它用作樹或複製它。然而，頂級級別樹沒有關於有多少個子樹（或多少個級別）的說明，因此不可能聲明「結束迭代器」？而像像std :: find（）這樣的算法不會遍歷整個樹（以及它的所有子樹）？

那麼這裏的問題更多的是一個概念問題。

我總是通過遞歸求解樹結構中的CRUD功能。遞歸併不需要知道子樹的數量，這是使O(log n)插入，查找和刪除的一件事情。

插入例如：

void insertNode(Node* &treeNode, Node *newNode) { 
    if (treeNode) treeNode = newNode; 
    else if (newNode->key < treeNode->key) insertNode(treeNode->left, newNode); 
    else insertNode(treeNode->right, newNode); 
}

如果你需要知道有多少水平上樹剛去左邊的孩子，直到NULL。您可以使用此知識輕鬆計算O(log n)算法來計算樹中子項的數量。

樹被設計用於遞歸訪問。如果你想要非遞歸訪問，也許樹不是你想要的？ - 這個結構會保持什麼數據，訪問頻率是多少？

來源

2012-01-17 15:22:43

創建一個樹形數據結構 - 不同的方法

回答

相關問題