层次遍历递归算法c语言

㈠ 层次序的非递归遍历算法的实现代码(C语言)

层次遍历算法：（用队列的方法）
[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>

㈡ 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
}

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

㈣ 二叉树的层次遍历是递归的算法吗

层次遍历从方法上不具有递归的形式，所以一般不用递归实现。当然了，非要写成递归肯定也是可以的，大致方法如下。 void LevelOrder(BTree T, int cnt) { BTree level = malloc(sizeof(struct BTNode)*cnt); if(level==NULL) return; int i=0,rear=0; if(cnt==0) return; for(i=0; i<cnt; i++){ printf("%c ",T[i].data); if(T[i].lchild) level[rear++]=*T[i].lchild; if(T[i].rchild) level[rear++]=*T[i].rchild; } printf("\n"); LevelOrder(level, rear); free(level); } 补充一下，在main里面调用的时候就得用LevelOrder(T,1)了。

㈤ 二叉树的层次遍历算法

二叉树的层次遍历算法有如下三种方法：

给定一棵二叉树，要求进行分层遍历，每层的节点值单独打印一行，下图给出事例结构：

之后大家就可以自己画图了，下面给出程序代码：

[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语言实现

经测，该代码已经修改正确，只需在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语言实现层次遍历二叉树

下面是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语言)..

是二叉链表的层次遍历吧？

#include<stdlib.h>
//定义动态分配空间的二叉链表类型
typedefstructBiTNode{
chardata;
structBiTNode*lchild,*rchild;
}BiTNode,*BiTree;
//层次遍历输出二叉链表的所有结点的值
voidLevelOrderTraverse(BiTreeT){
typedefstructPNode{
BiTNode*ptr;structPNode*next;
}PNode;//定义链表结点类型，链表的数据域存放二叉链表结点的指针
PNode*R,*L,*p;
if(T){
R=(PNode*)malloc(sizeof(PNode));//建立第一个链表结点
if(!R){
printf("
LevelOrderTraverseError:FailedToMALLOCMemory!");
return;
}
R->ptr=T;R->next=NULL;//R指向尾结点，尾结点指针域必须为空
L=R;p=L;//L指向链表头结点
while(p){//p结点的数据域指向当前处理的二叉链表结点
printf("%c",p->ptr->data);
if(p->ptr->lchild){//如果有左孩子，添加一个结点
R->next=(PNode*)malloc(sizeof(PNode));
if(!(R->next)){
printf("
LevelOrderTraverseError:FailedToMALLOCMemory!");
return;
}
R=R->next;R->ptr=p->ptr->lchild;R->next=NULL;//R重新指向尾结点，尾结点的数据域为当前处理的二叉链表结点的左孩子指针
}
if(p->ptr->rchild){//如果有右孩子，添加一个结点
R->next=(PNode*)malloc(sizeof(PNode));
if(!(R->next)){
printf("
LevelOrderTraverseError:FailedToMALLOCMemory!");
return;
}
R=R->next;R->ptr=p->ptr->rchild;R->next=NULL;
}
L=p->next;//L指向下一个链表结点，准备释放p结点
free(p);//释放p结点
p=L;//p重新指向链表头结点
}
}
}

这里使用了队列结构来存储某个结点的孩子结点。