怎么理解递归创建二叉树

怎么理解递归创建二叉树

递归=传递+回归，即任务的下放和结果的回收。
　　create（node *root）
　　{
　　root=new node；
　　写上关于root的信息//初始化root节点
　　if(root满足自定义的条件)//自定义一个递归的条件，即传递和回归的界限，这是必须的。
　　{
　　create(root->lchild);//建左子树
　　create(root->rchild);//建右子树
　　}
　　}
　　总体上来看，建一颗树，每一次调用creat（）都是只创建一个节点，把剩下的任务下放给create（root->lchild)和create(root->rchild) ，而这两个也会重复第一个create（root）的做法，实质体现的是任务的不断下放，当达到最后的回归的界限的，结果又将不断回收，对应的是函数的不断返回，实质是退栈的过程。这个过程其实经历了一个不断进栈和不断出栈的过程，对应的是任务的不断下放和不断提交，最后栈空，即告全部任务完成。

　　pTree createTree(pTree T)
　　{
　　char ch;
　　ch = getchar();
　　if (ch == '#')//这是递归结束条件
　　{
　　T = NULL;
　　}
　　else
　　{
　　T = (pTree)malloc(sizeof(TreeNode));
　　T->data = ch;
　　T->left = createTree(T->left);//注意，这里采用的是先建左子树
　　T->right = createTree(T->right);//再建右子树，所以建树时须按照相应的遍历次序，即先序遍历
　　}
　　return T;//这里不能缺，新建的树，必须让它的父亲能指向它，如T->left = createTree(T->left);
　　}
　　}

|
#g ##
-------
||
##
请你按照前序遍历的方法遍历一下，看看结果是否就是那个字符串。至于说程序的逻辑很简单，输入的不是#，即表示是一个节点，创建该节点（"T = (pTree)malloc(sizeof(TreeNode));"
），并且继续处理左子树（“T->left = createTree(T->left);”）和右子树（“T->right = createTree(T->right);”）。而#即表示此处不是一个节点，或者说该指针仅仅是一个空指针，因此返回NULL。大概就是这样，你要理解的是二叉树的建立和表达是可以一一对应的，但是要求知道遍历的方式，前，中，还是后。

|
## e f
------------

二叉树的遍历和创建全是分成3种形式，前序，中序，和后序。前序及先访问一棵子树的根节点，然后访问左子树，最后访问右子树。你的程序正是一个前序方式创建的二叉树。抛开你的code，看输入的字符串abc##de#g##f###表示一棵什么样的树：
a
--------------
||
b#
--------------
||
cd
--------------------

递归=传递+回归，即任务的下放和结果的回收。
这个需要自己慢慢体会，其实所有递归算法实质上都是一样的，理解了就万变不离其宗了。
create（node *root）
{
root=new node；
写上关于root的信息//初始化root节点
if(root满足自定义的条件)//自定义一个递归的条件，即传递和回归的界限，这是必须的。
{
create(root->lchild);//建左子树
create(root->rchild);//建右子树
}
}
总体上来看，建一颗树，每一次调用creat（）都是只创建一个节点，把剩下的任务下放给create（root->lchild)和create(root->rchild) ，而这两个也会重复第一个create（root）的做法，实质体现的是任务的不断下放，当达到最后的回归的界限的，结果又将不断回收，对应的是函数的不断返回，实质是退栈的过程。这个过程其实经历了一个不断进栈和不断出栈的过程，对应的是任务的不断下放和不断提交，最后栈空，即告全部任务完成！
pTree createTree(pTree T)
{
char ch;
ch = getchar();
if (ch == '#')//这是递归结束条件
{
T = NULL;
}
else
{
T = (pTree)malloc(sizeof(TreeNode));
T->data = ch;
T->left = createTree(T->left);//注意，这里采用的是先建左子树
T->right = createTree(T->right);//再建右子树，所以建树时须按照相应的遍历次序，即先序遍历
}
return T;//这里不能缺，新建的树，必须让它的父亲能指向它，如T->left = createTree(T->left);
}
}