递归创建二叉树的程序是怎么执行的如下

template BiTree :: BiTree( ){    root = Creat(root);}template BiNode *BiTree::Creat(BiNode *bt){    cin >> ch;                   //输入结点的数据信息，假设为字符  ...template
BiTree :: BiTree( )
{
   root = Creat(root);
}
template
BiNode *BiTree::Creat(BiNode *bt)
{
   cin >> ch;                   //输入结点的数据信息，假设为字符
   if (ch == '# ') bt = NULL;             //建立一棵空树
   else {
      bt = new BiNode; bt->data= ch;  //生成一个结点，数据域为ch
      bt->lchild = Creat(bt->lchild);       //递归建立左子树
      bt->rchild = Creat(bt->rchild);       //递归建立右子树
}
return bt;
}
这段部分代码是不是输入一次#递归调用就结束了？还有我怎么左看右看都是一直递归调用左子树啊，什么情况下才是递归调用右子树啊?我下面给一张二叉树的图，麻烦大神帮我从一开始构建二叉树到结束的过程（包括怎么递归等过程）详细的和我说一下，感激不尽啊。

展开

热心网友 · 2018-4-30 02:31:59

bt->rchild = Creat(bt->rchild); //递归建立右子树
这就是创建右子树。
左右是相对的，根据你的根节点而定，a是根，那么bd就是左子树，b是根，d就是右子树，
只是子树具备父树的关系才用递归而已。
至于过程嘛，你只需知道父树的创建顺序就Ok了，子树同理，否则就不是树，这里是前序创建，中左右。
创建根节点
创建整个左子树
创建整个右子树
三步完成树就完成了，至于左子树怎么创建，上面已经说的很明白了。

yl_shadow · 2018-4-30 02:31:58

递归只是一种形式，本质还是调用函数，所你你不要一直想着它是递归，就认为建立二叉树的函数是函数A，建立左子树是函数B，建立右子树是函数C，只不过B和C的内容和A一样罢了。那函数内的代码怎么执行？就是自上而下一步一步按顺序执行咯，执行完了建立左子树的函数就会执行建立右子树的函数了，只不过这些函数里面还要再调用函数。对于函数的调用，你就当是把函数里的代码全部嵌入到调用它的地方就好了，然后还是自上而下顺序执行。
具体过程你看下面的图好了，由于内容比较多，我把if给省略了，就只写了执行到的部分。

递归创建二叉树的程序是怎么执行的如下

2 个回复