二叉树之Morris遍历

  • 递归理解以及morris遍历
  • 由morris遍历改成前序遍历
  • 由morris遍历改成中序遍历
  • 由morris遍历改成后续遍历
  • 完整测试代码

递归理解以及morris遍历
1 2 3 4 5 6 7 8 static void rec(Node head) { if (head == null) return; System.out.print(head.value + " "); //这里打印就是前序遍历 rec(head.left); System.out.print(head.value + " "); //这里打印就是中序遍历 rec(head.right); System.out.print(head.value + " "); //这里打印就是后续遍历 }

这是我们用递归写的三种遍历方法，如果是下面的例子，上面程序输出如下：

这里写图片描述

程序输出:
1 1 2 4 8 8 8 4 4 2 5 5 9 9 9 5 2 1 3 6 10 10 10 6 6 3 7 11 11 11 7 7 3 1
  • 可以看到，每一个结点都会被访问三次，也就是说，访问的过程中，每一个结点都会经过三次；
  • 一个结点如果没有parent指针或者我们在非递归遍历中使用栈，是不能回到它的父节点的；
  • 而morris就是借助叶子结点的空闲指针帮助我们想办法回到父亲结点，省去了递归的空间，或者栈的空间，达到O(1)空间；

每个结点来到三次:

在这里插入图片描述

下面介绍morris遍历规则(现在和前、中、后序无关，就是morris序):

这里写图片描述

流程看下图的举例:

这里写图片描述

这里写图片描述

按照上面的解释可以完全写出下面的morris遍历过程(没有打印)：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 static void morris(Node head){ if(head == null)return; Node cur = head; Node mostRight = null;//左子树上最右的结点 while(cur != null){ mostRight = cur.left; //cur的第一个左结点 if(mostRight != null){ //如果左子树不为空 while(mostRight.right != null && mostRight.right != cur){ //找到最右边的结点 有两种情况 mostRight = mostRight.right; } if(mostRight.right == null){ //第一次来到这个结点 满足第二大条中的第一条 mostRight.right = cur; cur = cur.left; continue; // cur = cur.left 直接结束所有的 }else { //第二次来到这个结点 满足第二大条中的第二条 mostRight.right = null; } } cur = cur.right; //包括两种情况的 左子树为空和第二次来到这个结点 } }

由morris遍历改成前序遍历

需要注意几点:

  • 首先可以肯定是第一次来到这个结点的时候打印，所以是当mostRight.right == null(第一次来的时候，打印当前的cur)；
  • 其次，如果一个结点没有左子树，相当于只会来到结点一次，就直接打印一遍就可以了；
  • 其实这样的做法等同于在递归的时候把打印的行为放在第一次来到这个结点的时候；
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 //先序遍历 static 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.print(cur.value + " "); //先序是第一次来到这个结点的时候打印 cur = cur.left; continue; }else { mostRight.right = null; } }else { //如果一个结点没有左子树 相当于只会来到这个结点一次 直接打印，然后往右走 System.out.print(cur.value + " "); } cur = cur.right; } System.out.println(); }

由morris遍历改成中序遍历

中序更加简单:

  • 如果一个结点有左子树，那么我打印的时机是我遍历完左子树之后的打印，也就是第二次来到这个结点时候打印，也就是mostRight.right = cur的时候打印；
  • 如果一个结点没有左子树，那么本来也要打印一下，打印完就往右边窜了；
  • 本质就是不论怎么样要处理玩左子树才打印根结点；
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 //中序遍历 static 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.print(cur.value + " ");//这里包括两种情况 没有左子树和有左子树的第二次来到这里打印 cur = cur.right; } System.out.println(); }

由morris遍历改成后续遍历

后续遍历比较麻烦: 因为morris只会来到一个结点两次，但是递归会来到一个结点三次:

主要看以下几点:

  • 我们只关心那些有左子树，也就是会到一个结点两次的结点；
  • 逆序打印有左子树结点的左子树的右边界；
  • 最后打印整棵树的右边界的逆序；

这里写图片描述
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 //morris后续 static void morrisPos(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; printEdge(cur.left); //打印左子树的右边界 } } cur = cur.right; } printEdge(head); //最后打印整棵树的右边界 System.out.println(); } //打印边界 static void printEdge(Node head) { //先逆序边界 Node tail = reverseEdge(head); //打印 Node cur = tail; while(cur != null){ System.out.print(cur.value + " "); cur = cur.right; } //再逆序回来 reverseEdge(tail); } //有点类似链表的逆序 static Node reverseEdge(Node cur) { Node pre = null; Node next = null; while(cur != null){ next = cur.right;//先保存下一个 cur.right = pre; pre = cur; cur = next; } return pre; }

完整测试代码(例子就是上面的例子):
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 ``` public class Morris { static class Node { public int value; public Node left; public Node right; public Node(int value) { this.value = value; } } static Node createTree(int[] arr, int i) { if (i >= arr.length

测试结果:
这里写图片描述