UC知道关于二叉树先序遍历的递归算法问题
来源：百度知道 编辑：UC知道 时间：2024/06/15 16:12:18
二叉树先序遍历算法如下：
void Preorder (BiTree T,
void( *visit)(TElemType& e))
{ // 先序遍历二叉树
if (T) {
visit(T->data); // 访问结点
Preorder(T->lchild, visit); // 遍历左子树
Preorder(T->rchild, visit);// 遍历右子树
}
}
我就不明白，当遍历到某只有右子树的结点时，其lchild为空，NULl作为参数递归调用到if语句，if语句条件不成立，结束递归，然后程序是怎么执行的。请学过数据结构的前辈或者电脑高手给我讲讲递归调用啊！数据结构中最重要的树和图中好多递归问题，全部搞不明白，关于程序的出口接口什么的。这个问题已经困扰我好久了。再次拜托！
void Preorder (BiTree T,
void( *visit)(TElemType& e))
{ // 先序遍历二叉树
if (T) {
visit(T->data); // 访问结点
Preorder(T->lchild, visit); // 遍历左子树
Preorder(T->rchild, visit);// 遍历右子树
}
}
我就不明白，当遍历到某只有右子树的结点时，其lchild为空，NULl作为参数递归调用到if语句，if语句条件不成立，结束递归，然后程序是怎么执行的。请学过数据结构的前辈或者电脑高手给我讲讲递归调用啊！数据结构中最重要的树和图中好多递归问题，全部搞不明白，关于程序的出口接口什么的。这个问题已经困扰我好久了。再次拜托！
其实理解递归要从栈那里理解的，当遍历到某只有右子树的结点时，若这个结点的lchild结点为空，lchild结点出栈，输出NULL或不输出。因为，是线序遍历，所以，新的栈顶结点就是某个右子树的结点的rchild结点
如果rchild结点的lchild和rchild结点都为空就，那么rchild结点出栈，输出rchild结点，栈顶新结点就是某个右子树结点，因为某个右子树的rchild和lchild都输出了，为空，所以直接输出某个右子树的结点
如此类推
这个只是去访问一下这个函数，如果左子树为空，自然就不去访问，注意，我们的目的是为了遍历全棵二叉树，而不是去看所谓不存在子树的空节点该如何继续访问下去。
你放错地方了