morris前序

  1. //morris前序
  2.     public void morrisPreOrder(Node head) {
  3.         Node cur1 = head;
  4.         Node cur2 = null;//左子节点
  5.         while (cur1 != null) {
  6.             cur2 = cur1.left;//当前节点的左子节点
  7.             if (cur2 != null) {
  8.                 //循环遍历到左子节点的最右子节点
  9.                 while (cur2.right != null && cur2.right != cur1) {
  10.                     cur2 = cur2.right;
  11.                 }
  12.                 //如过最右节点未指向cur1，则使之指向cur1,并略过后续代码;
  13.                 if (cur2.right == null) {
  14.                     cur2.right = cur1;
  15.                     System.out.print(cur1.value + " ");//遇见父节点，先打印父节点
  16.                     cur1 = cur1.left;
  17.                     continue;
  18.                 } else {
  19.                     //如过最右节点已指向cur1，恢复，则使之指向null,
  20.                     cur2.right = null;
  21.                 }
  22.             } else {
  23.                 //如果cur1.left 为null,说明没有左子节点,在切换到右子树之前先打印父节点
  24.                 System.out.print(cur1.value + " ");
  25.             }
  26.             cur1 = cur1.right;
  27.         }
  28.         System.out.println();
  29.     }

morris中序

  1.      //morris中序
  2.     public void morrisInOrder(Node head) {
  3.         Node cur1 = head;
  4.         Node cur2 = null;//左子节点
  5.         while (cur1 != null) {
  6.             cur2 = cur1.left;//当前节点的左子节点
  7.             if (cur2 != null) {
  8.                 //循环遍历到左子节点的最右子节点
  9.                 while (cur2.right != null && cur2.right != cur1) {
  10.                     cur2 = cur2.right;
  11.                 }
  12.                 //如过最右节点未指向cur1，则使之指向cur1,并略过后续代码;
  13.                 if (cur2.right == null) {
  14.                     cur2.right = cur1;
  15.                     cur1 = cur1.left;
  16.                     continue;
  17.                 } else {
  18.                     //如过最右节点已指向cur1，恢复，则使之指向null,
  19.                     cur2.right = null;
  20.                 }
  21.             }
  22.             //如果cur1.left 为null,则说明没有左子树,则开始打印父节点;
  23.             System.out.print(cur1.value + " ");
  24.             cur1 = cur1.right;
  25.         }
  26.         System.out.println();
  27.     }

morris后序

  2.     //morris后序
  3.     public void morrisPostOrder(Node head) {
  4.         Node cur1 = head;
  5.         Node cur2 = null;//左子节点
  6.         while (cur1 != null) {
  7.             cur2 = cur1.left;//当前节点的左子节点
  8.             if (cur2 != null) {
  9.                 //循环遍历到左子节点的最右子节点
  10.                 while (cur2.right != null && cur2.right != cur1) {
  11.                     cur2 = cur2.right;
  12.                 }
  13.                 //如过最右节点未指向cur1，则使之指向cur1,并略过后续代码;
  14.                 if (cur2.right == null) {
  15.                     cur2.right = cur1;
  16.                     cur1 = cur1.left;
  17.                     continue;
  18.                 } else {
  19.                     //如过最右节点已指向cur1，恢复，则使之指向null,
  20.                     cur2.right = null;
  21.                     printEdge(cur1.left);
  22.                 }
  23.             }
  24.             cur1 = cur1.right;
  25.         }
  26.         printEdge(head);
  27.         System.out.println();
  28.     }
  30.     //打印节点
  31.     public void printEdge(Node head) {
  32.         Node tail = reverse(head);
  33.         Node cur = tail;
  34.         while (cur != null) {
  35.             System.out.print(cur.value + " ");
  36.             cur = cur.right;
  37.         }
  38.         //恢复链表
  39.         reverse(tail);
  40.     }
  42.     //反转节点的右子节点链
  43.     public Node reverse(Node head) {
  44.         Node pre = null;
  45.         Node next = null;
  46.         while (head != null) {
  47.             next = head.right;
  48.             head.right = pre;
  49.             pre = head;
  50.             head = next;
  51.         }
  52.         return pre;
  53.     }

测试

  1. /**
  2.  * @Description:遍历二叉树的神级方法 morris
  3.  * @Author: lizhouwei
  4.  * @CreateDate: 2018/4/14 17:15
  5.  */
  6. public class Chapter3_5 {
  8.     //测试
  9.     public static void main(String[] args) {
  10.         Chapter3_5 chapter = new Chapter3_5();
  11.         int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
  12.         Node head = NodeUtil.generTree(arr, 0, arr.length - 1);
  13.         System.out.print("morris中序遍历：");
  14.         chapter.morrisInOrder(head);
  15.         System.out.print("非递归中序遍历：");
  16.         NodeUtil.inOrder(head);
  17.         System.out.println();
  18.         System.out.print("morris前序遍历：");
  19.         chapter.morrisPreOrder(head);
  20.         System.out.print("非递归前序遍历：");
  21.         NodeUtil.preOrder(head);
  22.         System.out.print("morris后序遍历：");
  23.         chapter.morrisPostOrder(head);
  24.         System.out.print("非递归后序遍历：");
  25.         NodeUtil.postOrder(head);
  26.     }
  27. }