前序遍历递归算法

① C语言中，递归先序遍历和非递归先序遍历的有何区别各自优缺点

1、递归就是函数调用函数本身，运行起来就是函数嵌套函数，层层嵌套，所以函数调用、参数堆栈都是不小的开销，但是程序简单。
2、非递归就是不断地对参数入栈、出栈，省去了函数层层展开、层层调用的开销。虽然参数出入栈次数多了，但是一般都开辟固定的足够大的内存来一次性开辟、重复使用。
3、非递归是从堆栈的角度来编写程序，速度快，但代码复杂。
递归是从问题本身的逻辑角度来编写，虽然速度相对慢，但代码容易理解。
如果对速度要求不高，建议用递归方式。
4、摘录例子如下：
#include <stdio.h>
#include <stdlib.h>
typedef struct BiTNode
{
char data;
struct BiTNode *lchild,*rchild;
} BiTNode,*BiTree;//二叉树的节点类型
typedef struct QNode
{
BiTNode data;
struct QNode *next;
} QNode,*QueuePtr;//队列节点类型
typedef struct
{
QueuePtr front;
QueuePtr rear;
}LinkQueue;//队列的头尾指针
void InitQueue(LinkQueue *Q)//创建队列
{
Q->front=Q->rear=(QueuePtr)malloc(sizeof(QNode));
Q->rear->next=NULL;
}
void EnQueue(LinkQueue *Q,BiTNode e)//入队操作
{
QueuePtr p;
p=(QueuePtr)malloc(sizeof(QNode));
p->data=e;
p->next=NULL;
Q->rear->next=p;
Q->rear=p;
}
BiTNode DeQueue(LinkQueue *Q)//出对操作
{
BiTNode e;QueuePtr p;
p=Q->front->next;
e=p->data;
Q->front->next=p->next;
if(Q->rear==p)
Q->rear=Q->front;
free(p);
return (e);

}
int QueueEmpty(LinkQueue *Q)//判断队列是否为空
{
if(Q->front==Q->rear )
return 1;
else
return 0;
}
BiTree CreateBiTree()//创建二叉树
{
char p;BiTree T;
scanf("%c",&p);
if(p==' ')
T=NULL;
else
{
T=(BiTNode *)malloc(sizeof(BiTNode));
T->data=p;
T->lchild=CreateBiTree(T->lchild);
T->rchild=CreateBiTree(T->rchild);
}
return (T);
}
void PreOrder(BiTree T)//先序
{
if(T!=NULL)
{
printf("%c",T->data);
PreOrder(T->lchild);
PreOrder(T->rchild);
}
}

void LevelOrder(BiTree T)//层次遍历
{
LinkQueue Q; BiTNode p;
InitQueue(&Q);
EnQueue(&Q,*T);
while(!QueueEmpty(&Q))
{
p = DeQueue(&Q);
printf("%c",p.data);
if(p.lchild!=NULL)
EnQueue(&Q,*(p.lchild));
if(p.rchild!=NULL)
EnQueue(&Q,*(p.rchild));
}
}

void main()
{
BiTree Ta;
Ta=CreateBiTree();
printf("层次遍历:");
printf("\n");
LevelOrder(Ta);
printf("\n");
printf("先序遍历:");
printf("\n");
PreOrder(Ta);
}

层次使用非递归的，用到队列
先序是用递归的
创建树使用先序递归建树

输入个例子：
abc**de*f**g***(注意*代表空格，因为空格你看不到就不好表示).

② 二叉树先序遍历递归算法问题

status preordertraverse(bitree T,status (*visit)(telemtype e))
{
if(T) //判断跟指针是否为空，若不空，则进入
{
if(visit (T->data)) //若不空，访问该指针所指向的关键字
if(preordertraverse(T->lchild,visit)) //若不空，访问该指针的左孩子
if(preordertraverse(T->rchild,visit)) //若不空，访问该指针的右孩子
return OK;
return ERROR;

}else return OK;
}
}else return OK;
}

③ 建立二叉树，并利用递归方法实现先序、中序、后序遍历。

#include
#include
#include
#include
#include

using namespace std;

struct node;

typedef node *tree;

struct node{
char data;
tree lchild,rchild;
};

tree bt;

void build(tree &bt){
char ch;
ch=getchar();
if(ch!='.'){
bt=new node;
bt->data=ch;
build(bt->lchild);
build(bt->rchild);
}
else
bt=NULL;
}

void prework(){
ios::sync_with_stdio(false);
//freopen("data.in","r",stdin);
build(bt); //建树
}

void preorder(tree bt){
if(bt){
cout<data;
preorder(bt->lchild);
preorder(bt->rchild);
}
}

void midorder(tree bt){
if(bt){
preorder(bt->lchild);
cout<data;
preorder(bt->rchild);
}
}

void backorder(tree bt){
if(bt){
preorder(bt->lchild);
cout<data;
preorder(bt->rchild);
}
}

void mainwork(){
preorder(bt);
cout<<endl;
midorder(bt);
cout<<endl;
backorder(bt);
}

int main(){
prework();
mainwork();
return 0;
}
//我这里输入的东西是要求叶子节点的子节点为'.'
但仍无铃声，则送维修店维修。三无受话现象：

④ 用递归算法先序中序后序遍历二叉树

1、先序

void PreOrderTraversal(BinTree BT)

{

if( BT )

{

printf(“%d ”, BT->Data); //对节点做些访问比如打印

PreOrderTraversal(BT->Left); //访问左儿子

PreOrderTraversal(BT->Right); //访问右儿子

}

}

2、中序

void InOrderTraversal(BinTree BT)

{

if(BT)

{

InOrderTraversal(BT->Left);

printf("%d ", BT->Data);

InOrderTraversal(BT->Right);

}

}

3、后序

void PostOrderTraversal(BinTree BT)

{

if (BT)

{

PostOrderTraversal(BT->Left);

PostOrderTraversal(BT->Right);

printf("%d ", BT->Data);

}

}

(4)前序遍历递归算法扩展阅读：

注意事项

1、前序遍历

从整棵二叉树的根结点开始，对于任意结点VV，访问结点VV并将结点VV入栈，并判断结点VV的左子结点LL是否为空。若LL不为空，则将LL置为当前结点VV；若LL为空，则取出栈顶结点，并将栈顶结点的右子结点置为当前结点VV。

2、中序遍历

从整棵二叉树的根结点开始，对于任一结点VV，判断其左子结点LL是否为空。若LL不为空，则将VV入栈并将L置为当前结点VV；若LL为空，则取出栈顶结点并访问该栈顶结点，然后将其右子结点置为当前结点VV。重复上述操作，直到当前结点V为空结点且栈为空，遍历结束。

3、后序遍历

将整棵二叉树的根结点入栈，取栈顶结点VV，若VV不存在左子结点和右子结点，或VV存在左子结点或右子结点，但其左子结点和右子结点都被访问过了，则访问结点VV，并将VV从栈中弹出。若非上述两种情况，则将VV的右子结点和左子结点依次入栈。重复上述操作，直到栈为空，遍历结束。

⑤ 树的递归算法

答案是正确的啊。
if(root)就是如果root!=0，这里root是一个指针，指向结构体struct node的指针，第一次进入函数它就是指向根节点A的指针
运行步骤：
如果指向A的指针不为空(不为0),打印'A',
递归调用函数指向A的左孩子节点
如果指向B的指针不为空(不为0),打印'B',
递归调用函数指向B的左孩子节点
如果指向C的指针不为空(不为0),打印'C',
递归调用函数指向C的左孩子节点
由于C的左孩子节点为空，所以本次递归traversal(root->lchild)结束，回到上一层递归中即从C的左孩子节点回到C中，然后执行traversal(root->lchild)这一句下面一句，打印出'C'
然后递归调用traversal(root->rchild);指向C的右孩子节点
如果指向E的指针不为空(不为0),打印'E',
然后再递归指向E的左孩子节点，为空再返回到E中，再次打印出'E',然后再指向E的右孩子节点，为空，E的递归结束返回上一层递归即C中，然后C也到达末尾结束返回上一层递归B中，然后执行traversal(root->lchild)这一句下面一句，打印出'B'
然后递归调用traversal(root->rchild);指向B的右孩子节点
......
如此不断进入某个节点的子节点操作后再从子节点返回父节点，层层进入再层层向上返回，从而遍历树中各个节点，最终得出结果：
A B C C E E B A D F F D G G

⑥ 二叉树的中序、前序、后序的递归、非递归遍历算法，层次序的非递归遍历算法的实现，应包含建树的实现。

二叉树的遍历是指按照一定次序访问二叉树中的所有节点，且每个节点仅被访问一次的过程。是最基本的运算，是其他运算的基础。
二叉树有两种存储结构：顺序存储和链式存储
顺序存储： （对完全二叉树来说，可以充分利用存储空间，但对于一般的二叉树，只有少数的存储单元被利用）
[cpp] view plain
typedef struct
{
ElemType data[MaxSize];
int n;
}SqBTree;
链式存储：
[csharp] view plain
typedef struct node
{
ElemType data;
struct node *lchild;
struct node *rchild;
} BTNode;

二叉树三种递归的遍历方法：
先序遍历 访问根节点→先序遍历左子树→先序遍历右子树
中序遍历 中序遍历左子树→访问根节点→中序遍历右子树
后序遍历 后序遍历左子树→后序遍历右子树→访问根节点
二叉树遍历的递归算法：
[cpp] view plain
void preOrder(BTNode *b) //先序遍历递归算法
{
if (b!=NULL)
{
visit(b);
preOrder(b->lchild);
preOrder(b->rchild);
}
}
void InOrder(BTNode *b) //中序遍历递归算法
{
if(b!=NULL)
{
InOrder(b->lchild);
visit(b);
InOrder(b->rchild);
}
}
void PostOrder(BTNode *b) //后序遍历递归算法
{
if(b!=NULL){
PostOrder(b->lchild);
PostOrder(b->rchild);
visit(b);
}
}
二叉树非递归遍历算法：
有两种方法：①用栈存储信息的方法 ②增加指向父节点的指针的方法 暂时只介绍下栈的方法
先序遍历：
[cpp] view plain
void PreOrder(BTNode *b)
{
Stack s;
while(b!=NULL||!s.empty())
{
if(b!=NULL){
visit(b);
s.push(b);
b=b->left;
}
else{
b=s.pop();
b=b->right;
}
}
}
中序遍历：
[cpp] view plain
void InOrder(BTNode *b){
Stack s;
while(b!=NULL||!s.empty()){
if (b!=NULL)
{
s.push(b);
s=s->left
}
if(!s.empty()){
b=s.pop();
visit(b);
b=b->right;
}
}
}
后序遍历：
[cpp] view plain
void PostOrder(BTNode *b){
Stack s;
while(b!=NULL){
s.push(b);
}
while(!s.empty()){
BTNode* node=s.pop();
if(node->bPushed){
visit(node);
}
else{
s.push(node);
if(node->right!=NULL){
node->right->bPushed=false;
s.push(node->right);
}
if(node->left!=NULL){
node->left->bpushed=false;
s.push(node->left);
}
node->bPushed=true; //如果标识位为true,则表示入栈
}
}
}
层次遍历算法：（用队列的方法）
[cpp] view plain
void levelOrder(BTNode *b){
Queue Q;
Q.push(b);
while(!Q.empty()){
node=Q.front();
visit(node);
if(NULL!=node->left){
Q.push(node->left);
}
if(NULL!=right){
Q.push(node->right);
}
}
}<span style=""></span>
已知先序和中序求后序的算法：（已知后序和中序求先序的算法类似，但已知先序和后序无法求出中序）
[cpp] view plain
int find(char c,char A[],int s,int e) /* 找出中序中根的位置。 */
{
int i;
for(i=s;i<=e;i++)
if(A[i]==c) return i;
}
/* 其中pre[]表示先序序，pre_s为先序的起始位置，pre_e为先序的终止位置。 */
/* 其中in[]表示中序，in_s为中序的起始位置，in_e为中序的终止位置。 */
/* pronum()求出pre[pre_s～pre_e]、in[in_s～in_e]构成的后序序列。 */
void pronum(char pre[],int pre_s,int pre_e,char in[],int in_s,int in_e)
{
char c;
int k;
if(in_s>in_e) return ; /* 非法子树，完成。 */
if(in_s==in_e){printf("%c",in[in_s]); /* 子树子仅为一个节点时直接输出并完成。 */
return ;
}
c=pre[pre_s]; /* c储存根节点。 */
k=find(c,in,in_s,in_e); /* 在中序中找出根节点的位置。 */
pronum(pre,pre_s+1,pre_s+k-in_s,in,in_s,k-1); /* 递归求解分割的左子树。 */
pronum(pre,pre_s+k-in_s+1,pre_e,in,k+1,in_e); /* 递归求解分割的右子树。 */
printf("%c",c); /* 根节点输出。 */
}
main()
{
char pre[]="abdc";
char in[]="bdac";
printf("The result:");
pronum(pre,0,strlen(in)-1,in,0,strlen(pre)-1);
getch();
}

⑦ 建立二叉树，实现前序遍历的非递归算法及递归算法<有追加>

找本数据结构书，自己看去。
/////////////////////////////////
地球人都知道遍历二叉树不用递归就只能用栈了
另：
hope1262你说的那个是堆，数组存储二叉树，他的这个明显不是
////////////////////////////////
递归在编译器实现的时候也是用堆栈实现的。递归的时候是从上向下的，而由于堆栈是先进后出，所以压栈的时候要先压后面的结点。
一棵树分为左子树、根和右子树，所以先把右子树压入栈，输出根，然后再压入左子树，压左子树时又重复这一过程了，直左子树为空；这时开始从栈中把之前压入的右子树pop出来，再重复上面的过程，直到栈为空。
代码：
void PreOrder(BiTNode *BT)
{
push(BT);
while(!IsEmpty)
{
pop(BT);
while(BT)
{
VISIT(BT);
push(BT->rchild);
BT=BT->lchild;
}
}
}
你的代码自己改吧，记得先把根压进栈。

⑧ c语言实现二叉树的先序,中序,后序的递归和非递归算法和层次遍历算法

#include<malloc.h> // malloc()等
#include<stdio.h> // 标准输入输出头文件，包括EOF(=^Z或F6)，NULL等
#include<stdlib.h> // atoi()，exit()
#include<math.h> // 数学函数头文件，包括floor()，ceil()，abs()等

#define ClearBiTree DestroyBiTree // 清空二叉树和销毁二叉树的操作一样

typedef struct BiTNode
{
int data; // 结点的值
BiTNode *lchild,*rchild; // 左右孩子指针
}BiTNode,*BiTree;

int Nil=0; // 设整型以0为空
void visit(int e)
{ printf("%d ",e); // 以整型格式输出
}
void InitBiTree(BiTree &T)
{ // 操作结果：构造空二叉树T
T=NULL;
}

void CreateBiTree(BiTree &T)
{ // 算法6.4：按先序次序输入二叉树中结点的值(可为字符型或整型，在主程中定义)，
// 构造二叉链表表示的二叉树T。变量Nil表示空(子)树。修改
int number;
scanf("%d",&number); // 输入结点的值
if(number==Nil) // 结点的值为空
T=NULL;
else // 结点的值不为空
{ T=(BiTree)malloc(sizeof(BiTNode)); // 生成根结点
if(!T)
exit(OVERFLOW);
T->data=number; // 将值赋给T所指结点
CreateBiTree(T->lchild); // 递归构造左子树
CreateBiTree(T->rchild); // 递归构造右子树
}
}

void DestroyBiTree(BiTree &T)
{ // 初始条件：二叉树T存在。操作结果：销毁二叉树T
if(T) // 非空树
{ DestroyBiTree(T->lchild); // 递归销毁左子树，如无左子树，则不执行任何操作
DestroyBiTree(T->rchild); // 递归销毁右子树，如无右子树，则不执行任何操作
free(T); // 释放根结点
T=NULL; // 空指针赋0
}
}

void PreOrderTraverse(BiTree T,void(*Visit)(int))
{ // 初始条件：二叉树T存在，Visit是对结点操作的应用函数。修改算法6.1
// 操作结果：先序递归遍历T，对每个结点调用函数Visit一次且仅一次
if(T) // T不空
{ Visit(T->data); // 先访问根结点
PreOrderTraverse(T->lchild,Visit); // 再先序遍历左子树
PreOrderTraverse(T->rchild,Visit); // 最后先序遍历右子树
}
}

void InOrderTraverse(BiTree T,void(*Visit)(int))
{ // 初始条件：二叉树T存在，Visit是对结点操作的应用函数
// 操作结果：中序递归遍历T，对每个结点调用函数Visit一次且仅一次
if(T)
{ InOrderTraverse(T->lchild,Visit); // 先中序遍历左子树
Visit(T->data); // 再访问根结点
InOrderTraverse(T->rchild,Visit); // 最后中序遍历右子树
}
}

void PostOrderTraverse(BiTree T,void(*Visit)(int))
{ // 初始条件：二叉树T存在，Visit是对结点操作的应用函数
// 操作结果：后序递归遍历T，对每个结点调用函数Visit一次且仅一次
if(T) // T不空
{ PostOrderTraverse(T->lchild,Visit); // 先后序遍历左子树
PostOrderTraverse(T->rchild,Visit); // 再后序遍历右子树
Visit(T->data); // 最后访问根结点
}
}

void main()
{
BiTree T;
InitBiTree(T); // 初始化二叉树T
printf("按先序次序输入二叉树中结点的值,输入0表示节点为空，输入范例：1 2 0 0 3 0 0\n");
CreateBiTree(T); // 建立二叉树T
printf("先序递归遍历二叉树：\n");
PreOrderTraverse(T,visit); // 先序递归遍历二叉树T
printf("\n中序递归遍历二叉树：\n");
InOrderTraverse(T,visit); // 中序递归遍历二叉树T
printf("\n后序递归遍历二叉树：\n");
PostOrderTraverse(T,visit); // 后序递归遍历二叉树T
}

⑨ 关于二叉树先序遍历的递归算法问题

你把递归理解错了，递归调用我用下面这种方法表示
Preorder->Preorder->Preorder->Preorder->Preorder->Preorder->Preorder
每一个Preoder都是去访问一个节点的左子树，当最后的叶子没有左节点时，是最有一次调用Preorder返回了，继续倒数第二次调用Preorder的代码。如下

void Preorder (BiTree T,
void( *visit)(TElemType& e))
{ // 先序遍历二叉树
if (T) {
visit(T->data); // 访问结点
Preorder(T->lchild, visit); // 最后一次没有左子树了，返回到这里
Preorder(T->rchild, visit);// 继续访问右子树
}
}

⑩ 先序遍历二叉树的递归算法怎样理解（严蔚敏主编）

先序调用的时候，递归函数，先序函数会一直递归，直到t->next为空，即t为叶节点，需要注意的是当t->next 为空时，函数的实参没有传过去，所以t指向叶结点的父节点，更要注意的是，先序调用的递归函数还没执行完，在先序调用的最里层，要执行这个函数的最后一个语句，即先序访问右子树。
在了解递归函数时，要注意函数是一层一层执行的，把没有调用的函数看作哦是第一层，第一次调用的时候，，势必会第二次遇到调用函数，变成第二层，，，，