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

alunfrankly · 2018-4-30 01:55:48

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

liuranghuan123 · 2018-4-30 01:55:47

//递归方法实现创建
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;
}
这是个按条件先序遍历的顺序输入的二叉树，你必须理解的是这些代码中的递归有一个隐含的条件就是利用栈来进行存储，有一个压栈和出栈的过程，栈起了一个保护现场的作用，左孩子是优先的，一直到这个结点为空，才进行弹栈将这个结点的父亲结点，并且进入这个父亲结点的右孩子，对这个过程重复。
有什么问题可以继续找我，数据结构我学的还可以的

云澹枫卿 · 2018-4-30 01:55:46

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

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

return OK;
}

知道高高手无敌 · 2018-4-30 01:55:45

遍历算法
　　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

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

4 个回复