1) n 个结点的二叉链表中含有 n+1
【公式 2n-(n-1)=n+1】 个空指针域。利用二叉链表中的空指针域，存放指向
该结点在某种遍历次序下的前驱和后继结点的指针（这种附加的指针称为"线索"）
2) 这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树(Threaded BinaryTree)。根据线索性质
的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种
3) 一个结点的前一个结点，称为
前驱
结点
4) 一个结点的后一个结点，称为后继结点
！！！线索化二叉树每个节点都用上了左右指针，故一个节点左右指针连的要么是子节点要么是前驱或者后继，不可能滞空，故借此可以讨论情况。
1.前序线索化二叉树
public void turnToPre(ThreadedNode temp) {
if(temp == null) {
return ;
}
if(temp.left == null) {
temp.left = pre;
temp.leftType = true;
}
if(pre != null && pre.right == null) {
pre.right = temp;
pre.rightType = true;
}
pre = temp;
//只有当类型为false时才进入，否则进入死循环
if(!temp.leftType) {
turnToPre(temp.left);
}
if(!temp.rightType) {
turnToPre(temp.right);
}
}
前序遍历线索化二叉树
//前序遍历线索二叉树
public void preOrderThreaded() {
ThreadedNode temp = root;
while(temp != null) {
System.out.print(temp.data + " ");
//如果存在左子节点就往左走，否则往右走，此时右指针一定是前序遍历的下一个节点
if(!temp.leftType) {
temp = temp.left;
}else {
temp = temp.right;
}
}
}
2.中序线索化二叉树
public void turnToIn(ThreadedNode temp) {
if(temp == null) {
return ;
}
turnToIn(temp.left);
if(temp.left == null) {
temp.left = pre;
temp.leftType = true;
}
if(pre != null && pre.right == null) {
pre.right = temp;
pre.rightType = true;
}
pre = temp;
turnToIn(temp.right);
}
中序遍历线索化二叉树算法一
//中序遍历线索二叉树算法一
public void inOrderThreaded1() {
ThreadedNode temp = root;
while(temp != null) {
while(!temp.leftType) {
temp = temp.left;
}
//此时temp指向第一个没有左子节点的节点，故他就是首先输出的节点
System.out.print(temp.data + " ");
//此时tmep要么没有右子节点而右指针指向后继节点，即其父节点；要么就是有右子节点并指向它，此时就不能直接输出而需要判断该右子节点有没有左子节点了。
while(temp.rightType) {
temp = temp.right;
System.out.print(temp.data + " ");
}
temp = temp.right;
}
}
中序遍历线索化二叉树算法二
//中序遍历线索二叉树算法二
public void inOrderThreaded2() {
ThreadedNode temp = root;
while(temp != null) {
if(!temp.leftType) {
temp = temp.left;
}else {
System.out.print(temp.data + " ");
//如果temp的右指针是线索指针，则需要先走一步，否则会陷入死循环
if(temp.rightType) {
temp = temp.right;
System.out.print(temp.data + " ");
}
temp = temp.right;
}
}
}
3后序线索化二叉树
//转化为后序线索二叉树
public void turnToPost(ThreadedNode temp) {
if(temp == null) {
return ;
}
turnToPost(temp.left);
turnToPost(temp.right);
if(temp.left == null) {
temp.left = pre;
temp.leftType = true;
}
if(pre != null && pre.right == null) {
pre.right = temp;
pre.rightType = true;
}
pre = temp;
}
后序遍历线索化二叉树
/**
* 后续线索化遍历
*/
public void threadedListPost(){
MyThreadedNode node = root;
//找到第一个线索化的结点
while(node!=null && node.getLeftType()==0){
node = node.getLeft();
}
while(node!=null){
//后继已经线索化的直接打印
if(node.getRightType()==1){
System.out.println(node);
preNode = node;
node = node.getRight();
}else{
//这是一个子树的根节点，此时要区分：
//如果当前结点的右子节点是前一个被打印结点,即右子树回调的，则直接打印
if(node.getRight()==preNode){
System.out.println(node);
if(node==root){
return;
}
preNode = node;
node = node.getParent();
}else {
//如果当前结点的右子节点不是前一个被打印结点,则是左子树回调回到的父节点，则去他的右子树继续循环
node = node.getRight();
while(node!=null && node.getLeftType()==0){
node = node.getLeft();
}
}
}
}
}
