不使用额外内存的级别顺序树遍历

Question

我知道树的水平顺序遍历的算法。（我想大家都知道）该算法使用队列存储树的节点。有没有不使用额外内存的算法？该算法不能使用递归（这样我们就可以使用堆栈）。注意，该树以左子右同级表示形式给出。不允许使用其他指针
对于树，C中的结构是：

struct node {
int data;
struct node *left-child;
struct node *right-sibling;
}

树用指向根节点的指针表示。当然，root不能有正确的兄弟。

Answer 1

如果要在恒定空间中遍历树，可以应用莫里斯级顺序遍历。你可以参考这里和这里。

Answer 2

如果可以在树的每个节点中存储一个额外的下一个指针，该指针按每个级别的级别顺序指向下一个节点，则可以在常量空间中执行级别顺序遍历。

Answer 3

一种方法是使用空的右同级指针使所有节点成为彼此的同级（暂时）。

你可以用一个又慢又快的指针。最快的一个总是在最后一个同级（它的空指针为右同级）。然后，慢速节点的左子节点指针将被复制到该右同级节点，之后快速指针将再次运行到末端。慢速指针向右移动一步，重复相同的操作。当慢速指针也到达终点时，所有节点都将是同级节点。可以使用慢速或快速指针按级别顺序输出值。这将完成任务，但树将因此被摧毁。

要恢复树，我建议在上述过程中，所有兄弟边的方向都是反向的。这意味着您需要另一个落后于慢速指针的指针。这将允许在这两者之间执行反转。这有点晦涩，因为右同胞实际上会指向一些主要是左同胞的东西。

在上面的过程之后，指针将位于节点列表的末尾，但是由于我们已经反转了同级边，所以我们也可以返回并再次反转边。一个困难是知道哪些同级指针应该再次变为null（当节点最初是最右边的子节点时）。这可以通过再次让一个快速指针向前移动（向左）来查找具有子节点的节点来实现。如果落后于慢指针的指针命中这样一个子指针，我们知道慢指针的节点应该得到一个空指针，即右同级。当应用此修复程序时，快速指针应再次向前运行以查找另一个父节点。。。等

请注意，此算法不会更改左子指针。

所以，总的来说，这个解决方案使用了三个指针和树本身的结构。

下面是我在以下实现中使用的示例树：

          1
         /
        2 ------------ 3 ---------4
       /              /          /
      5 -- 6 -- 7    8 -- 9     10 -- 11 -- 12 -- 13
          /                           /
        14 -- 15 -- 16              17 -- 18 -- 19

JavaScript中的实现--可运行代码段：

function * traverse(node) {
    let lead = node; // ...walks somewhere ahead of node
    let lag = null; // ... always follows one step behind node
    while (node) {
        yield node.data; // output
        lead.rightSibling = node.leftChild;
        while (lead.rightSibling) lead = lead.rightSibling;
        // rotate: point node to next right-sibling, and reverse direction of sibling edge
        [node.rightSibling, lag, node] = [lag, node, node.rightSibling]
    }
    
    // Restore tree
    lead = node = lag.rightSibling; // backwards
    lag.rightSibling = null;
    while (lead !== null && lead.leftChild === null) lead = lead.rightSibling; // actually going left!
    while (node) {
        if (lead !== null && lead.leftChild === lag) {
            // When lag is the leftChild of some node (lead), then lag should not be the target of a rightSibling
            [node.rightSibling, lag, node] = [null, node, node.rightSibling];
            // Find previous parent
            lead = lead.rightSibling;
            while (lead !== null && lead.leftChild === null) lead = lead.rightSibling; // actually going left!
        } else {
            // walk back and restore sibling pointers
            [node.rightSibling, lag, node] = [lag, node, node.rightSibling];
        }
    }
}

// Create node, given its data and child nodes
function Node(data, ...children) {
    // Link the children as siblings
    if (children.length > 1) children.reduceRight((a, b) => (b.rightSibling = a, b))
    // Create the node itself. For now, without any siblings
    return {
        data,
        leftChild: children.length ? children[0] : null,
        rightSibling: null
    };
}

// Example tree
let tree = Node(1, 
    Node(2, 
        Node(5), Node(6,
            Node(14), Node(15), Node(16)
        ), Node(7)
    ), Node(3,
        Node(8), Node(9)
    ), Node(4,
        Node(10), Node(11,
            Node(17), Node(18), Node(19)
        ), Node(12), Node(13)
    )
);

// Apply the algorithm and output the yielded values     
console.log(...traverse(tree));