//二叉树遍历
/*
* 前序遍历：根左右
* 中序遍历：左根右
* 后序遍历：左右根
* 层序遍历：从上往下、从左往右
*
* 递归遍历：使用递归方法遍历
* 迭代遍历：使用迭代方法实现递归函数，与递归等价
* morris遍历
* */
public class P33 {
/*
* 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);
// morrisMid(node1);
morrisPos(node1);
}
//线索二叉树 主要是降低空间复杂度
/*
* 叶子节点下面是有空闲指针，可以用来存放数据，空闲指针数量 = 节点数量+1
* 线索二叉树，可以这样理解：当前在4节点，怎样直接找到5节点？以前是需要回退到2节点才能找到5节点
* 现在是用线索连起来，直接从4找到5
*
* 1
* / \
* 2 3
* / \ \
* 4 --- 5 |
* / \ |
* 6 --- 7
* 不同的序连的方式不同，此图仅参考
* 遍历线索二叉树就是边构建边删除
* */
//后序-morris遍历
/*
* 原理：
* 如果一个节点的前驱节点.right指向自己，就要输出前驱节点，并断开线索
* 所以4指向2，要输出4，然后断开指向
* 6指向5，输出6，然后断开指向
* 但是7是指向1，这个时候就要把2-5-7这个链表反转输出为7-5-2
* 3右指针是空，也是反转链表输出3-1
* 反转的链表都是right构成的链
* */
//4-6-7-5-2-3-1
public static void morrisPos(TreeNode cur){
if(cur == null){
return;
}
TreeNode root = cur;
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; //为了不破坏二叉树结构
printNode(cur.left);
}
}
cur = cur.right; //找右树的前驱节点
}
printNode(root);
}
/*
* 1找到前驱节点7，建立7到1的线索，
* 然后左移到2，同样找前驱节点4，建立4到2的线索
* 然后左移到4，4的左子树为null，让cur=4.right，即cur现在是2
* 然后删除4到2的线索，并执行打印cur.left的节点，即打印头结点为4的链表，
* 因为4没有左右孩子了，之前已经断开，所以反转还是4，然后输出这个链表，只有4一个元素，再还原链表不破坏树结构
* 然后左边处理完毕，让cur=cur.right，开始右树，现在cur为5
* 5找到前驱节点6，建立6到5的线索
* 然后左移到6，6的左子树为null，让cur=6.right，即cur现在是5
* 然后删除6到5的线索，并执行打印cur.left的节点，即打印头结点为6的链表
* 6因为没有左右孩子了，之前已经断开，所有反转还是6，然后输出这个链表，只有6一个元素，再还原链表不破坏树结构
* 然后左边处理完毕，让cur=cur.right，开始右树，现在cur为7
* 7的左子树为null，让cur=7.right，即cur现在是1
* 然后删除7到1的线索，并执行打印cur.left的节点，即打印头结点为2的链表
* 只反转右节点，所有链表变为7-5-2，打印7-5-2，再还原链表不破坏树结构
* 然后左边处理完毕，让cur=cur.right，开始右树，现在cur为3
* 因为3的左节点为null，然后cur=cur.right，cur现在为null，退出了while（垂直投影最后的节点就是结束while的）
* 然后以事先备份的root作为头节点执行打印（因为现在cur是3，无办法再回到root，所以事先备份）
* 反转链表1-3，输出3-1，结束
* */
//负责打印
private static void printNode(TreeNode head) {
TreeNode tail = reverse(head); //反转链表
while(tail != null){
System.out.println(tail.val);
tail = tail.right;
}
reverse(tail);
}
//反转链表，P1说过
private static TreeNode reverse(TreeNode head) {
TreeNode prev = null;
TreeNode curr = null;
TreeNode next = null;
curr = head;
while(curr != null){
next = curr.right;
curr.right = prev;
prev = curr;
curr = next;
}
return prev;
}
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;
}
}
}
网友评论