我访问了很多网站，但无法找到Morris postOrder遍历的任何算法。我知道我们可以在preOrder和inOrder中使用Morris算法。如果有人指向postOrder Morris算法（如果存在的话），那将会很有帮助。
我将尝试解释，我们如何使用Morris方法实现后序遍历。预先要求：在解释，下订单遍历之前，让我们修改有序遍历。
在按顺序遍历中，从根节点1开始。如果当前节点已经离开子节点，则找到其有序前导并使root作为其右子节点并向左移动。 [找到前任，在其左子树中找到最大元素] 2.如果当前节点没有左子节点，则打印数据并向右移动。
恢复树：应该注意的主要事情是，在执行步骤1时，我们将达到前任右子项本身是当前节点的点，这只发生在整个左子节点关闭并且我们从那里开始打印数据时。 [当你没有找到当前节点的左子时]所以对于这种情况，我们需要从该节点切掉右子。
void MorriesInorder(BTnode root) {
if(root == null ) return;
BTnode temp;
while ( root!=null){
//case 2: when left child does not exist
if ( root.left == null ) {
print( root.data );
root = root.right;
}else {
//find predecessor
temp = root.left;
while ( temp.right!=null &&
temp.right!=root) // to check restore case
temp = temp.right;
if ( temp.right == null ) //predecessor found, converting
{
temp.right = root;
root = root.left;
} else {
print root.data;
temp.right = null; // cut right child off
root = root.right;
}
}
}}
现在回到原始问题，我们如何执行Postorder遍历。我们将使用上述概念进行微小更改以实现后序遍历。首先让我们有一个虚拟节点，并将整个树作为虚拟节点的左子，并使右子空。 [为什么？如果我们假设没有正确的root子，那么打印左子，然后root成为postorder遍历，对吧;）]现在接下来呢？我们完成了，不...只对新树执行顺序没有任何意义，它仍然打印遍历原始树后跟虚拟节点。
首先从案例2中删除打印数据[在inorder遍历中讨论]
关键部分：现在仔细观察内部的其他块，这是需要注意的一段代码。由于这个临时扩展树是有序遍历中的遍历主题，除了在内部else子句中，在找到临时父节点之后，p.left（包括）和p（被排除）之间的节点在修改后向右扩展树以相反的顺序处理。为了在恒定时间内处理它们，向下扫描节点链并反转右引用以引用节点的父节点。然后向上扫描相同的链，访问每个节点，并将右引用恢复到其原始设置。
//This is Post Order :children before node( L ,R , N)
void morrisPostorderTraversal(Node *root){
// Making our tree left subtree of a dummy Node
Node *dummyRoot = new Node(0);
dummyRoot->left = root;
//Think of P as the current node
Node *p = dummyRoot, *pred, *first, *middle, *last;
while(p!=NULL){
if(p->left == NULL){
p = p->right;
} else{
/* p has a left child => it also has a predeccessor
make p as right child predeccessor of p
*/
pred = p->left;
while(pred->right!=NULL && pred->right != p){
pred = pred->right;
}
if(pred->right == NULL){
// predeccessor found for first time
// modify the tree
pred->right = p;
p = p->left;
}else {
// predeccessor found second time
// reverse the right references in chain from pred to p
first = p;
middle = p->left;
while(middle!=p){
last = middle->right;
middle->right = first;
first = middle;
middle = last;
}
// visit the nodes from pred to p
// again reverse the right references from pred to p
first = p;
middle = pred;
while(middle!=p){
cout<<" "<<middle->data;
last = middle->right;
middle->right = first;
first = middle;
middle = last;
}
// remove the pred to node reference to restore the tree structure
pred->right = NULL;
p = p-> right;
}
}
}
}
一种更简单的方法是与预先订购的morris遍历对称地相反，并以相反的顺序打印节点。
TreeNode* node = root;
stack<int> s;
while(node) {
if(!node->right) {
s.push(node->val);
node = node->left;
}
else {
TreeNode* prev = node->right;
while(prev->left && prev->left != node)
prev = prev->left;
if(!prev->left) {
prev->left = node;
s.push(node->val);
node = node->right;
}
else {
node = node->left;
prev->left = NULL;
}
}
}
while(!s.empty()) {
cout << s.top() << " ";
s.pop();
}
cout << endl;
我的Java解决方案 - 它有很多代码注释，但如果你想要更多的解释，请在这里评论。
public static void postOrder(Node root) {
// ensures all descendants of root that are right-children
// (arrived at only by "recurring to right") get inner-threaded
final Node fakeNode = new Node(0); // prefer not to give data, but construction requires it as primitive
fakeNode.left = root;
Node curOuter = fakeNode;
while(curOuter != null){ // in addition to termination condition, also prevents fakeNode printing
if(curOuter.left != null){
final Node curOuterLeft = curOuter.left;
// Find in-order predecessor of curOuter
Node curOuterInOrderPred = curOuterLeft;
while(curOuterInOrderPred.right != null && curOuterInOrderPred.right != curOuter){
curOuterInOrderPred = curOuterInOrderPred.right;
}
if(curOuterInOrderPred.right == null){
// [Outer-] Thread curOuterInOrderPred to curOuter
curOuterInOrderPred.right = curOuter;
// "Recur" on left
curOuter = curOuterLeft;
} else { // curOuterInOrderPred already [outer-] threaded to curOuter
// -> [coincidentally] therefore curOuterLeft's left subtree is done processing
// Prep for [inner] threading (which hasn't ever been done yet here)...
Node curInner = curOuterLeft;
Node curInnerNext = curInner.right;
// [Inner-] Thread curOuterLeft [immediately backwards] to curOuter [its parent]
curOuterLeft.right = curOuter;
// [Inner-] Thread the same [immediately backwards] for all curLeft descendants
// that are right-children (arrived at only by "recurring" to right)
while(curInnerNext != curOuter){
// Advance [inner] Node refs down 1 level (to the right)
final Node backThreadPrev = curInner;
curInner = curInnerNext;
curInnerNext = curInnerNext.right;
// Thread immediately backwards
curInner.right = backThreadPrev;
}
// curInner, and all of its ancestors up to curOuterLeft,
// are now indeed back-threaded to each's parent
// Print them in that order until curOuter
while(curInner != curOuter){
/*
-> VISIT
*/
System.out.print(curInner.data + " ");
// Move up one level
curInner = curInner.right;
}
// "Recur" on right
curOuter = curOuter.right;
}
} else {
// "Recur" on right
curOuter = curOuter.right;
}
}
}
class Node {
Node left;
Node right;
int data;
Node(int data) {
this.data = data;
left = null;
right = null;
}
}