morris 遍历非常适合具有 O(n) 时间和 O(1) 空间的 InOrder 遍历。是否可以仅通过更改一些东西来使用相同的算法实现 PreOrder 和 PostOrder 遍历。
问问题
3022 次
6 回答
2
我不认为我们可以使用线程来实现发布顺序。在后序中，我们必须遍历两个孩子，然后是他们的父母。我们可以建立从孩子到父母的链接，但在那之后我们不能上这个父母，因为他们没有链接。（一个指向左孩子，一个指向右孩子，没有向上指向）
1
/ \
2 3
/ \
4 5
我们可以在 4 的右节点创建一个指向节点 5 的线程。我们可以在 5 的右节点创建一个指向节点 2 的线程。
但是在节点 2 上没有空指针来创建任何线程。节点 2 已经有指向节点 4 和 5 的指针。
于 2013-08-08T20:03:00.480 回答
1
我知道使用 morison Algo 进行预购的解决方案。
这是java代码
public static void morisonPreOrder(TreeNode root) {
TreeNode curr = root, tmp=null;
while (curr != null) {
if(curr.leftNode == null) {
System.out.print(curr.value + " ");
curr = curr.rightNode;
} else {
tmp = curr.leftNode;
while (tmp.rightNode != null && tmp.rightNode != curr) {
tmp = tmp.rightNode;
}
if(tmp.rightNode == null) {
System.out.print(curr.value + " ");
tmp.rightNode = curr;
curr = curr.leftNode;
} else {
tmp.rightNode = null;
curr = curr.rightNode;
}
}
}
}
于 2012-04-07T08:59:53.980 回答
1
后序可以通过简单地反转有序莫里斯算法来实现。解释，
按顺序 python Morris 实现：
def in_order(root):
if not root:
return []
current = root
in_order_list = []
while current:
if not current.left:
in_order_list += [current.val] # Mark current as visited
current = current.right
else:
# find the right most of the left tree
predecessor = current.left
while (predecessor.right) and (predecessor.right != current):
predecessor = predecessor.right
# and create a link from this to current
if not predecessor.right:
predecessor.right = current
current = current.left
else: # now bring back the tree to it's original shape
predecessor.right = None
in_order_list += [current.val]
current = current.right
return in_order
对于后订单，从 current 开始，如果 current.right 为空 - 开始向左看。如果没有，找到最左边的前任并将这个前任的左边链接回当前。（简而言之，按顺序翻转左侧并保持将节点插入到访问列表的开头；））
后订购 Python Morris
def post_order(root):
if not root:
return []
current = root
post_order_list = []
while current:
if not current.right:
post_order_list.insert(0, current.val)
current = current.left
else:
# find left most of the right sub-tree
predecessor = current.right
while (predecessor.left) and (predecessor.left != current):
predecessor = predecessor.left
# and create a link from this to current
if not predecessor.left:
post_order_list.insert(0, current.val)
predecessor.left = current
current = current.right
else:
predecessor.left = None
current = current.left
return post_order
于 2019-03-29T07:15:36.583 回答
0
/ PreOrder 实现没有堆栈和递归/
private static void morrisPreorder(){
while(node != null){
System.out.println(node.getData());
if (node.getLeftNode() == null){
node = node.getRightNode();
} else {
Node rightnode = node.getRightNode();
Node current = node.getLeftNode();
while(current.getRightNode() != null && current.getRightNode().getData() != node.getData())
current = current.getRightNode();
if(current.getRightNode() == null){
current.setRightNode(node.getRightNode());
node = node.getLeftNode();
} else {
node = node.getRightNode();
}
}
}
}
于 2013-07-02T19:16:10.387 回答
0
这是使用修改后的 morris 遍历进行预购遍历的示例代码。
您可以使用类似的方式修改右前任的左链接以进行后序遍历。
我没有时间测试代码。如果这段代码有问题，请告诉我。
void preOrderNonRecursive( BSTNode* root )
{
if(!root)
return;
BSTNode* cur = root;
while(cur)
{
bool b = false;
BSTNode* pre = NULL;
if (cur->left)
{
pre = cur->left;
while(pre->right && pre->right != cur)
pre = pre->right;
if(!pre->right)
{
pre->right = cur;
b = true;
}
else
pre->right = NULL;
}
else
printf("%d\n",cur->val);
if(b)
{
printf("%d\n",cur->val);
cur = cur->left;
}
else
cur = cur->right;
}
}
于 2012-11-12T04:28:02.490 回答
0
上面已经回答了前序遍历。
对于后序遍历，答案也是“是”。
唯一需要的修改是： 1.当前任的右孩子是当前节点时，将右孩子设置为null，并将当前节点左孩子的所有节点反向输出到前任。2.设置一个虚拟节点并将其左子节点设置为树的根。
Java代码写在这里：
private void printPostTraverse(List<Integer> traverseList, TreeNode start, TreeNode end) {
TreeNode node = start;
int insertIndex = traverseList.size();
while (node != end) {
traverseList.add(insertIndex, node.val);
node = node.right;
}
traverseList.add(insertIndex, node.val);
}
public List<Integer> postorderMorrisTraversal(TreeNode root) {
List<Integer> traverseList = new ArrayList<>();
TreeNode dummy = new TreeNode(-1);
dummy.left = root;
TreeNode cur = dummy, prev = null;
while (cur != null) {
if (cur.left == null) {
cur = cur.right;
} else {
prev = cur.left;
while (prev.right != null && prev.right != cur)
prev = prev.right;
if (prev.right == null) {
prev.right = cur;
cur = cur.left;
} else {
// Modification on get the traversal list
printPostTraverse(traverseList, cur.left, prev);
prev.right = null;
cur = cur.right;
}
}
}
return traverseList;
}
于 2017-07-25T19:29:53.270 回答