相关疑难解决方法(0)

有人可以帮我理解下面的Morris inorder树遍历算法而不使用堆栈或递归吗？我试图了解它是如何工作的,但它只是逃避了我.

 1. Initialize current as root
 2. While current is not NULL
  If current does not have left child     
   a. Print current’s data
   b. Go to the right, i.e., current = current->right
  Else
   a. In current's left subtree, make current the right child of the rightmost node
   b. Go to this left child, i.e., current = current->left

我理解的树被修改的方式,将current node在作出right child的的max node中right subtree和使用该财产序遍历.但除此之外,我迷失了.

编辑:找到这个附带的c ++代码.我很难理解修改后树的恢复方式.神奇在于else子句,一旦修改了正确的叶子就会被击中.请参阅代码了解详情:

/* Function to traverse binary …

在由具有指向父级、兄弟级和第一个/最后一个子级的指针的节点表示的通用树中，如下所示：

class Tnode {

    def data
    Tnode parent = null
    Tnode first_child = null, last_child = null 
    Tnode prev_sibling = null, next_sibling = null 

    Tnode(data=null) {
        this.data = data
    }
}

是否可以在不使用任何其他辅助结构（例如队列）的情况下进行迭代（非递归）广度优先（级别顺序）遍历。

所以基本上：我们可以使用单节点引用进行回溯，但不能保存节点集合。到底能不能做到是理论上的部分，但更实际的问题是，在大段上不回溯的情况下，能否高效地做到。