树遍历 Tree Traversal

整理 transform tree 的深度优先遍历接口和 iterator 实现。

May 29, 2025约 5 分钟Transform Hierarchiesysysimon

树遍历 Tree Traversal

一种常见的组织变换的形式是，在 变换节点 中存储指向它 父变换 的指针以及其所有 子变换 的列表

struct Transform 
{
  Transform* parent;
  std::vector<Transform*> children;
 
  Vector    position;
  Quaternion rotation;
  Vector    scale;
};

这种数据组织结构，很容易进行 深度优先遍历 depth first traversal，可以使用递归 (使用 系统栈)，或者显式的使用一个 栈 stack 数据结构，但是不管使用哪种方式都免不了一些内存分配的开销，当然实际存储所有 子变换 的列表也需要分配内存空间

我们可以使用另一种数据的组织结构，称为 First-Child/Next-Sibling，它把每个节点的 “子节点列表” 展开成一条链表：第一个子节点通过 firstChild 指针，后面的兄弟通过 nextSibling 串起来，由于只有指针，不需要额外数组或动态分配

struct Transform {
  Transform* parent;        // 指向父节点
  Transform* firstChild;    // 指向第一个子节点
  Transform* nextSibling;   // 指向下一个兄弟节点
 
  Vector     position;
  Quaternion rotation;
  Vector     scale;
};

对这种数据结构使用 递归版深度优先遍历 (使用 系统栈)

void DepthFirstTraversal(Node* root, NodeVisitorFnPtr callback) {
  callback(root);
  if (root->firstChild)
    DepthFirstTraversal(root->firstChild, callback);
  for (auto* sib = root->nextSibling; sib; sib = sib->nextSibling) {
    DepthFirstTraversal(sib, callback);
  }
}

下钻到 firstChild，走到末尾再回溯到 parent，然后跳到 nextSibling

也可以使用 迭代版本

class Scene {
  Node* root;
public:
  // 传入 nullptr 表示从 root 开始；每次调用返回下一个要访问的节点，遍历完返回 nullptr
  Node* DepthFirst(Node* iter = nullptr) {
    if (!iter) return root;
    if (iter->firstChild)
      return iter->firstChild;
    while (iter->nextSibling == nullptr) {
      if (iter == root) return nullptr;
      iter = iter->parent;
    }
    return iter->nextSibling;
  }
};
// 用法：
for (Node* it = scene.DepthFirst(); it; it = scene.DepthFirst(it)) {
  // 对 it 做点什么……
}

这样就把遍历逻辑封装到一个 “下一个节点” 函数里，外层只要一个简单的 for 循环，无需显式管理栈

可以将其设计为 迭代器

// df_iterator.hpp
#pragma once
 
template<typename NodeT>
struct DFIterator {
  using value_type        = NodeT*;
  using reference         = NodeT*&;
  using pointer           = NodeT**;
  using difference_type   = std::ptrdiff_t;
  using iterator_category = std::forward_iterator_tag;
 
  inline explicit DFIterator(NodeT* root = nullptr)  
    : root_(root), current_(root) {}
 
  inline NodeT* operator*()  const noexcept { return current_; }
  inline NodeT* operator->() const noexcept { return current_; }
 
  inline DFIterator& operator++() noexcept {
    if (current_->firstChild) {
      current_ = current_->firstChild;
    } else {
      while (current_->nextSibling == nullptr) {
        if (current_ == root_) {
          current_ = nullptr;
          return *this;
        }
        current_ = current_->parent;
      }
      current_ = current_->nextSibling;
    }
    return *this;
  }
 
  inline bool operator==(DFIterator const& o) const noexcept {
    return current_ == o.current_;
  }
  inline bool operator!=(DFIterator const& o) const noexcept {
    return !(*this == o);
  }
 
private:
  NodeT* root_;
  NodeT* current_;
};
 
template<typename NodeT>
struct DFRange {
  NodeT* root_;
  inline DFRange(NodeT* root): root_(root) {}
  inline DFIterator<NodeT> begin() const noexcept { return DFIterator<NodeT>(root_); }
  inline DFIterator<NodeT> end()   const noexcept { return DFIterator<NodeT>(nullptr); }
};

用法

#include "df_iterator.hpp"
 
// 假设你有：
struct Node {
  Node* parent;
  Node* firstChild;
  Node* nextSibling;
  // …其他数据…
};
 
DFRange<Node> range(scene.root());
for (Node* node : range) {
  // 内部的 operator++()、operator*() 都是 inline 在这里展开的
  process(node);
}