‘壹’ 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语言数据机构：由中序遍历和层次遍历能不能唯一确定一颗二叉树为什么说法不一致哪
由中序遍历和层次遍历能够唯一确定一颗二叉树。从下面的算法可知，每一步构造得到的二叉树结果是唯一的。
以下构造部分的答案来自网络知道：
假定树的层次遍历ABCDEFG
HIJ中序遍历DBGEHJACIF
两种遍历顺序要结合着分析，才能画出这颗树的图
比如，层次遍历，先访问到A节点，说明A是树的根节点
那么在中序遍历结果里看：
DBGEHJ在A前面，说明这些节点，都在A左子树上
CIF在A的后面，说这些节点，都在A的右子树上
那么，树可以先这样画：
__________A________
________/____\_____
_____DBGEHJ__CIF___
再看层次遍历，A后面是B，说明B是A左子树的根节点
从上图中的先序遍历顺序DBGEHJ中看到：
D在B的前面，说明D在B的左子树上
GEHJ在B的后面，说明它们在B的右子树上
那么，树又可以画成：
_________A________
_______/____\_____
_____B________CIF__
____/__\____________
___D__GEHJ_________
如此循环，直到将整个树都画完全
结果如下：
_____________A_______________
___________/____\_____________
________B_________C__________
______/___\_________\_________
_____D_____E_________F_______
__________/__\_________\______
_________G____H_________I____
_______________\______________
_________________J____________
‘叁’ 由中序遍历和层次遍历还原二叉树。C语言实现
经测，该代码已经修改正确，只需在void BuildTree(char *level,char *inorder,pBiTree T)这里的最后一个变量T改为引用即可。还有一个地方判断调用右子树的地方的判断条件。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedefstruct_BiTree
{
chardata;
struct_BiTree*lchild;
struct_BiTree*rchild;
}BiNode,*pBiTree;
voidBuildTree(char*level,char*inorder,pBiTree&T)
{
inti;
intlen=strlen(level);//取得层次遍历长度
intpos=0;
if(len==0)
return;
char*p=strchr(inorder,level[0]);
if(p==NULL)//如果为空则抛弃第隐丛一个，跳到下一个；
{
char*L=(char*)malloc(sizeof(char)*len);//开辟数组
strncpy(L,level+1,len-1);//舍弃第一个
L[len-1]=0;
BuildTree(L,inorder,T);//调用建树函数
return;
}
亏碧pos=p-inorder;//得到中序遍历左子树字符串长度
T->data=level[0];//为根节点赋值
T->lchild=NULL;
T->rchild=NULL;
if(pos!=0)//左子树的递归调用
{
T->lchild=(pBiTree)malloc(sizeof(BiNode));
char*left_level=(char*)malloc(sizeof(char)*len);
char*left_inor=(char*)malloc(sizeof(char)*(pos));
strncpy(left_level,level+1,len-1);//舍去层次遍历第一个
strncpy(left_inor,inorder,pos);//截取左子树字符销携举串
left_level[len-1]=0;
left_inor[pos]=0;
BuildTree(left_level,left_inor,T->lchild);
}
if(pos<strlen(inorder)-1)//右子树的递归调用
{
T->rchild=(pBiTree)malloc(sizeof(BiNode));
char*right_level=(char*)malloc(sizeof(char)*(len));
char*right_inor=(char*)malloc(sizeof(char)*(len-pos));
strncpy(right_level,level+1,len-1);
strncpy(right_inor,inorder+pos+1,len-pos-1);
right_level[len-1]=0;
right_inor[len-pos-1]=0;
BuildTree(right_level,right_inor,T->rchild);
}
}
voidpriOrder(pBiTreeT)
{
if(T!=NULL){
printf("%c",T->data);
priOrder(T->lchild);
priOrder(T->rchild);
}
}
voidpostOrder(pBiTreeT)
{
if(T!=NULL){
postOrder(T->lchild);
postOrder(T->rchild);
printf("%c",T->data);
}
}
voidfreeNode(pBiTree&T)
{
if(T!=NULL){
freeNode(T->lchild);
freeNode(T->rchild);
free(T);
}
}
intmain()
{
pBiTreeroot;
charlevel[28],inorder[28];
intn;
scanf("%d",&n);
//fflush(stdin);
getchar();
while(n--){
scanf("%s%s",level,inorder);
root=(pBiTree)malloc(sizeof(BiNode));
BuildTree(level,inorder,root);
priOrder(root);
printf(" ");
postOrder(root);
printf(" ");
//freeNode(root);
}
return0;
}
‘肆’ C语言实现左孩子右兄弟树的建立，插入，层次遍历，可以加分
问的有些问题，程序建立的2叉树只能是完全2叉树，其他的树只能手动建立，我这里给你完全2叉树的建立和遍历，完全2叉树是没有插入的，给你函数
#include
#include
typedef
struct
_node_
{
int
data;
struct
_node_
*lchild,*rchild;
}bitree;
//递归建立完全2x树，root每次遍历后都会返回上层树的根节点，这点容易理解错，最终返回的root是整个2x树的根节点，传参int
i
是给2x树赋值：1,2,3,4,5……，int
n是想建立的总共节点数。
bitree
*CreatBitree(int
i,int
n)
{
bitree
*root
=
(bitree*)malloc(sizeof(bitree));
root->data
=
i;
if(i
*
2
<=
n)
root->lchild
=
CreatBitree(2
*
i,n);
else
root->lchild
=
NULL;
if(i
*
2
+
1
<=n)
root
->rchild
=
CreatBitree
(2
*
i
＋1，n）；
else
root->rchild
=
NULL;
return
root;
}
//遍历
void
proorder(bitree*
root)
{
if(root
==
NULL)
return;
printf("%d
",root->data);
proorder(root->lchild);
proorder(root->rchild);
}//这是根左右遍历即前序遍历，如果想改成中序或者后序只需要把printf改到lchild后和rchild后即可
写完才发现你要层次遍历啊？！，那个还要引入个队列的建立，需要建队，出队，入队的函数，全写出来很麻烦的，写2x树的都不是初学了，我假设你已经有了队列相关函数，给出函数功能注释，然后直接给你层次遍历的函数吧：
void
noorder(bitree
*root)
{
sequeue
*sq;//用的顺序队列，没有用链式的，要不更麻烦了，sequeue是typedef的队列结构体
sq
=
CreatEmptySequeue();//建立空队列
EnSequeue(sq,root);//根节点入队
while(!EmptySequeue(sq))//判断队列是否空
{
root
=
Desequeue;//出列
printf("%d",root->data);
if(root->lchild
!=NULL)
EnSequeue(sq,root->lchild);
if(root->rchild
!=
NULL)
EnSequeue(sq
,root->rchild);
}
return;
}
算法描述，
利用队列的先进先出的特性，首先把根节点入队列，然后开始循环，先判断队列是否空，取出队首元素并打印，然后检查出列节点的左节点，有的话入队，没有的话检查右节点，有的话入队，开始下次循环，这时队列里是第二层的左节点和有节点，这次是先打印2层左节点，然后让2层的左孩子节点入队，右孩子入队，然后打印2层右节点，然后2层右节点的左孩子入队，右孩子入队，队列中现在是第3层节点左边依次向右，依次类推，层次打印2x树
看在我折腾了那么多，时隔这么久才有我给答案，分就别吝啬了哈~~~嘿嘿
‘伍’ 如何用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;
//结束
}
‘陆’ C语言递归有什么用处，又有什么缺点
递归好处：代码更简洁清晰，可读性更好
递归可读性好这一点，对于初学者可能会反对。实际上递岩漏辩归的代码更清晰，但是从学习的角度要理解递归真正发生的什么，是如何调用的，调用层次和路线，调用堆栈中保存了什么，可能是不容易。但是不可否认递归的代码更简洁。一般来说，一个人可能很容易的写出前中后序的二叉树遍历的递归算法，要写出相应的非递归算法就搜渗比较考粗缺验水平了，恐怕至少一半的人搞不定。所以说递归代码更简洁明了。
递归坏处：由于递归需要系统堆栈，所以空间消耗要比非递归代码要大很多。而且，如果递归深度太大，可能系统撑不住。
‘柒’ 二叉树的层次遍历算法
二叉树的层次遍历算法有如下三种方法：
给定一棵二叉树，要求进行分层遍历，每层的节点值单独打印一行，下图给出事例结构：
之后大家就可以自己画图了，下面给出程序代码：
[cpp] view plain
void print_by_level_3(Tree T) {
vector<tree_node_t*> vec;
vec.push_back(T);
int cur = 0;
int end = 1;
while (cur < vec.size()) {
end = vec.size();
while (cur < end) {
cout << vec[cur]->data << " ";
if (vec[cur]->lchild)
vec.push_back(vec[cur]->lchild);
if (vec[cur]->rchild)
vec.push_back(vec[cur]->rchild);
cur++;
}
cout << endl;
}
}
最后给出完成代码的测试用例：124##57##8##3#6##
[cpp] view plain
#include<iostream>
#include<vector>
#include<deque>
using namespace std;
typedef struct tree_node_s {
char data;
struct tree_node_s *lchild;
struct tree_node_s *rchild;
}tree_node_t, *Tree;
void create_tree(Tree *T) {
char c = getchar();
if (c == '#') {
*T = NULL;
} else {
*T = (tree_node_t*)malloc(sizeof(tree_node_t));
(*T)->data = c;
create_tree(&(*T)->lchild);
create_tree(&(*T)->rchild);
}
}
void print_tree(Tree T) {
if (T) {
cout << T->data << " ";
print_tree(T->lchild);
print_tree(T->rchild);
}
}
int print_at_level(Tree T, int level) {
if (!T || level < 0)
return 0;
if (0 == level) {
cout << T->data << " ";
return 1;
}
return print_at_level(T->lchild, level - 1) + print_at_level(T->rchild, level - 1);
}
void print_by_level_1(Tree T) {
int i = 0;
for (i = 0; ; i++) {
if (!print_at_level(T, i))
break;
}
cout << endl;
}
void print_by_level_2(Tree T) {
deque<tree_node_t*> q_first, q_second;
q_first.push_back(T);
while(!q_first.empty()) {
while (!q_first.empty()) {
tree_node_t *temp = q_first.front();
q_first.pop_front();
cout << temp->data << " ";
if (temp->lchild)
q_second.push_back(temp->lchild);
if (temp->rchild)
q_second.push_back(temp->rchild);
}
cout << endl;
q_first.swap(q_second);
}
}
void print_by_level_3(Tree T) {
vector<tree_node_t*> vec;
vec.push_back(T);
int cur = 0;
int end = 1;
while (cur < vec.size()) {
end = vec.size();
while (cur < end) {
cout << vec[cur]->data << " ";
if (vec[cur]->lchild)
vec.push_back(vec[cur]->lchild);
if (vec[cur]->rchild)
vec.push_back(vec[cur]->rchild);
cur++;
}
cout << endl;
}
}
int main(int argc, char *argv[]) {
Tree T = NULL;
create_tree(&T);
print_tree(T);
cout << endl;
print_by_level_3(T);
cin.get();
cin.get();
return 0;
}
‘捌’ C语言根据层次遍历和中序遍历求二叉树的前序遍历和后序遍历。下面有我的建树函数，有注释的。
#include"cstdio"
#include"vector"
#include"cstring"
#include"algorithm"
using namespace std;
const int maxn =30;
struct node{
int data;
node* lchild;
node* rchild;
};
int n;
int in[maxn];
bool vis[maxn]={false};
vector<int> lev;
node* create(vector<int> lev,int inl,int inr){
if(lev.size()==0) return NULL;
if(inl>inr) return NULL;
//printf("00\n");
node* root= new node;
root->data =lev[0];
int k;
for(k=inl;k<=inr;k++){
if(lev[0]==in[k])
break;
}
for(int j=inl;j<=k-1;j++)
vis[in[j]]=true;
vector<int> tempLeft,tempRight;//要函旁埋闭数体内新建
for(int i=1;i<运裂lev.size();i++){
if(vis[lev[i]]==true)
tempLeft.push_back(lev[i]);
else
tempRight.push_back(lev[i]);
}
root->液吵lchild =create(tempLeft,inl,k-1);
root->rchild =create(tempRight,k+1,inr);
return root;
}
void preorder(node* root){
if(root==NULL)
return;
printf("%d ",root->data);
preorder(root->lchild);
preorder(root->rchild);
}
int main(){
scanf("%d",&n);
int x;
for(int i=0;i<n;i++){
scanf("%d",&x);
lev.push_back(x);
}
for(int j=0;j<n;j++)
scanf("%d",&in[j]);
node *root =create(lev,0,n-1);
preorder(root);
return 0;
}