线索二叉树：一棵n节点二叉树有2n个指针，每一个节点有一个指针指向它，除了根节点。因此有n-1个有效指针。所以有n+1个空指针。线索二叉树意义就是要将空闲指针利用起来。将空指针指向下一个要遍历的节点，即可降低空间复杂度。我们称利用起来的空闲指针称为线索。
正常来说，我们使用最多的是中序线索二叉树。可以很快找到前驱和后续节点。在中序遍历中，他的遍历序列即为垂直方向上的投影，所以我们知道节点的前驱就是左子树最右边的节点。根据这个特点可以编写线索二叉树的线索化。当然，在使用morris遍历时不要忘记去线索化，因为线索化后的二叉树空指针被线索化了，破坏了二叉树原来的结构，需要还原。
前序遍历遍历顺序为根左右。
上代码：
//21遍历二叉树-morris
public class BinaryTree21 {
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);
morrisPre(node1);
}
//前序
public static void morrisPre(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 == cur
mostRight.right = null;
}
} else {
System.out.println(cur.val);
}
cur = cur.right;
}
}
}
结果：
1245673
中序遍历遍历顺序为左根右
上代码：
//21遍历二叉树-morris
public class BinaryTree21 {
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);
// morrisPre(node1);
morrisMid(node1);
}
//中序
public static void morrisMid(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 == cur
mostRight.right = null;
}
} else {
// System.out.println(cur.val);
}
System.out.println(cur.val);
cur = cur.right;
}
}
}
结果：4265713
后序遍历遍历顺序为左右根
上代码：
//21遍历二叉树-morris
public class BinaryTree21 {
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);
morrisLast(node1);
}
//后序
public static void morrisLast(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 == cur
mostRight.right = null;
printNode(cur.left);
}
}
cur = cur.right;
}
printNode(root);
}
private static void printNode(TreeNode head) {
TreeNode tail = reverse(head);
while (tail!=null){
System.out.println(tail.val);
tail=tail.right;
}
reverse(tail);//恢复结构
}
private static TreeNode reverse(TreeNode head) {
TreeNode prev = null,curr,next;
curr = head;
while (curr!=null){
next = curr.right;
curr.right = prev;
prev=curr;
curr = next;
}
return prev;
}
}
结果：
4675231
