2

假设你有一个像这个或这个这样的通用 k-ary 树

在这里重复后者：

template <typename T>
struct TreeNode
{
  T* DATA ; // data of type T to be stored at this TreeNode

  vector< TreeNode<T>* > children ;

  void insert( T* newData ) ;

  // runs f on this and all children of this
  void preorder( function<void (T*)> f )
  {
    f( this->DATA ) ; // exec f on this
    for( int i = 0 ; i < children.size(); i++ )
      children[i]->preorder( f ) ; // exec f on each child
  }

} ;

template <typename T>
struct Tree
{
  TreeNode<T>* root;

  // TREE LEVEL functions
  void clear() { delete root ; root=0; }

  void insert( T* data ) { if(root)root->insert(data); } 
} ;

现在通常，您将前序和后序遍历作为递归成员函数，TreeNode如上所示。 但是假设您不想传递函数，您想从类外部访问树中的每个节点（即只给定一个Tree对象）。

你怎么能这样做？

4

2 回答 2

3

我将通过定义一个PreorderIterator维护它在遍历中的状态的类来解决这个问题。它将具有返回当前节点和在遍历中前进一步的方法。

如果树结构可能在迭代器的生命周期内发生变异，您将必须小心。也许这棵树可以保持一个修改计数；迭代器可以在开始时捕获计数并检查每次访问时的更改（如果找到则抛出异常）。

于 2013-03-05T22:08:20.920 回答
2

一种简单的方法是将树加载到列表中，然后在需要时遍历列表。该列表将只是一个指针列表，因此不会那么昂贵。为此，您将使用trie 遍历算法的修改版本：

void traverse(Node n){
  if(null == n) return;

  for( Node c: n.children){
    visit( c );
    traverse( c );
  }
}

您将使用visit来实际加载您的列表。所以像

List<Node> getListToIterate(Node n){
   List<Node> result = new ArrayList<Node>();
   traverse(n,resutl);
   return result;
}

void traverse(Node n, List list){
  if(null == n) return;

  for( Node c: n.children){
    list.add( c );
    traverse( c );
  }

}

此外，如果您决定，您可以将此算法包装在一个TreeIterator类中，该类将跟踪您在列表中的位置。

于 2013-03-06T00:29:48.433 回答