线索化二叉树

二叉树的线索化是指给二叉树加左右两个指针域（称为线索），可以提高空间利用率。

一般先规定好遍历顺序，确定每个结点的前驱和后继即遍历得到的顺序中前后结点，下面都以中序遍历为例。

规定：左指针域指向该结点的左子结点（或前驱），右指针指向该结点的右子结点

中序遍历得到的第一个结点为首结点，前驱为NULL，得到的最后一个结点为尾结点，后继为NULL。

线索化二叉树的建立代码如下：

 1   public void threadNode(Node node)
 2         {
 3             //leftType，rightType为1则表示左（右）子结点不存在，为前驱（后继）
 4             if (node == null)
 5             {
 6                 return;
 7             }
 8             //线索化左子树
 9             threadNode(node.left);
10             if (node.left == null)
11             {
12                 //让当前结点的左指针指向前驱结点
13                 node.left = pre;
14                 node.leftType = 1;
15             }
16             if (pre != null && pre.right == null)
17             {
18                 //前驱结点右指针指向当前结点
19                 pre.right = node;
20                 pre.rightType = 1;
21             }
22             //每处理一个结点，前驱结点前进（让前驱结点为当前结点）
23             pre = node;
24             threadNode(node.right);
25         }

中序遍历线索二叉树：先找到首结点。对于每一个结点，都要判断其左右子结点是否存在，如果存在则继续递归左-中-右

和中序遍历普通二叉树不同的是，如果不存在左右子结点，则进入其后继结点

代码如下（尚硅谷老师的遍历代码思想有点难懂，要多看）

 1 public void list()
 2         {
 3             Node node = root;
 4             while (node != null)
 5             {
 6                 //如果结点存在左子结点 则继续往下找
 7                 while (node.leftType == 0)
 8                 {
 9                     node = node.left;
10                 }//跳出while循环表示得到了一个没有左子结点的结点
11                 Console.WriteLine(node.tostring());//打印结点
12                 //如果结点右边不存在子节点，只有后驱结点 则打印后驱结点
13                 while (node.rightType == 1)
14                 {
15                     node = node.right;//结点移到后驱结点
16                     Console.WriteLine(node.tostring());//打印结点
17                 }//跳出while循环表示该节点存在右子结点
18                 node = node.right;//指向结点右子结点
19             }
20         }