线索二叉树
// 不做任何访问的遍历
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 快了一步。(两者都经过了中序遍历,遍历结果是一样的)。