c语言中前序遍历,先序遍历c语言

本文目录一览：

• 1、C语言二叉树前，中，后遍厉序列有什么规律，就是已知俩个，如何推出第三个，谢谢
• 2、求解释！！！！中序遍历怎么找到前序结点？？？？（c语言）
• 3、C语言中，递归先序遍历和非递归先序遍历的有何区别?各自优缺点?
• 4、C语言中，到底先序遍历、中序遍历、后续遍历怎么看的…真的快疯掉了！求高人指点指点…泪目
• 5、如何用C语言实现层次遍历二叉树?

C语言二叉树前，中，后遍厉序列有什么规律，就是已知俩个，如何推出第三个，谢谢

概念弄懂了，这个就懂了！

假设有棵树，长下面这个样子，它的前序遍历，中序遍历，后续遍历都很容易知道。

前序:         GDAFEMHZ

中序:            ADEFGHMZ

后续:       AEFDHZMG

现在，假设仅仅知道前序和中序遍历，如何求后序遍历呢？比如，已知一棵树的前序遍历是”GDAFEMHZ”，而中序遍历是”ADEFGHMZ”应该如何求后续遍历?

第一步，root最简单，前序遍历的第一节点G就是root。

第二步，继续观察前序遍历GDAFEMHZ，除了知道G是root，剩下的节点必然是root的左右子树之外，没法找到更多信息了。

第三步，那就观察中序遍历ADEFGHMZ。其中root节点G左侧的ADEF必然是root的左子树，G右侧的HMZ必然是root的右子树。

第四步，观察左子树ADEF，左子树的中的根节点必然是大树的root的leftchild。在前序遍历中，大树的root的leftchild位于root之后，所以左子树的根节点为D。

第五步，同样的道理，root的右子树节点HMZ中的根节点也可以通过前序遍历求得。在前序遍历中，一定是先把root和root的所有左子树节点遍历完之后才会遍历右子树，并且遍历的右子树的第一个节点就是右子树的根节点。

如何知道哪里是前序遍历中的左子树和右子树的分界线呢？通过中序遍历去数节点的个数。

在上一次中序遍历中，root左侧是A、D、E、F，所以有4个节点位于root左侧。那么在前序遍历中，必然是第1个是G，第2到第5个由A、D、E、F过程，第6个就是root的右子树的根节点了，是M。

第六步，观察发现，上面的过程是递归的。先找到当前树的根节点，然后划分为左子树，右子树，然后进入左子树重复上面的过程，然后进入右子树重复上面的过程。最后就可以还原一棵树了。

第七步，其实，如果仅仅要求写后续遍历，甚至不要专门占用空间保存还原后的树。只需要稍微改动第六步，就能实现要求。

时间问题：只能炒一些来答你： 

求解释！！！！中序遍历怎么找到前序结点？？？？（c语言）

中序遍历可记作为：左根右。即：首先遍历左子树，然后访问根结点，最后遍历右子树。在遍历左、右子树时，仍然先遍历左子树，再访问根结点，最后遍历右子树。应多画图，我以前学数据结构时也是多画图，画图的话就容易理解。谢谢。

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***(注意*代表空格，因为空格你看不到就不好表示).

C语言中，到底先序遍历、中序遍历、后续遍历怎么看的…真的快疯掉了！求高人指点指点…泪目

先序遍历就是“根左右”，不管你现在在哪个节点，都是按这种规则。上面的题目：根是A，左是B，右是C，所以是A-》B，在当前根节点B，还是按上述规则，那么接下来到D，D之后没有子节点，返回B，遍历E-》X，X之后没有子节点，返回E，E的子节点都遍历完了，返回B，B的子节点都遍历完了，返回A，接下来遍历右子树，规则同上。

中序遍历就是“左根右”，对于A来说，先遍历B，对于B来说，先遍历D，对于D来说，已经没有左子树，所以遍历D，D没有右子树,返回B，遍历B，B有右子树E，对于E来说，先遍历X，完了返回E，E完了返回B，B完了返回A，遍历A，遍历右子树，规则同上。

后序遍历就是跟先序遍历相反的，先遍历右子树，再左子树，最后才是根。

好好思考一下。

如何用C语言实现层次遍历二叉树?

下面是c语言的前序遍历二叉树的算法，在这里假设的节点元素值假设的为字符型，

说明：算法中用到了结构体，也用到了递归的方法，你看看怎么样，祝你好运！

#include”stdio.h”

typedef

char

elemtype;

typedef

struct

node

//定义链表结构

{

elemtype

data;

//定义节点值

struct

note

*lchild;

//定义左子节点值

struct

note

*rchild;

//定义右节点值

}btree;

preorder(btree

*root)

//前序遍历

{

if(roof!=null)

//如果不是空节点

{

printf(“%c\n”,root-data);

//输出当前节点

preorder(root-lchild);

//递归前序遍历左子节点

preorder(root-rchild);

//递归前序遍历右子节点

}

return;

//结束

}