UC知道关于二叉树遍历的递归算法
来源：百度知道 编辑：UC知道 时间：2024/05/13 09:26:50
比如先序
先序
void trav(node* p){ 1
if(!p) return; 2
cout<<data; 3
if(p->lchild) pretrav(p->lchild); 4
if(p->rchild) pretrav(p->rchild); 5
}
按函数内应该是顺序向下执行的，那么执行到4行的时候进行递归,那么按这样下去应该永远到不了第5行，哪位能够给我讲解下这方面的问题,我对递归了解的比较少.
先序
void trav(node* p){ 1
if(!p) return; 2
cout<<data; 3
if(p->lchild) pretrav(p->lchild); 4
if(p->rchild) pretrav(p->rchild); 5
}
按函数内应该是顺序向下执行的，那么执行到4行的时候进行递归,那么按这样下去应该永远到不了第5行，哪位能够给我讲解下这方面的问题,我对递归了解的比较少.
代码写错了，要是递归的话，45行的函数应该是 pretrav;
这是深度遍历。
逻辑很简单啊：
比如一个二叉树：
.............A
.........../...\
..........B.....C
........./.\......\
........D...E......F
......./
......G
第一次函数调用，传入节点A。
执行到4，左子树非空，
..调用 trav函数，传入B，再执行到 第四步 B的左子树非空，
....调用 trav函数，传入 D，再执行到第四步 D的左子树非空
......调用 trav函数，传入 G。执行到第四步，
......左子空，跳过继续，执行第五步，
......右子空，跳过继续。返回到
....D节点的第五步，D的右子空 跳过继续
..B节点的第五步，B右子非空
....调用 trav函数，传入E,执行到第四步
....左子空，跳过继续，执行第五步，
....右子空，跳过继续。返回到
..B节点返回
A节点第五步，右子非空
..调用trav，传入C，执行到第四步
..C的左子空，跳过继续
..C的右子非空，
....调用trav，传入 F,执行到第四步
....左子空，跳过继续，执行第五步，
....右子空，跳过继续。返回到
..c执行完，返回
A执行完，整个遍历完成，返回