查找二叉搜索樹

第n個節點使用該引導程序：查找二叉搜索樹

template <class Comparable> 
const Comparable& AugmentedBinarySearchTree<Comparable>::NthElement(int n) 
{ 
    int *i = 0; 
    return NthElement(root, i, n)->element; 
}

你怎麼會發現在使用nodesVisited指針跟蹤節點查了BST的第n個節點？

template <class Comparable> 
BinaryNode<Comparable>* AugmentedBinarySearchTree<Comparable>:: 
NthElement(BinaryNode<Comparable> *t, int *nodesVisited, int n) const 
{ 

}

在BST每個節點都有一個指針left和right和稱爲element的template <class Comparable>的值。

來源

2015-10-26 m_callens

二叉樹中的「第N個節點」是什麼意思？這不取決於二叉樹是如何遍歷的？ – PaulMcKenzie

@PaulMcKenzie通過查找「第N個節點」，我的意思是插入樹中的第n個值，這是非常明顯的。 –

以任何您想要的順序遍歷樹（可能按順序）。爲每個節點增加'* nodesVisited'。當'* nodesVisited == n'時停止。 –

這聽起來像（你的評論），就像你正在尋找Boost的多指標容器（http://www.boost.org/doc/libs/1_59_0/libs/multi_index/doc/index.html）。您可以使用矢量和地圖視圖，並使用push_back插入矢量視圖，同時使用地圖視圖按鍵搜索。然後，您將使用矢量視圖來獲取第n個插入的元素。

來源

2015-10-26 17:48:09

查找二叉搜索樹

回答

相關問題