morris遍历树

本文主要是介绍morris遍历树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

    public class Node{Node left;Node right;int val;}public void morris(Node head){if(head == null){ return;}Node cur = head;Node mostRight = null;while(cur != null){mostRight = cur.left;if(mostRight != null){//如果当前cur有左子树，找到cur左子树上最右的节点while(mostRight.right != null && mostRight.right != cur){mostRight = mostRight.right;}if(mostRight.right == null){//如果right为null,则指向cur.mostRight.right = cur;//cur向左移动cur = cur.left;continue;//继续判断cur}else{mostRight.right = null;}}//cur没有左子树cur向右移动，或者cur左子树上最右节点已经指向了cur，cur向右移动。cur = cur.right;}}//先序遍历对于cur只能到达一次的节点（无左子树的节点），cur到达时直接打印。//对于cur可以到达两次的节点（有左子树的节点），cur第一次到达时打印，第二次到达时不打印。public void morrisPre(Node head){if(head == null){return;}Node cur = head;Node mostRight = null;while(cur != null){mostRight = cur.left;if(mostRight != null){while(mostRight.right != null && mostRight.right != cur){mostRight = mostRight.right;}if(mostRight.right == null){mostRight.right = cur;System.out.println(cur.val);cur = cur .left;continue;}else{mostRight.right = null;}}else{System.out.println(cur.val);}cur = cur.right;}}//中序遍历对于cur只能到达一次的节点，直接打印。//对于cur可以到达两次的节点，cur第一次到达时不打印，第二次到达时打印public void morrisIn(Node head){if(head == null){ return;}Node cur = head;Node mostRight = null;while(cur != null){mostRight = cur.left;if(mostRight != null){while(mostRight.right!=null&&mostRight.right!=cur){mostRight = mostRight.right;}if(mostRight.right == null){mostRight.right = cur;cur=cur.left;continue;}else{mostRight.right = null;}}System.out.println(cur.val);cur = cur.right;}}//后续遍历//1.对于cur只能到达一次的节点直接跳过。//2.对于cur可以到达两次的任何一个节点X，cur第一次到达X时没有打印行为，当第二次到达X的时候，逆序打印X左子树的有边界.//3.cur遍历完成后，逆序打印整棵树的有边界public static void printEdge(Node head){Node tail = reverseEdge(head);Node cur = tail;while(cur != null){System.out.println(cur.val+ " ");cur = cur.right;}reverseEdge(tail);}public static Node reverseEdge(Node from){Node pre = null;Node next = null;while(from != null){next = from.right;from.right = pre;pre = from;from = next;}return pre;}public void mirrisPos(Node head){if(head == null){return;}Node cur = head;Node mostRight = cur.left;while(cur!=null) {if (mostRight != null) {while (mostRight.right != null && mostRight.right != cur) {mostRight = mostRight.right;}if (mostRight.right == null) {mostRight.right = cur;cur = cur.left;continue;}else{mostRight.right = null;printEdge(cur.left);}}cur = cur.right;}printEdge(head);}

 

这篇关于morris遍历树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---