Question

数据结构中的二叉树中的递归怎么理解？

Answer 1

//递归方法实现创建
status createbitree(bitree *t)
{
int ch=0;
cin>>ch;
if(ch==0)(*t)=NULL;
else
{
(*t)=(bitree)malloc(sizeof(binode));
(*t)->data=ch;
createbitree(&(*t)->lchild);
createbitree(&(*t)->rchild);
}
return OK;
}
这是个按条件先序遍历的顺序输入的二叉树，你必须理解的是这些代码中的递归有一个隐含的条件就是利用栈来进行存储，有一个压栈和出栈的过程，栈起了一个保护现场的作用，左孩子是优先的，一直到这个结点为空，才进行弹栈将这个结点的父亲结点，并且进入这个父亲结点的右孩子，对这个过程重复。
有什么问题可以继续找我，数据结构我学的还可以的

Answer 2

以中序遍历为例，思想是：
若二叉树为空，则空操作；否则
（1）中序遍历左子树
（中序遍历左子树时也是这三步）
（2）访问根结点
（3）中序遍历右子树
（当然右子树也是重复着三步）

示例代码：
int InOrderTraverse(BiTree T)
{
if(T)
{
InOrderTraverse(T->lchild);
printf("%d\t",T->data);
InOrderTraverse(T->rchild);
}

return OK;
}

Answer 3

遍历算法
　　1．中序遍历的递归算法定义：
　　若二叉树非空，则依次执行如下操作：
　　(1)遍历左子树；
　　(2)访问根结点；
　　(3)遍历右子树。
　　2．先序遍历的递归算法定义：
　　若二叉树非空，则依次执行如下操作：
　　(1) 访问根结点；
　　(2) 遍历左子树；
　　(3) 遍历右子树。
　　3．后序遍历得递归算法定义：
　　若二叉树非空，则依次执行如下操作：
　　(1)遍历左子树；
　　(2)遍历右子树；
　　(3)访问根结点。
实现代码：
#include "stdio.h"
#include "malloc.h"
#define M 100
typedef struct node
{ /* 链式存储的指针类型和结点定义 */
char data;
struct node *lchild,*rchild;
}BTnode;
BTnode *create()/*建立二叉树*/
{
BTnode *t;
char ch;
scanf("%c",&ch);
if(ch=='#')
t=NULL;
else
{t=(BTnode *)malloc(sizeof(BTnode)) ;
t->data=ch;
t->lchild=create();
t->rchild=create();
}
return t;
}
void preorder(BTnode *t)/*先序遍历二叉树*/
{
if(t!=NULL)
printf("%c ",t->data);
if(t->lchild!=NULL)
preorder(t->lchild);
if(t->rchild!=NULL)
preorder(t->rchild);
}
void inorder(BTnode *t)/*中序遍历二叉树*/
{
if(t!=NULL)
{
if(t->lchild!=NULL)
inorder(t->lchild);
printf("%c ",t->data);
if(t->rchild!=NULL)
inorder(t->rchild);
}
}
void postorder(BTnode *t)/*后序遍历二叉树*/
{
if(t!=NULL)
{ if(t->lchild!=NULL)
postorder(t->lchild);
if(t->rchild!=NULL)
postorder(t->rchild);
printf("%c ",t->data);
}
}
void main()
{
BTnode *t;
printf("Input data:") ;
t=create();
printf("==================The result==========================/n");
printf("The preorder is:/n");
preorder(t);
printf("/n");
printf("The inorder is:/n");
inorder(t);
printf("/n");
printf("The postorder is:/n");
postorder(t);
printf("/n");
getch();
}
例如：
A
/ /
B C
/ / /
D E F
输入：ABD###CE##F##
先序遍历输出：A B D C E F
中序遍历输出：D B A E C F
后序遍历输出：D B E F C A

Answer 4

二叉树中的递归，最本质的东西是：每个结点都是平等的，即根结点所代表的二叉树，与以任何结点为根的子树具有相同的结构性质，因此，对根结点所代表的二叉树的处理方法与以任何其他结点为根的子树的处理方法一样，且子树的规模比原树还小，因此可以进行递归定义，求解和处理。

Answer 5

二叉树的递归理解很重要，否则树转二叉树和森林转二叉树你会懵逼的，更别说利用递归来解决有关树和森林的问题了。

二叉树本身就是一个递归的结构，这个怎么理解，以每个结点为根它都是一棵二叉树，二叉树里面嵌套二叉树，或者说二叉树里面又是二叉树。

二叉树的递归定义怎么说的，二叉树是由一个根结点和左右子树组成的，左右子树无论空与非空又是一棵二叉树，这种定义是明显的递归定义，递归的特点不就是进去了还是它本身吗？看下面这个图片

最外层这个图片可以进去的，进去了还是那张图片，只不过小了，从这张图片再进还是这张图片，只不过更小了，想想二叉树不就是这样吗？二叉树的左右子树又是一棵二叉树，意味者从左右子树进去了还是一棵二叉树，左右子树的左右子树又是一棵二叉树。递归的特点都是一样，二叉树也不例外。

二叉树的有很多递归算法，简单的比如求叶子结点个数，求根到结点的路径，稍微难点的如构造二叉树，输出二叉树等等，其他的实际问题抽象出来仍然是这些问题罢了，所以理解并掌握二叉树的递归特性并用来解决问题很重要。

有一个理解方法，你看下面这段程序

void AppreciateRecursion(int n)//n的种子值是1
{
    if(n == 3)
        return;
    else
    {
        for(int i = 0;i < 2; ++i)
        {
            AppreciateRursion(n+1);
        }
    }
}

整个递归过程画出来就一棵二叉树。