遍历二叉树的递归程序详解

Question

请问这段代码的执行步骤 <重点是递归调用那段> 最好每一步都写出来 哪步哪个数据进栈,什么时候出栈，请明白人来给讲解一下。连题都看不懂的请一起等待答案。谢谢.重点是递归调用的部分，前面的结构就不用了。

struct bitree
{
int data;
bitree *lchild;
bitree *rchild;
};
void preorder(struct bitree *root){
struct bitree *p;
p=root;
if(p!=NULL)
{
printf("%d\n",p->data);
preorder(p->lchild);
preorder(p->rchild);
}
}

Answer 1

这是一个先序遍历递归算法void preorder(struct bitree *root){
struct bitree *p;
p=root;
if(p!=NULL)//不为空树
{
printf("%d\n",p->data);//先访问数据区，即根结点
preorder(p->lchild);//再访问左孩子(树)
preorder(p->rchild);//再访问右孩子(树)
}
}比如一颗完全二叉树,层次遍历为(A)(BC)(DEFG)(HIJKLMNO)按照这的先序遍历过程为:第一次调用,所以访问到A<进入第一层递归>访问以B为根结点的树(A的左子树),所以访问到B.<进入第二层递归>访问以D为根结点的树(B的左子树),.所以访问到D.<进入第三层递归>访问以H为根结点的树(D的左子树),.所以访问到H.<进入第四层递归>访问H的左子树,因为H是叶子结点(即左孩子指针P=NULL),返回第三层递归,<再进入第四层递归>访问H的右子树,因为H是叶子结点(即右孩子指针P=NULL),返回第三层递归.到这里H的左右子树访问完,退回到第二层递归.<再进入第三层递归>访问以I为根结点的树(D的右子树),所以访问到I<进入第四层递归>访问I的左子树,因为I是叶子结点(即左孩子指针P=NULL),返回第三层递归,<再进入第四层递归>访问I的右子树,因为I是叶子结点(即右孩子指针P=NULL),返回第三层递归.到这里I的左右子树访问完,退回到第二层递归.到这里D的左右子树访问完,退回到第一层递归.<再进入第二层递归>访问以E为根结点的树(B的右子树),.所以访问到E.这样依次下去.......最后访问到O本回答被网友采纳