Question

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

template <class DataType>
BiTree :: BiTree( )
{
root = Creat(root);
}
template <class DataType>
BiNode<DataType> *BiTree<DataType>::Creat(BiNode<DataType> *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;
}
这段部分代码是不是输入一次#递归调用就结束了？还有我怎么左看右看都是一直递归调用左子树啊，什么情况下才是递归调用右子树啊?我下面给一张二叉树的图，麻烦大神帮我从一开始构建二叉树到结束的过程（包括怎么递归等过程）详细的和我说一下，感激不尽啊。

Answer 1

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

具体过程你看下面的图好了，由于内容比较多，我把if给省略了，就只写了执行到的部分。

Answer 2

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