修改后的前序树遍历算法（Modified Preorder Tree Traversal）

无限分类树（Nested Set Model）是一种用于表示层次结构数据的有效方法。在这种模型中，每个节点都有左右值（left, right），可以用于快速查询树的结构。使用修改后的前序遍历算法可以方便地构建和遍历这种树形结构。

1. 树的结构

在无限分类树中，每个节点都有两个额外的字段：left 和 right。这些字段用于表示节点在树中的位置。通过这些值，可以很容易地获取节点的层级关系和子节点。

例子

假设有以下树结构：

A
├── B
│   ├── D
│   └── E
└── C
    └── F

对应的左右值可能如下：

2. 构建树的算法

2.1 修改后的前序遍历算法

以下是一个简单的算法，用于通过修改后的前序遍历构建无限分类树。

class Node {
    public $id;
    public $left;
    public $right;
    public $children = [];

    public function __construct($id) {
        $this->id = $id;
    }
}

function modifiedPreorderTraversal($node, &$index) {
    // 设置左值
    $node->left = ++$index;

    foreach ($node->children as $child) {
        modifiedPreorderTraversal($child, $index);
    }

    // 设置右值
    $node->right = ++$index;
}

// 示例用法
$root = new Node('A');
$childB = new Node('B');
$childC = new Node('C');
$childD = new Node('D');
$childE = new Node('E');
$childF = new Node('F');

$root->children = [$childB, $childC];
$childB->children = [$childD, $childE];
$childC->children = [$childF];

$index = 0;
modifiedPreorderTraversal($root, $index);

// 输出结果
function printTree($node) {
    echo "Node: {$node->id}, Left: {$node->left}, Right: {$node->right}\n";
    foreach ($node->children as $child) {
        printTree($child);
    }
}

printTree($root);

3. 运行结果

运行上述代码后，将输出每个节点的左右值，例如：

Node: A, Left: 1, Right: 10
Node: B, Left: 2, Right: 5
Node: D, Left: 3, Right: 4
Node: E, Left: 6, Right: 7
Node: C, Left: 8, Right: 9
Node: F, Left: 11, Right: 12

4. 遍历树的算法

使用左右值，可以轻松地查询树的结构。例如，要获取某个节点的所有子节点，可以使用如下方法：

function getSubtree($node, $left, $right) {
    if ($node->left >= $left && $node->right <= $right) {
        return $node;
    }

    foreach ($node->children as $child) {
        $result = getSubtree($child, $left, $right);
        if ($result) {
            return $result;
        }
    }

    return null;
}

// 获取节点 A 的子节点
$subtree = getSubtree($root, 1, 10);
printTree($subtree);