二叉树前序遍历的递归过程

飘到心海发布于 2010-05-29 11:57， 1654 次点击

void PreOrderTree(BiTNode *bt)
{
    if(bt!=NULL)
    {
        printf("%c ",bt->data);
        PreOrderTree(bt->lchild);
        PreOrderTree(bt->rchild);
    }

}
大家可不可以解释下这个函数的递归过程，一直不理解。
如果我把代码最后加上这个语句：

程序代码：

void PreOrderTree(BiTNode *bt)
{
    if(bt!=NULL)
    {
        printf("%c ",bt->data);
        PreOrderTree(bt->lchild);
        PreOrderTree(bt->rchild);
    }
getch（）；

}

那么当运行输出的时候会有问题，归根到底还是对运行过程不了解，希望高手指教。现行谢过。

12 回复

飘到心海2010-05-29 18:39

没人知道还是我的问题太弱智啊？

xichong2010-05-29 21:06

下面这个是非递归的前序遍历，实际上也是对递归程序执行过程过程的模拟：

void PreOrderTraverse(BiTree T)//先序遍历
{
    SqStack S;
    initialStack(&S);
    Push(&S,T);
    while(!StackEmpty(&S))//出栈顺序：根->左->右
    {
        Pop(&S,&T);
        Visit(T);
        if(T->rchild!=NULL)
            Push(&S,T->rchild);//右子树进栈（后出栈）
        if(T->lchild!=NULL)
            Push(&S,T->lchild);//左子树进栈（先出栈）
    }
}

2010-05-30 10:15

试想一下每次都要执行getch（）函数这样递归怎么能执行结束呢。

飘到心海2010-05-30 14:42

回复 4楼 LegendofMine

这个递归是回溯法吧？

寒风中的细雨2010-05-30 16:54

对会返回到根

飘到心海2010-05-30 17:59

程序在什么时候会运行到getch（）函数？

寒风中的细雨2010-05-30 18:30

分两种情况
一种是为空则直接就执行getch()
另一种是不为空则在左右孩子遍历完成回溯到该层就相当于程序的顺序执行从上到下

飘到心海2010-05-30 20:06

为空的时候直接执行getch（）。执行完之后再回溯到上一层对吧？

#10

寒风中的细雨2010-05-30 20:56

恩

#11

飘到心海2010-05-30 21:00

还是有点乱，有没有好的方法可以把递归的过程一目了然？

#12

寒风中的细雨2010-05-30 21:12

和潜水差不多吧潜下去啦还得冒起来

#13

飘到心海2010-05-30 21:40

这个递归的出口是什么啊，是不是最后回溯到根节点就退出了？