对递归的思考

线索二叉树

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

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


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

指针T所走的路径

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

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

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

暂无评论

发送评论 编辑评论


				
上一篇
下一篇