线索二叉树

// 不做任何访问的遍历
void traverse(Btree T)
{
  if(!T){
    // ①
    traverse(T->lchild);
    // ②此处为访问左孩子递归返回地址
    traverse(T->rchild);
    // ③此处为访问右孩子递归返回地址 
  }
}

// 可以看出递归结束条件是 T == NULL

阿Q觉得有意思的地方就在于：
1)若T经过左支变为NULL，那返回上一层递归 即:返回到上一层的②位置处（那接着访问上一层的右孩子）
2)若T经过右支变为NULL，那返回上一层递归 即:返回到上一层的③位置处（这一层又结束了），接着就有两种情况：
一个就是从上两层的左支递归来的（那上两层接着递归右孩子即可）
另一个就是上两层右支 递归来的（那此时这一层又结束了，直到是从左支递归下来的为止）

阿Q再去思考线索二叉树的建立就很简单了。

void traverse(Btree P, Btree Ptr)
{
  if(!P){
    // ①
    traverse(P->lchild, Ptr);
    // ②
    Ptr = P;
    traverse(P->rchild, Ptr);
    // ③
  }
}

Ptr 和 P 都走了一遍路径，只是 P 走的比 Ptr 快了一步。（两者都经过了中序遍历，遍历结果是一样的）。