c++ - 无递归的面向数据的树遍历

Question

我有一个这样的树结构：一个模型有一个根节点，每个节点有任意数量的子节点和任意数量的网格。

在我的应用程序中，很多时间都花在遍历这棵树并进行诸如视图截头体剔除和矩阵乘法之类的计算上。目前，它是幼稚的实现，其中每个节点都有子节点和网格的向量，并且树是递归遍历的。这是非常缓慢的。

我一直在研究面向数据的设计，我喜欢它对缓存非常友好的想法。我一直在想这样的事情：

struct Mesh
{
    // misc data
    MeshID mMeshID;
}

// probably needs more information?
struct Node
{
    // begin and end index into Models 'mNodes'
    uint32_t mChildrenBegin;
    uint32_t mChildrenEnd;

    // as above but for meshes
    uint32_t mMeshesBegin;
    uint32_t mMeshesEnd;
}

struct Model
{
    std::vector<Node> mNodes;
    std::vector<Mesh> mMeshes;
}

现在我需要遍历树以获得可见网格的列表。在每个节点上，我必须检查该节点是否可见。以下分支：

节点可见。它下面的所有子节点和网格也是可见的。不要深入这个分支。检查相同深度的其他节点。
节点不可见。此节点或其下方的子节点或网格不可见。不要深入这个分支。检查相同深度的其他节点。
该节点是部分可见的。一些节点和/或一些网格是可见的。必须深入层次结构。

树是静态的。一旦模型被加载到应用程序中，树就永远不会改变。所以不知何故，我必须能够使用这些信息来获得一个有效的结构。

我很困惑如何解决这个问题。

几个问题；

如何在内存中布局节点？是第一个索引的根节点吗？其他节点是根据深度添加的吗？
如何在不使用递归的情况下迭代树？我不想访问每个节点，除非我真的必须这样做。例如，如果 depth=2 的节点不可见，则不应测试其所有网格和子节点（及其网格），而应完全跳过。

score 5 · Accepted Answer

您可以按深度优先遍历顺序将树表示为内存中的单个数组

struct Node {
    ... node data ...
    int next;
};

std::vector<Node> nodes;

next字段保持下一个节点的索引在相同或更高级别；节点的第一个子节点没有明确说明，因为它是序列中当前节点之后的节点（除非 next 也指向它；在这种情况下，当前节点没有子节点）。例如在树中：

在此处输入图像描述

红色箭头代表next指向的地方。

例如用于渲染的遍历变为：

void check(int ix) {
    switch(nodes[ix].visibility()) {
        case VISIBLE:
            // Draw whole subtree, no more checking needed
            for (int i=ix,e=nodes[ix].next; i!=e; i++) {
                nodes[i].draw();
            }
            break;
        case PARTIALLY_VISIBLE:
            nodes[ix].draw();
            for (int c=ix+1, e=nodes[ix].next; c!=e; c=nodes[c].next) {
                check(c);
            }
            break;
    }
}

相同的代码也可以通过保留显式堆栈转换为非递归代码（不知道为什么这是一个好主意，除非节点操作和检查非常快或树非常深）。

score 2 · Accepted Answer

短版：改用 6502 的预购答案。我将在下面留下我之前的答案，因为它仍然有一些有趣的代码和注释。

以半预订方式布置您的存储阵列。即：sentinel end node、roots、first root的children、first root的first child的children、first root的first grandchild的children，以此类推。然后使用递归半前序遍历遍历树，该遍历将直接祖先及其兄弟姐妹的索引信息的副本保留在堆栈上。这样，您的遍历将从左到右扫描存储阵列，无需回溯。您不需要使用递归访问所有节点，并且您所做的任何跳过子树只会使您的扫描在存储阵列中向前跳转。

model.semiPreOrderTraversalRecur(model.getEnd());  // traverse the whole tree

...

// NOTE: pass prnt by *COPY* -- break Node into index portion and app. data portion; we only need the index portions here

void Model::semiPreOrderTraversalRecur(Node prnt)
{  
  Node children[prnt.mChildrenEnd - prnt.mChildrenBegin];  // just index info
  uint32_t i;

  // visit children of prnt; determine visibility etc.

  for (i = prnt.mChildrenBegin; i < prnt.mChildrenEnd; ++i)
  {
    cout << "Visiting " << mNodes[i].mVal << endl;
    mNodes[i].mInvisible = false;  // TODO: determine based on culling, etc.
    children[i - prnt.mChildrenBegin] = mNodes[i];  // just index info
  }

  // recurse on children as necessary

  for (i = 0; i < prnt.mChildrenEnd - prnt.mChildrenBegin; ++i)
    if (!children[i].mInvisible && children[i].mChildrenBegin != children[i].mChildrenEnd)
      semiPreOrderTraversalRecur(children[i]);
}

长版本（其中一些已被排除）：我认为您可以通过向 Node 结构添加更多信息来实现您想要的：节点的父节点的索引和当前节点的索引。（后者可能不是绝对必要的，因为它可能来自指向节点的指针和节点存储向量。）

这应该为您提供足够的上下文信息，以便根据树中的任何节点的需要轻松地将“向上”、“向下”或“侧向”移动到同级。要“向上”移动，您只需转到父索引。要向下移动，请转到任何一个子索引。要将“横向”移动到兄弟姐妹，您只需增加/减少当前节点的索引（在检查您不是父母的最后一个/第一个孩子之后）。

您可能需要考虑组合 Node 和 Mesh 结构，以便可以将它们连续存储在一个向量中。对鹅有益的缓存性能通常对鹅有益。由于您的 Mesh 存储在另一个向量中，它们在内存中可能与它们的节点兄弟姐妹相距甚远，并且在遍历中间访问它们将对缓存施加更大的压力。当然，如果你的 Mesh 比你的 Node 有更多的数据（反之亦然），或者你不需要在遍历过程中访问 Mesh，那么这可能不是一个好的选择，因为它会浪费内存。此外，您的网格可能不需要所有树索引，因为它们是终端节点，并且在您访问节点的子节点时可能是特殊情况。根据具体情况，您最初单独存储 Mesh 的建议可能会更好。

在下面的代码中，我结合了您的节点和网格结构并将它们存储在一个向量中。

#include <cstdint>
#include <iostream>
#include <vector>
#include <string>
#include <chrono>
#include <thread>

using namespace std;

struct Node
{
  uint32_t mParentIndex;    // index of parent Node in Model
  uint32_t mIndex;          // index of this Node in Model (may be possible to derive this from Node pointer and Model's vector rather than storing it)

  uint32_t mChildrenBegin;  // begin and end index of children Node in Model
  uint32_t mChildrenEnd;

  bool     mInvisible;      // used during semiPreOrderTraversal to remember no need to traverse subtree rooted at this Node

  int      mVal;            // dummy data for debugging
};

struct Model
{
  vector<Node> mNodes;  // preferably private, but your call

  Model(istream *in = NULL);

  Node *getEnd(void) { return &mNodes[0]; }  // sentinel end node that always exists and has itself as parent
  Node *getRoot(void) { return getChild(getEnd()); }

  Node *getParent(Node *curr) { return &mNodes[curr->mParentIndex]; }  // always safe to call; returns end as sentinel
  Node *getNextSibling(Node *curr) { Node *prnt = getParent(curr); return (curr->mIndex && curr->mIndex + 1 < prnt->mChildrenEnd ? &mNodes[curr->mIndex + 1] : NULL); }
  Node *getPrevSibling(Node *curr) { Node *prnt = getParent(curr); return (curr->mIndex > prnt->mChildrenBegin ? &mNodes[curr->mIndex - 1] : NULL); }
  Node *getChild(Node *curr, unsigned nth_child = 0) { unsigned index = curr->mChildrenBegin + nth_child; return (index < curr->mChildrenEnd ? &mNodes[index] : NULL); }

  void semiPreOrderTraversal(void);
  void semiPreOrderTraversalRecur(Node prnt);

private:
  int  buildFromStreamRecur(Node *curr, int val, istream &in);
};

void Model::semiPreOrderTraversal(void)
{
  Node *curr = getRoot();
  Node *next;

  cout << "Beginning Semi-Pre-Order traversal of tree!" << endl;

  if (NULL == curr)
    goto DONE;

  while (1)
  {
    // TODO: visit curr; determine and record mInvisible in curr

    cout << "Visiting " << curr->mVal << endl;
    curr->mInvisible = false;

    // try to move to sibling

    if (NULL == (next = getNextSibling(curr)))
    {
      // try to move to children of siblings

      curr = getChild(getParent(curr));  // move back to oldest sibling

      cout << "No more siblings to visit! Try to visit their children. Rewinding to oldest sibling " << curr->mVal << endl;

      while (curr->mInvisible || NULL == (next = getChild(curr)))
      {
        cout << "No children to visit of " << curr->mVal << endl;

        // shouldn't visit curr's children or it has no children
        // try to move to sibling

        if (NULL == (next = getNextSibling(curr)))  
        {
          cout << "Reached end of siblings again -> completed traversal of subtree rooted by parent " << getParent(curr)->mVal << endl;
          // ascend while we can't find a uncle to check for children to visit

          do {
            if (getEnd() == (curr = getParent(curr)))  
              goto DONE;  // got back to end -> traversal complete

            cout << "Moved back up to " << curr->mVal << endl;

          } while (NULL == (next = getNextSibling(curr)));

          cout << "Found a great^Nth uncle (" << next->mVal << ") to check for children to visit!" << endl;
        }
        // else check sibling for children to visit

        curr = next;
        cout << "Trying to visit children of " << curr->mVal << endl;
      }
      // visit children of curr

      cout << "Will visit children of " << curr->mVal << endl;
    }
    else
      cout << "Will visit sibling of " << curr->mVal << endl;

    curr = next;
  }

DONE:
  cout << "Finished Semi-Pre-Order traversal of tree!" << endl;
}

void Model::semiPreOrderTraversalRecur(Node prnt)
{  
  Node children[prnt.mChildrenEnd - prnt.mChildrenBegin];  // just index info
  uint32_t i;

  // visit children of prnt; determine visibility etc.

  for (i = prnt.mChildrenBegin; i < prnt.mChildrenEnd; ++i)
  {
    cout << "Visiting " << mNodes[i].mVal << endl;
    mNodes[i].mInvisible = false;
    children[i - prnt.mChildrenBegin] = mNodes[i];  // just index info
  }

  // recurse on children as necessary

  for (i = 0; i < prnt.mChildrenEnd - prnt.mChildrenBegin; ++i)
    if (!children[i].mInvisible && children[i].mChildrenBegin != children[i].mChildrenEnd)
      semiPreOrderTraversalRecur(children[i]);
}

Model::Model(istream *in)
{
  Node dmy, *end;

  mNodes.push_back(dmy);  // create sentinel end node

  end = getEnd();
  end->mParentIndex   = 0;
  end->mIndex         = 0;
  end->mChildrenBegin = 1;
  end->mChildrenEnd   = 1;
  end->mVal           = -1;  

  if (in)
    buildFromStreamRecur(getEnd(), 0, *in);
}

int Model::buildFromStreamRecur(Node *curr, int val, istream &in)
{
  uint32_t numChildren, i, currInd = curr->mIndex;

  // read in how many children curr will have

  in >> numChildren;

  // allocate children in mNodes and set curr's children references
  // NOTE: protect against reallocations of mNodes

  curr->mChildrenBegin = mNodes.size();

  for (i = 0; i < numChildren; ++i)
  {
    Node node;

    node.mParentIndex   = currInd;
    node.mIndex         = mNodes.size();
    node.mChildrenBegin = (uint32_t) -1;
    node.mChildrenEnd   = (uint32_t) -1;
    node.mVal           = val++;

    mNodes.push_back(node);
  }

  curr = &mNodes[currInd];
  curr->mChildrenEnd = mNodes.size();

  cout << "Node " << curr->mVal << " is complete! mParentIndex = " << curr->mParentIndex << "; mIndex = " << curr->mIndex
       << "; mChildrenBegin = " << curr->mChildrenBegin << "; mChildrenEnd = " << curr->mChildrenEnd << endl;

  // recursively build children
  // NOTE: protect against reallocations of mNodes

  for (i = 0; i < numChildren; ++i)
  {
    curr = &mNodes[currInd];
    curr = &mNodes[curr->mChildrenBegin + i];
    val = buildFromStreamRecur(curr, val, in);
  }

  return val;  
}

int main(int argc, char **argv)
{
  Model m(&cin);

  m.semiPreOrderTraversal();
  m.semiPreOrderTraversalRecur(*m.getEnd());

  return 0;
}

整个树的非递归、预排序遍历看起来像这样：

Node *curr = model.getRoot();  // TODO: handle empty tree
Node *next;
bool  shouldnt_visit_children;

while (1)
{
  // TODO: visit curr -- determine shouldnt_visit_children

  if (shouldnt_visit_children || NULL == (next = model.getChild(curr)))
  {
    // move to next sibling; if no siblings remain then ascend while no siblings remain

    while (NULL == (next = model.getNextSibling(curr)))
      if (model.getEnd() == (curr = model.getParent(curr)))
        goto DONE;

    curr = next;
  }
  else
    curr = next;  // descend to first child
}

DONE:;

话虽如此，我没有看到任何明显的原因说明这种实现（与您之前的链接结构相反）可能具有更好的缓存性能。向量的布局方式和访问方式将推动缓存性能。无论如何，我看不出有什么令人信服的理由，为什么以任何特定的方式进行布局，您不可能在类似地构建链接树时获得类似的结果。例如，如果您发现/相信以半预先排序的树遍历方式布置向量（即 - 向量的布局如下：end、root、root 的孩子、root 的第一个孩子的孩子、root 的第一个孙的孩子等）为您的应用程序提供最佳缓存性能，那么很有可能使用相同的半预购构建顺序构建链接树将产生类似的结果，因为您的内存分配器可能会以与您明确执行的方式类似的方式将您的树打包到内存中。当然，通过您的方法，您可以确定地控制它，而不是依赖于您的结构和相关的分配器是否智能。

显式管理节点和网格在内存中的布局可能会为您带来更好的缓存性能，因为您可以“强制”它在内存中紧密打包对象并强制执行您喜欢的访问模式/局部性——但是一个体面的分配器会可能会获得类似的结果，特别是如果树构建仅在启动时完成一次。

如果您主要按照您的问题所暗示的那样进行预购遍历，那么我建议您以半预购方式布置存储向量，就像我上面描述的那样：end、root、root 的孩子、root 的第一个孩子的孩子, root 的第一个孙子的孩子等等。

PS - 如果您的遍历总是从根开始，那么您也可以消除 Node 中的 mParentIndex ，而是在遍历树时构建一个显式的祖先堆栈，以允许您在下降后遍历树（这可能是递归是隐式执行的）。如果您需要能够从任何给定的随机节点在树中移动，那么您需要将父级的索引存储在节点中。

编辑：正如我在我的一条评论中提到的，我提出的半预购布局还具有一个属性，即节点的所有后代网格都可以在一个简单的数字范围 [Node.mDescedantMeshBegin, Node.mDescendantMeshEnd) 中表示您按照您的建议单独存储网格。因此，如果您需要或想要通过遍历树来构建可见网格的显式列表，那么无论何时找到可见节点，您都可以轻松地将整个可见后代网格范围合并到您的列表中。

EDIT2：我显着更新了代码。我添加了一个基于半预订输入流的递归模型构建器。我修复了一些错误。最重要的是，我添加了一个对模型进行非递归、半前序遍历的函数。它不像真正的预购遍历那么简单，但它可能会让您感兴趣。递归版本可能要简单得多——我会考虑添加它。在我的测试中，节点的访问在 mNodes 中从左到右进行得非常好。然而，当我们向上爬回树时，内存访问有时会在存储阵列中倒退。我相信可以通过维护一个明确的副本数组来删除这些向后引用遍历期间堆栈上的祖先（至少是它们的索引信息）。必须重写 getParent() 和 getNextSibling() 等调用的功能才能使用此数组，而不是在存储向量本身中跳转，但可以这样做。然后你的 mNodes 的内存访问只会从左向右滑动，这可能接近于缓存性能的最佳值（假设你的树足够浅，堆栈上的祖先总是在缓存中，不会产生过度的缓存压力）。

编辑3： 我添加了一个递归半预定遍历，与迭代版本相比它是微不足道的。传递节点索引部分的副本以保留在堆栈中也非常容易，这样当您的递归展开时，您实际上不会返回并再次访问存储阵列的早期部分。相反，您只需查看堆栈上的内容，几乎肯定会在缓存中 - 假设您的树不是超深+宽。您确实需要存储给定级别的所有子项的副本。仅存储您的直系祖先是不够的，您还必须存储他们的兄弟姐妹。使用此代码并以半预定方式布置存储向量，遍历中的所有内存访问都将在存储阵列上从左到右扫描，而不会回溯。我觉得你' 将具有接近最佳的缓存性能。我不明白它怎么会变得更好。

示例 input.txt：每个数字表示隐式当前节点以预购方式有多少个子节点。在下面，哨兵端节点只有1个孩子，一个单数根（代码支持多根），根有5个孩子，根的第一个孩子有0个孩子，根的第二个孩子有2个孩子等等。我使用间距来指示眼睛的树结构，但对于程序本身来说不是必需的。

样本输出：

john-schultzs-macbook-pro:~ jschultz$ clear; ./a.out < input.txt

Node -1 is complete! mParentIndex = 0; mIndex = 0; mChildrenBegin = 1; mChildrenEnd = 2
Node 0 is complete! mParentIndex = 0; mIndex = 1; mChildrenBegin = 2; mChildrenEnd = 7
Node 1 is complete! mParentIndex = 1; mIndex = 2; mChildrenBegin = 7; mChildrenEnd = 7
Node 2 is complete! mParentIndex = 1; mIndex = 3; mChildrenBegin = 7; mChildrenEnd = 9
Node 6 is complete! mParentIndex = 3; mIndex = 7; mChildrenBegin = 9; mChildrenEnd = 16
Node 8 is complete! mParentIndex = 7; mIndex = 9; mChildrenBegin = 16; mChildrenEnd = 16
Node 9 is complete! mParentIndex = 7; mIndex = 10; mChildrenBegin = 16; mChildrenEnd = 16
Node 10 is complete! mParentIndex = 7; mIndex = 11; mChildrenBegin = 16; mChildrenEnd = 16
Node 11 is complete! mParentIndex = 7; mIndex = 12; mChildrenBegin = 16; mChildrenEnd = 17
Node 15 is complete! mParentIndex = 12; mIndex = 16; mChildrenBegin = 17; mChildrenEnd = 17
Node 12 is complete! mParentIndex = 7; mIndex = 13; mChildrenBegin = 17; mChildrenEnd = 17
Node 13 is complete! mParentIndex = 7; mIndex = 14; mChildrenBegin = 17; mChildrenEnd = 17
Node 14 is complete! mParentIndex = 7; mIndex = 15; mChildrenBegin = 17; mChildrenEnd = 17
Node 7 is complete! mParentIndex = 3; mIndex = 8; mChildrenBegin = 17; mChildrenEnd = 19
Node 16 is complete! mParentIndex = 8; mIndex = 17; mChildrenBegin = 19; mChildrenEnd = 20
Node 18 is complete! mParentIndex = 17; mIndex = 19; mChildrenBegin = 20; mChildrenEnd = 20
Node 17 is complete! mParentIndex = 8; mIndex = 18; mChildrenBegin = 20; mChildrenEnd = 20
Node 3 is complete! mParentIndex = 1; mIndex = 4; mChildrenBegin = 20; mChildrenEnd = 21
Node 19 is complete! mParentIndex = 4; mIndex = 20; mChildrenBegin = 21; mChildrenEnd = 21
Node 4 is complete! mParentIndex = 1; mIndex = 5; mChildrenBegin = 21; mChildrenEnd = 25
Node 20 is complete! mParentIndex = 5; mIndex = 21; mChildrenBegin = 25; mChildrenEnd = 26
Node 24 is complete! mParentIndex = 21; mIndex = 25; mChildrenBegin = 26; mChildrenEnd = 26
Node 21 is complete! mParentIndex = 5; mIndex = 22; mChildrenBegin = 26; mChildrenEnd = 28
Node 25 is complete! mParentIndex = 22; mIndex = 26; mChildrenBegin = 28; mChildrenEnd = 29
Node 27 is complete! mParentIndex = 26; mIndex = 28; mChildrenBegin = 29; mChildrenEnd = 29
Node 26 is complete! mParentIndex = 22; mIndex = 27; mChildrenBegin = 29; mChildrenEnd = 30
Node 28 is complete! mParentIndex = 27; mIndex = 29; mChildrenBegin = 30; mChildrenEnd = 30
Node 22 is complete! mParentIndex = 5; mIndex = 23; mChildrenBegin = 30; mChildrenEnd = 30
Node 23 is complete! mParentIndex = 5; mIndex = 24; mChildrenBegin = 30; mChildrenEnd = 30
Node 5 is complete! mParentIndex = 1; mIndex = 6; mChildrenBegin = 30; mChildrenEnd = 30
Beginning Semi-Pre-Order traversal of tree!
Visiting 0
No more siblings to visit! Try to visit their children. Rewinding to oldest sibling 0
Will visit children of 0
Visiting 1
Will visit sibling of 1
Visiting 2
Will visit sibling of 2
Visiting 3
Will visit sibling of 3
Visiting 4
Will visit sibling of 4
Visiting 5
No more siblings to visit! Try to visit their children. Rewinding to oldest sibling 1
No children to visit of 1
Trying to visit children of 2
Will visit children of 2
Visiting 6
Will visit sibling of 6
Visiting 7
No more siblings to visit! Try to visit their children. Rewinding to oldest sibling 6
Will visit children of 6
Visiting 8
Will visit sibling of 8
Visiting 9
Will visit sibling of 9
Visiting 10
Will visit sibling of 10
Visiting 11
Will visit sibling of 11
Visiting 12
Will visit sibling of 12
Visiting 13
Will visit sibling of 13
Visiting 14
No more siblings to visit! Try to visit their children. Rewinding to oldest sibling 8
No children to visit of 8
Trying to visit children of 9
No children to visit of 9
Trying to visit children of 10
No children to visit of 10
Trying to visit children of 11
Will visit children of 11
Visiting 15
No more siblings to visit! Try to visit their children. Rewinding to oldest sibling 15
No children to visit of 15
Reached end of siblings again -> completed traversal of tree rooted by parent 11
Moved back up to 11
Found a great^Nth uncle (12) to check for children to visit!
Trying to visit children of 12
No children to visit of 12
Trying to visit children of 13
No children to visit of 13
Trying to visit children of 14
No children to visit of 14
Reached end of siblings again -> completed traversal of tree rooted by parent 6
Moved back up to 6
Found a great^Nth uncle (7) to check for children to visit!
Trying to visit children of 7
Will visit children of 7
Visiting 16
Will visit sibling of 16
Visiting 17
No more siblings to visit! Try to visit their children. Rewinding to oldest sibling 16
Will visit children of 16
Visiting 18
No more siblings to visit! Try to visit their children. Rewinding to oldest sibling 18
No children to visit of 18
Reached end of siblings again -> completed traversal of tree rooted by parent 16
Moved back up to 16
Found a great^Nth uncle (17) to check for children to visit!
Trying to visit children of 17
No children to visit of 17
Reached end of siblings again -> completed traversal of tree rooted by parent 7
Moved back up to 7
Moved back up to 2
Found a great^Nth uncle (3) to check for children to visit!
Trying to visit children of 3
Will visit children of 3
Visiting 19
No more siblings to visit! Try to visit their children. Rewinding to oldest sibling 19
No children to visit of 19
Reached end of siblings again -> completed traversal of tree rooted by parent 3
Moved back up to 3
Found a great^Nth uncle (4) to check for children to visit!
Trying to visit children of 4
Will visit children of 4
Visiting 20
Will visit sibling of 20
Visiting 21
Will visit sibling of 21
Visiting 22
Will visit sibling of 22
Visiting 23
No more siblings to visit! Try to visit their children. Rewinding to oldest sibling 20
Will visit children of 20
Visiting 24
No more siblings to visit! Try to visit their children. Rewinding to oldest sibling 24
No children to visit of 24
Reached end of siblings again -> completed traversal of tree rooted by parent 20
Moved back up to 20
Found a great^Nth uncle (21) to check for children to visit!
Trying to visit children of 21
Will visit children of 21
Visiting 25
Will visit sibling of 25
Visiting 26
No more siblings to visit! Try to visit their children. Rewinding to oldest sibling 25
Will visit children of 25
Visiting 27
No more siblings to visit! Try to visit their children. Rewinding to oldest sibling 27
No children to visit of 27
Reached end of siblings again -> completed traversal of tree rooted by parent 25
Moved back up to 25
Found a great^Nth uncle (26) to check for children to visit!
Trying to visit children of 26
Will visit children of 26
Visiting 28
No more siblings to visit! Try to visit their children. Rewinding to oldest sibling 28
No children to visit of 28
Reached end of siblings again -> completed traversal of tree rooted by parent 26
Moved back up to 26
Moved back up to 21
Found a great^Nth uncle (22) to check for children to visit!
Trying to visit children of 22
No children to visit of 22
Trying to visit children of 23
No children to visit of 23
Reached end of siblings again -> completed traversal of tree rooted by parent 4
Moved back up to 4
Found a great^Nth uncle (5) to check for children to visit!
Trying to visit children of 5
No children to visit of 5
Reached end of siblings again -> completed traversal of tree rooted by parent 0
Moved back up to 0
Finished Semi-Pre-Order traversal of tree!

score -1 · Accepted Answer

我为 Qt 实现了一个尚未完全兼容的 XPath 版本，因此它包括在不需要使用递归函数的情况下遍历节点树的方法。有一个相关部分的副本，它使用一种算法来遍历给定节点的所有后代（最终包括 Self）。

如果您想查看整个实现（大约 5480 行），可以在SourceForge.net GIT 存储库中找到它。最新的现在在github中。

    case AXIS_DESCENDANT:
    case AXIS_DESCENDANT_OR_SELF:
        switch(node_type)
        {
        case NODE_TYPE_NODE:
        case NODE_TYPE_ELEMENT:
            {
                // as far as I know the type node is considered to be
                // the same as elements (at least in XPath 1.0)
                QDomNode node(context_node);
                if(axis == AXIS_DESCENDANT_OR_SELF
                && (local_part.isEmpty() || local_part == context_node.toElement().tagName())
                && (any_prefix || prefix == context_node.prefix()))
                {
                    result.push_back(context_node);
                }
                while(!node.isNull())
                {
                    QDomNode next(node.firstChild());
                    if(next.isNull())
                    {
                        next = node;
                        while(!next.isNull()) // this should never happend since we should bump in context_node first
                        {
                            if(next == context_node)
                            {
                                // break 2;
                                goto axis_descendant_done;
                            }
                            QDomNode parent(next.parentNode());
                            next = next.nextSibling();
                            if(!next.isNull())
                            {
                                break;
                            }
                            next = parent;
                        }
                    }
                    // the local_part & prefix must match for us to keep the node
                    node = next;
                    if((local_part.isEmpty() || local_part == node.toElement().tagName())
                    && (any_prefix || prefix == node.prefix()))
                    {
                        // push so nodes stay in document order
                        result.push_back(node);
                    }
                }
axis_descendant_done:;
            }
            break;

        default:
            throw QDomXPathException_NotImplemented(QString("this axis (%1) does not support this node type (%2)").arg(static_cast<int>(axis)).arg(static_cast<int>(node_type)).toStdString());

        }
        break;

c++ - 无递归的面向数据的树遍历

3 回答 3

Related

Reference