二叉树遍历之Morris

优点 时空复杂度由 O(n) ——>O(1)

---

线索二叉树的实现

• 特点是每个叶子结点是存在空闲指针的（n 个节点，每个节点都有2n 个指针），但是每个节点只有一个被指向针（除了根节点），总共利用了（n-1）个指针

• 有（n+1）个指针可以利用起来，作为索引的线索针

  

• 一是找到前驱节点，而是维护线索

• 主要是要建立中序线索二叉树，线索利用完需要断开，不能影响二叉树的结构

前、中遍历的Morris 实现

Morris 遍历框架

• 以中序遍历为基础，在左子树遍历，不断建立线索指针

public static void Morirspre(TreeNode cur){
		if(cur==null)  return ;
		//找到中序遍历中的前驱节点
		TreeNode 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;
        }
   		}else{
   		//		cur=cur.right;
   		}
   		cur=cur.right;
   }
}

• 不同的遍历实现实际上是在不同的地方选择打印

前序遍历

public static void Morirspre(TreeNode cur){
		if(cur==null)  return ;
		//找到中序遍历中的前驱节点
		TreeNode 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;

   }
}

中序遍历

public static void Morirsmid(TreeNode cur){
		if(cur==null)  return ;
		//找到中序遍历中的前驱节点
		TreeNode 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;
        	}
   		}else{
   			}
   			System.out.println(cur.val);
   		 	cur=cur.right;
   }
}

后续遍历实现

原理：框架不变 ，但是打印的时机有所变化，需要去找规律

当建立线索指针后，前驱节点刚好变为cur的左子节点时则必须打印

（比如图中 4—2 ，5—6出现的情况）

另外还存在一个单链表 如图

当遍历到的左子节点干好事当前节点的前驱节点 时 ，需要构建单链表进行打印

因为右子树需要考虑，所以要保存根节点

public static void Morirspost(TreeNode cur){
		if(cur==null)  return ;
		//找到中序遍历中的前驱节点
		TreeNode root = cur;   //保存 根节点
		TreeNode 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;
            // 该时刻为打印链表时刻
           	printNode(cur.left);
        	}
   		}
   		 	cur=cur.right;
   }
   printNode(root);
}

public static void printNode(TreeNode head){
		TreeNode tail = reverse(head);
		while(tail!=null){
			System.out.print(tail.val);
			tail=tail.right;
		}
		reverse(tail);
}

public static TreeNode reverse(TreeNode head){
		TreeNode pre=null,next;
		while(){
			next=head.right;
			head.right=pre;
			pre=head;
			head=next;
		}
		return pre;
}