最快遍历任意深度树的删除方法？

对于我自己的练习，我正在编写一个XML解析器。为了填充树，我使用正常的std::stack，并将当前节点设置为最后一个顶级节点的子节点（应该是深度优先？）。所以我现在做同样的删除节点，我想知道是否有更快的方法。
删除当前代码：最快遍历任意深度树的删除方法？

struct XmlNode{ 
    // ignore the rest of the node implementation for now 
    std::vector<XmlNode*> children_; 
}; 
XmlNode* root_ = new XmlNode; 

// fill root_ with child nodes... 
// and then those nodes with child nodes and so fort... 

std::stack<XmlNode*> nodes_; 
nodes_.push(root_); 
while(!nodes_.empty()){ 
    XmlNode* node = nodes_.top(); 
    if(node->children_.size() > 0){ 
     nodes_.push(node->children_.back()); 
     node->children_.pop_back(); 
    }else{ 
     delete nodes_.top(); 
     nodes_.pop(); 
    } 
}

工作完全正常，但它看起来有点慢。那么有没有更快/更好/更常见的方法来做到这一点？

来源

2011-02-16 Xeo

“有点看起来很慢”不是一个算法的性能可接受的描述。你分析了代码，看看它有多快？你有硬数据吗？ – 2011-02-16 02:50:31

不要走出自己的方式做反复什么可以递归轻松完成，除非你能证明是递归版本是不够的（如堆栈溢出）或更慢（这将不会发生除非你开始溢出堆栈，迫使操作系统扩展它或使你崩溃）。

换句话说，一般来说，对线性结构使用迭代，对树结构使用递归。

Compared to recursion，迭代法在我的机器上慢了大约3倍。如果您可以确定您的XML深度不会超过几百个嵌套（我在真实世界的XML文档中从未见过），那么递归不会成为问题。

迭代是人为的;递归，神圣。 :)

来源

2011-02-16 06:10:36 Mehrdad

最快遍历任意深度树的删除方法？

回答

相关问题