无递归的面向数据的树遍历
Data-oriented tree traversal without recursion
我有一个这样的树结构：模型有一个根节点，每个节点有任意数量的子节点和任意数量的网格。
我的应用程序中的很多时间都花在遍历这棵树和进行视锥体剔除和矩阵乘法等计算上。目前，它是天真的实现，其中每个节点都有子节点和网格的向量，并递归遍历树。这很慢。
我一直在研究面向数据的设计，我喜欢它对缓存非常友好的想法。我一直在想这样的事情：
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;
}
现在我需要遍历树以获取可见网格的列表。在每个节点，我必须检查该节点是否可见。以下分支机构：
- 节点可见。它下面的所有子节点和网格也是可见的。不要深入这个分支。检查相同深度的其他节点。
- 节点不可见。此节点或其下方的子节点或网格不可见。不要深入这个分支。检查相同深度的其他节点。
- 节点部分可见。一些节点 and/or 一些网格是可见的。必须深入层次结构。
树是静态的。一旦模型被加载到应用程序中，树就永远不会改变。因此，我肯定能够以某种方式使用这些信息来获得高效的结构。
虽然我很困惑如何处理这个问题。
几个问题；
- 如何在内存中布局节点？是第一个索引的根节点吗？其他节点是根据深度添加的吗？
- 如何在不使用递归的情况下迭代树？除非我真的必须，否则我不想访问每个节点。例如，如果深度为 2 的节点不可见，则不应测试其所有网格和子节点（及其网格），而应完全跳过。
简短版本：改用 6502 的 pre-order 答案。我将在下面留下我之前的答案，因为它仍然有一些有趣的代码和评论。
以半pre-order 方式布置您的存储阵列。即：哨兵端节点，roots，先根的children，先根的先child的children，先根的先grandchild的child仁等。然后使用递归半 pre-order 遍历遍历树，该遍历将直接祖先及其兄弟姐妹的索引信息的副本保留在堆栈中。这样，您的遍历将从左到右扫描存储阵列，没有回溯。您不需要通过递归访问所有节点，您所做的任何跳过子树只会在存储阵列中向前扫描。
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]);
}
长版（其中一些被省略）：我认为你可以通过向你的节点结构添加更多信息来实现你想要的：节点的索引 parent 和节点的索引当前节点（后者可能不是绝对必要的，因为它可能来自指向 Node 的指针和 Node 存储向量。）
这应该会为您提供足够的上下文信息，以便根据您的需要轻松地将 "up"、"down" 或 "sideways" 移动到同级，给定树中的任何节点。要移动 "up,"，您只需转到 parent 索引。要向下移动，请转到 child 索引中的任何一个。要将 "sideways" 移动到兄弟姐妹，您只需 increase/decrease 当前节点的索引（在检查您不是 parent 的 last/first child 之后）。
您可能需要考虑组合节点和网格结构，以便可以将它们连续存储在一个向量中。对鹅有利的缓存性能通常对鹅有利。由于您的 Mesh 存储在另一个向量中，它们在内存中可能远离它们的 Node 兄弟姐妹并且访问它们 mid-traversal 会给缓存带来更大的压力。当然，如果你的 Mesh 比你的 Node 有更多的数据（反之亦然），或者你不需要在遍历期间访问 Mesh，那么这可能不是一个好的选择，因为它会浪费内存。此外，您的网格可能不需要所有树索引，因为它们是终端节点，并且在您访问节点的 children 时可能是特殊情况。根据具体情况，您最初提出的单独存储网格的建议可能更好。
在下面的代码中，我结合了您的节点和网格结构并将它们存储在一个向量中。
#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;
}
一个non-recursive，pre-order整个树的遍历看起来像这样：
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:;
综上所述，我没有看到任何明显的理由说明为什么这种实现（与您之前使用的链接结构相反）可能具有更好的缓存性能。矢量的布局方式以及您访问它们的方式将推动您的缓存性能。无论如何，我看不出有任何令人信服的理由说明为什么以任何特定方式布置它都不可能以类似方式构建链接树来获得类似结果。例如，如果你 find/believe 以半 pre-order 树遍历的方式布置你的向量（即 - 向量布置如下：end，root，root's children， root's first child's children, root's first grandchild's children, etc.) 为您的应用程序提供最佳缓存性能，那么很有可能使用相同的 semi-pre-order 构建顺序构建链接树将产生类似的结果，因为您的内存分配器可能会以与显式类似的方式将您的树打包到内存中。当然，通过您的方法，您可以确定地控制它，而不是依赖于您的结构和相关分配器是否智能。
显式管理节点和网格在内存中的布局可能会给您带来更好的缓存性能，因为您可以 "force" 将 objects 紧密打包在内存中并强制执行访问模式/ 你喜欢的地方 - 但一个体面的分配器可能会达到类似的结果，特别是如果树构建只在启动时完成一次。
如果您的问题似乎表明您主要进行 pre-order 遍历，那么我建议您以半 pre-order 方式布置您的存储向量，就像我上面描述的那样：结束，根，根的child仁，根的先child的child仁，根的先祖child的child仁等等。
PS - 如果您的遍历总是从根开始，那么您也可以消除 Node 中的 mParentIndex，而是在遍历树时构建一个显式的祖先堆栈，以允许您向上遍历下降后的树（这可能是递归隐式执行的操作）。如果您需要能够从任何随机给定的节点绕树移动，那么您需要将 parent 的索引存储在节点中。
编辑： 正如我在其中一条评论中提到的，我提出的半 pre-order 布局也具有 属性 所有后代网格的节点的当您按照建议单独存储网格时，可以用简单的数字范围 [Node.mDescedantMeshBegin、Node.mDescendantMeshEnd) 表示。因此，如果您需要或想要通过遍历树来构建可见网格的显式列表，那么无论何时找到可见节点，您都可以轻松地将整个范围的可见后代网格合并到您的列表中。
EDIT2: 我显着更新了代码。我添加了一个基于半 pre-order 输入流的递归模型构建器。我修复了一些错误。最重要的是，我添加了一个函数，可以对模型进行 non-recursive、半 pre-order 遍历。它不像真正的 pre-order 遍历那么简单，但您可能会感兴趣。递归版本可能要简单得多——我会考虑添加它。在我的测试中，节点的访问在 mNodes 中从左到右进行得非常好。然而，当我们向上返回树时，内存访问有时会在存储阵列中倒退。我相信这些向后引用可以通过在遍历期间在堆栈上维护祖先的 副本 的显式数组（至少是它们的索引信息）来删除。必须重写 getParent() 和 getNextSibling() 等调用的功能才能使用此数组，而不是在存储向量本身中跳来跳去，但这是可以做到的。然后你对 mNodes 的内存访问只会从左向右滑动，这可能接近缓存性能的最佳状态（假设你的树足够浅以至于你在堆栈上的祖先将始终在缓存中并且不会产生过度的缓存压力）。
EDIT3: 我添加了一个递归半 pre-order 遍历，与迭代版本相比它是微不足道的。传递节点索引部分的副本以保留在堆栈中也非常容易，这样当递归展开时，您实际上不会返回并再次访问存储阵列的早期部分。相反，您只需查看堆栈上的内容，它们几乎肯定会在缓存中——假设您的树不是超深+宽。您确实需要在给定级别存储所有 children 的副本。仅存储您的直系祖先是不够的，您还必须存储他们的兄弟姐妹。使用此代码并在半 pre-order 中布置您的存储向量，遍历中的所有内存访问都将从左到右扫描您的存储阵列，没有回溯。我认为您将获得接近最佳的缓存性能。我看不出它如何变得更好。
样本input.txt：每个数字代表隐式当前节点有多少childrenpre-order时尚。下面sentinel端节点只有1个child，一个单根（代码支持多根），根有5个children，第一个child根有 0 children，根的第二个 child 有 2 children 等等。我用间距来指示眼睛的树结构，但程序本身没有必要。
1
5
0
2
7
0
0
0
1
0
0
0
0
2
1
0
0
1
0
4
1
0
2
1
0
1
0
0
0
0
示例输出：
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!
我为 Qt 实现了一个尚未完全兼容的 XPath 版本，因此它包括无需使用递归函数即可遍历节点树的方法。有一个相关部分的副本使用算法遍历给定节点的所有后代（最终包括自我）。
如果你想看whole implementation (around line 5480), it is available in SourceForge.net GIT repository. The latest is now in 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;
您可以按照深度优先遍历顺序将树表示为内存中的单个数组
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;
}
}
同样的代码也可以通过保留显式堆栈转换为非递归代码（不知道为什么这是个好主意，除非节点操作和检查非常快或者树非常深）。
我有一个这样的树结构：模型有一个根节点，每个节点有任意数量的子节点和任意数量的网格。
我的应用程序中的很多时间都花在遍历这棵树和进行视锥体剔除和矩阵乘法等计算上。目前，它是天真的实现，其中每个节点都有子节点和网格的向量，并递归遍历树。这很慢。
我一直在研究面向数据的设计，我喜欢它对缓存非常友好的想法。我一直在想这样的事情：
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;
}
现在我需要遍历树以获取可见网格的列表。在每个节点，我必须检查该节点是否可见。以下分支机构：
- 节点可见。它下面的所有子节点和网格也是可见的。不要深入这个分支。检查相同深度的其他节点。
- 节点不可见。此节点或其下方的子节点或网格不可见。不要深入这个分支。检查相同深度的其他节点。
- 节点部分可见。一些节点 and/or 一些网格是可见的。必须深入层次结构。
树是静态的。一旦模型被加载到应用程序中，树就永远不会改变。因此，我肯定能够以某种方式使用这些信息来获得高效的结构。
虽然我很困惑如何处理这个问题。
几个问题；
- 如何在内存中布局节点？是第一个索引的根节点吗？其他节点是根据深度添加的吗？
- 如何在不使用递归的情况下迭代树？除非我真的必须，否则我不想访问每个节点。例如，如果深度为 2 的节点不可见，则不应测试其所有网格和子节点（及其网格），而应完全跳过。
简短版本：改用 6502 的 pre-order 答案。我将在下面留下我之前的答案，因为它仍然有一些有趣的代码和评论。
以半pre-order 方式布置您的存储阵列。即：哨兵端节点，roots，先根的children，先根的先child的children，先根的先grandchild的child仁等。然后使用递归半 pre-order 遍历遍历树，该遍历将直接祖先及其兄弟姐妹的索引信息的副本保留在堆栈中。这样，您的遍历将从左到右扫描存储阵列，没有回溯。您不需要通过递归访问所有节点，您所做的任何跳过子树只会在存储阵列中向前扫描。
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]);
}
长版（其中一些被省略）：我认为你可以通过向你的节点结构添加更多信息来实现你想要的：节点的索引 parent 和节点的索引当前节点（后者可能不是绝对必要的，因为它可能来自指向 Node 的指针和 Node 存储向量。）
这应该会为您提供足够的上下文信息，以便根据您的需要轻松地将 "up"、"down" 或 "sideways" 移动到同级，给定树中的任何节点。要移动 "up,"，您只需转到 parent 索引。要向下移动，请转到 child 索引中的任何一个。要将 "sideways" 移动到兄弟姐妹，您只需 increase/decrease 当前节点的索引（在检查您不是 parent 的 last/first child 之后）。
您可能需要考虑组合节点和网格结构，以便可以将它们连续存储在一个向量中。对鹅有利的缓存性能通常对鹅有利。由于您的 Mesh 存储在另一个向量中，它们在内存中可能远离它们的 Node 兄弟姐妹并且访问它们 mid-traversal 会给缓存带来更大的压力。当然，如果你的 Mesh 比你的 Node 有更多的数据（反之亦然），或者你不需要在遍历期间访问 Mesh，那么这可能不是一个好的选择，因为它会浪费内存。此外，您的网格可能不需要所有树索引，因为它们是终端节点，并且在您访问节点的 children 时可能是特殊情况。根据具体情况，您最初提出的单独存储网格的建议可能更好。
在下面的代码中，我结合了您的节点和网格结构并将它们存储在一个向量中。
#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;
}
一个non-recursive，pre-order整个树的遍历看起来像这样：
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:;
综上所述，我没有看到任何明显的理由说明为什么这种实现（与您之前使用的链接结构相反）可能具有更好的缓存性能。矢量的布局方式以及您访问它们的方式将推动您的缓存性能。无论如何，我看不出有任何令人信服的理由说明为什么以任何特定方式布置它都不可能以类似方式构建链接树来获得类似结果。例如，如果你 find/believe 以半 pre-order 树遍历的方式布置你的向量（即 - 向量布置如下：end，root，root's children， root's first child's children, root's first grandchild's children, etc.) 为您的应用程序提供最佳缓存性能，那么很有可能使用相同的 semi-pre-order 构建顺序构建链接树将产生类似的结果，因为您的内存分配器可能会以与显式类似的方式将您的树打包到内存中。当然，通过您的方法，您可以确定地控制它，而不是依赖于您的结构和相关分配器是否智能。
显式管理节点和网格在内存中的布局可能会给您带来更好的缓存性能，因为您可以 "force" 将 objects 紧密打包在内存中并强制执行访问模式/ 你喜欢的地方 - 但一个体面的分配器可能会达到类似的结果，特别是如果树构建只在启动时完成一次。
如果您的问题似乎表明您主要进行 pre-order 遍历，那么我建议您以半 pre-order 方式布置您的存储向量，就像我上面描述的那样：结束，根，根的child仁，根的先child的child仁，根的先祖child的child仁等等。
PS - 如果您的遍历总是从根开始，那么您也可以消除 Node 中的 mParentIndex，而是在遍历树时构建一个显式的祖先堆栈，以允许您向上遍历下降后的树（这可能是递归隐式执行的操作）。如果您需要能够从任何随机给定的节点绕树移动，那么您需要将 parent 的索引存储在节点中。
编辑： 正如我在其中一条评论中提到的，我提出的半 pre-order 布局也具有 属性 所有后代网格的节点的当您按照建议单独存储网格时，可以用简单的数字范围 [Node.mDescedantMeshBegin、Node.mDescendantMeshEnd) 表示。因此，如果您需要或想要通过遍历树来构建可见网格的显式列表，那么无论何时找到可见节点，您都可以轻松地将整个范围的可见后代网格合并到您的列表中。
EDIT2: 我显着更新了代码。我添加了一个基于半 pre-order 输入流的递归模型构建器。我修复了一些错误。最重要的是，我添加了一个函数，可以对模型进行 non-recursive、半 pre-order 遍历。它不像真正的 pre-order 遍历那么简单，但您可能会感兴趣。递归版本可能要简单得多——我会考虑添加它。在我的测试中，节点的访问在 mNodes 中从左到右进行得非常好。然而，当我们向上返回树时，内存访问有时会在存储阵列中倒退。我相信这些向后引用可以通过在遍历期间在堆栈上维护祖先的 副本 的显式数组（至少是它们的索引信息）来删除。必须重写 getParent() 和 getNextSibling() 等调用的功能才能使用此数组，而不是在存储向量本身中跳来跳去，但这是可以做到的。然后你对 mNodes 的内存访问只会从左向右滑动，这可能接近缓存性能的最佳状态（假设你的树足够浅以至于你在堆栈上的祖先将始终在缓存中并且不会产生过度的缓存压力）。
EDIT3: 我添加了一个递归半 pre-order 遍历，与迭代版本相比它是微不足道的。传递节点索引部分的副本以保留在堆栈中也非常容易，这样当递归展开时，您实际上不会返回并再次访问存储阵列的早期部分。相反，您只需查看堆栈上的内容，它们几乎肯定会在缓存中——假设您的树不是超深+宽。您确实需要在给定级别存储所有 children 的副本。仅存储您的直系祖先是不够的，您还必须存储他们的兄弟姐妹。使用此代码并在半 pre-order 中布置您的存储向量，遍历中的所有内存访问都将从左到右扫描您的存储阵列，没有回溯。我认为您将获得接近最佳的缓存性能。我看不出它如何变得更好。
样本input.txt：每个数字代表隐式当前节点有多少childrenpre-order时尚。下面sentinel端节点只有1个child，一个单根（代码支持多根），根有5个children，第一个child根有 0 children，根的第二个 child 有 2 children 等等。我用间距来指示眼睛的树结构，但程序本身没有必要。
1
5
0
2
7
0
0
0
1
0
0
0
0
2
1
0
0
1
0
4
1
0
2
1
0
1
0
0
0
0
示例输出：
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!
我为 Qt 实现了一个尚未完全兼容的 XPath 版本，因此它包括无需使用递归函数即可遍历节点树的方法。有一个相关部分的副本使用算法遍历给定节点的所有后代（最终包括自我）。
如果你想看whole implementation (around line 5480), it is available in SourceForge.net GIT repository. The latest is now in 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;
您可以按照深度优先遍历顺序将树表示为内存中的单个数组
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;
}
}
同样的代码也可以通过保留显式堆栈转换为非递归代码（不知道为什么这是个好主意，除非节点操作和检查非常快或者树非常深）。