algorithm - 如何以相反的顺序遍历这棵树

Question

我找到了一个莫里斯树遍历的实现，

它工作正常，但是在尝试以相反的顺序遍历树时有点问题.. -

    void MorrisTraversal(struct Node *root)
    {  
    struct Node *p,*pre;
    if(root==0) { return; }
    for(p=root;p!=0;)
    {
    if(p->Left==0) { printf(" %d ",p->Data); p=p->Right; continue; }
    for(pre=p->Left;pre->Right!=0 && pre->Right!=p;pre=pre->Right) { }
    if(pre->Right==0)
        { pre->Right=p; p=p->Left; continue; }
    else
        { pre->Right=0; printf(" %d ",p->Data); p=p->Right; continue; }

    }
}

Answer 1

通过反向顺序，我假设您的意思是反向中序遍历。你至少有两个选择：

1. 您可以修改代码并将所有->Right指针引用交换为->Left一个。

2. 您可以将这两个printf语句替换为推送到堆栈上。算法完成后，您将从堆栈中弹出数据以打印它们。然而，这违背了 Morris 遍历算法的全部目的，即无堆栈。

这个相关的SO 线程可能会帮助您理解。

我希望这有帮助。

Answer 2

这是 Java 中的一个示例。单击此处获取另一个使用迭代而不是递归的示例。

public int depthOfTree(TreeNode node){
    if(node == null){
        return 0;
    }

    int leftDepth = depthOfTree(node.left);
    int rightDepth = depthOfTree(node.right);

    if(leftDepth > rightDepth){
        return leftDepth+1;
    } else {
        return rightDepth+1;
    }
}

//Reverse Level with recursion
public void reverseLevelOrder(TreeNode node){
    int depth = depthOfTree(node);

    for(int i=depth;i>0;i--){
        printTree(node,i);
    }
}

public void printTree(TreeNode node, int level){
    if(node == null){
        return;
    }
    if(level == 1){
        System.out.print(node.data+" ,");
    } else if(level>1){
        printTree(node.left, level-1);
        printTree(node.right, level-1);
    }
}