前序
//二叉树遍历
/*
* 前序遍历：根左右
* 中序遍历：左根右
* 后序遍历：左右根
* 层序遍历：从上往下、从左往右
*
* 递归遍历：使用递归方法遍历
* 迭代遍历：使用迭代方法实现递归函数，与递归等价
* morris遍历
* */
public class P32 {
/*
* 1
* / \
* 2 3
* / \
* 4 5
* / \
* 6 7
* */
public static void main(String[] args) {
TreeNode node7 = new TreeNode(7, null, null);
TreeNode node6 = new TreeNode(6, null, null);
TreeNode node5 = new TreeNode(5, node6, node7);
TreeNode node4 = new TreeNode(4, null, null);
TreeNode node3 = new TreeNode(3, null, null);
TreeNode node2 = new TreeNode(2, node4, node5);
TreeNode node1 = new TreeNode(1, node2, node3);
morris(node1);
}
//线索二叉树 主要是降低空间复杂度
/*
* 叶子节点下面是有空闲指针，可以用来存放数据，空闲指针数量 = 节点数量+1
* 线索二叉树，可以这样理解：当前在4节点，怎样直接找到5节点？以前是需要回退到2节点才能找到5节点
* 现在是用线索连起来，直接从4找到5
*
* 1
* / \
* 2 3
* / \ \
* 4 --- 5 |
* / \ |
* 6 --- 7
* 不同的序连的方式不同，此图仅参考
* */
//前序-morris遍历
//1-2-4-5-6-7-3
public static void morris(TreeNode cur){
if(cur == null){
return;
}
TreeNode mostRight = null; //前驱节点，相对当前cur的最积接近的点(7节点)
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; //让前驱节点右指针指向当前节点，如7指向1
System.out.println(cur.val);
cur = cur.left; //左移，开始下一个循环，继续找左子树
continue;
}else{ //即mostRight.right == cur 删除线索指针
mostRight.right = null; //为了不破坏二叉树结构
}
}else{
System.out.println(cur.val);
}
cur = cur.right; //找右树的前驱节点
}
}
/*
* 总结步骤：
* 1找到前驱节点7，维护好7到1的线索，
* 打印自己1，
* 然后左移到2，2同样找前驱节点4，维护好4到2的线索
* 打印自己2
* 然后左移到4，4没有左子树了，打印自己
* 4的左边找完就找右边，然后因为4的right是2，所以cur=cur.right之后，cur就是2
* 然后发现前驱节点4的right == cur ，就删除前驱节点的线索指针
* 2的左边找完就找右边（就开始了上面的循环步骤了），cur就为5，找5的前驱节点6，打印自己，并左移到6
* 6没有左子树，打印自己，6.right为5，再次回到5，
* 5发现前驱节点6的right是自己，删除线索，cur=5.right 即cur=7
* 7没有左子树，输出自己，然后cur=7.right，即1
* 1发现前驱节点的right是自己，删除线索，然后cur=1.right，即cur=3
* 3发现没有左子树，输出自己
* cur=3.right，为null，退出了while
*
* */
static class TreeNode{
int val;
TreeNode left;
TreeNode right;
int deep;
TreeNode(){}
TreeNode(int val){
this.val = val;
}
TreeNode(int val, TreeNode left, TreeNode right){
this.val = val;
this.left = left;
this.right = right;
}
}
}
中序，仅仅是打印位置不同了
//4-2-6-5-7-1-3
public static void morrisMid(TreeNode cur){
if(cur == null){
return;
}
TreeNode mostRight = null; //前驱节点，相对当前cur的最积接近的点(7节点)
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; //让前驱节点右指针指向当前节点，如7指向1
cur = cur.left; //左移，开始下一个循环，继续找左子树
continue;
}else{ //即mostRight.right == cur 删除线索指针
mostRight.right = null; //为了不破坏二叉树结构
}
}else{
}
System.out.println(cur.val);
cur = cur.right; //找右树的前驱节点
}
}
/**
* 总结步骤：
* 1找到前驱节点7，建立7到1的线索
* 然后左移到2，同样找前驱节点4，建立4到2的线索
* 然后左移到4，4的左子树为null，输出自己4，让cur=4.right，即cur现在为2
* 然后2发现前驱节点的right是自己，删除线索，打印自己2，让cur=2.right，即cur=5
* 5找前驱节点6，建立6到5的线索
* 然后左移到6,6的左子树是null，打印自己6，让cur=6.right，即cur是5
* 然后5发现前驱节点的right是自己，删除线索，打印自己5，让cur=5.right，即cur=7
* 然后7的左子树为null，打印自己7，让cur=7.right，即cur=1，
* 然后1发现前驱节点的right是自己，删除线索，打印自己1，让cur=1.right，即cur=3
* 3的左子树为空，cur=3.right，为null，结束
*/
网友评论