本文目录一览：
- 1、如何用C语言实现层次遍历二叉树?
- 2、用c语言编一个算法 按层次遍历二叉树的结点?
- 3、由中序遍历和层次遍历还原二叉树。C语言实现
- 4、求用C语言实现二叉树层次遍历的递归算法，谢谢！！！
- 5、C语言 层次遍历二叉树
如何用C语言实现层次遍历二叉树?
2叉树没有层次遍历
只有先序遍历，中序遍历，和后续遍历三种
用c语言编一个算法 按层次遍历二叉树的结点?
#includestdio.h
#includemalloc.h
// 定义队列的最大长度
#define QUEUE_LENGTH 100
//
// 二叉树与双向链表数据结构定义，
//
typedef struct struNode
{
int data;
struct struNode *lchild; //二叉树中的左子树或双向链表中的前向指针
struct struNode*rchild; //二叉树中的右子树或双向链表中的后向指针
}BitNode , *BitNodePtr , DuLNode , *DuLNodePtr;
//
// 生成二叉树
//
BitNodePtr Create_bitree()
{
int m;
BitNodePtr T;
T = NULL;
scanf("%d", m);
if(m)
{
T = (BitNodePtr)malloc(sizeof(BitNode));
T-data = m;
T-lchild = Create_bitree();
T-rchild = Create_bitree();
}
return T;
}
//
// 层次遍历二叉树
//
void ReadBitTree(BitNodePtr pRoot)
{
BitNodePtr pQueue[QUEUE_LENGTH];
int head = 0 , tail = 1;
pQueue[0] = pRoot;
//结束的条件是head向后移动一个位置后，与tail重合
while (head != tail)
{
printf("%d " , pQueue[head]-data);
//左孩子入队列
if (pQueue[head]-lchild)
{
pQueue[tail] = pQueue[head]-lchild;
tail = (tail + 1) % QUEUE_LENGTH;
if (tail == head)
{
//队列长度太小，退出
printf("Queue overflow!");
return;
}
}
//右孩子入队列
if (pQueue[head]-rchild)
{
pQueue[tail] = pQueue[head]-rchild;
tail = (tail + 1) % QUEUE_LENGTH;
if (tail == head)
{
//队列长度太小，退出
printf("Queue overflow!");
return;
}
}
//队首出队列
head = (head + 1) % QUEUE_LENGTH;
}
printf("\n");
return;
}
void main()
{
BitNodePtr Root;
Root = Create_bitree();
ReadBitTree(Root);
return;
}
由中序遍历和层次遍历还原二叉树。C语言实现
经测，该代码已经修改正确，只需在void BuildTree(char *level,char *inorder,pBiTree T)这里的最后一个变量T改为引用即可。还有一个地方判断调用右子树的地方的判断条件。
#include stdio.h
#include stdlib.h
#include string.h
typedef struct _BiTree
{
char data;
struct _BiTree *lchild;
struct _BiTree *rchild;
}BiNode, *pBiTree;
void BuildTree(char *level,char *inorder,pBiTree T)
{
int i;
int len=strlen(level); //取得层次遍历长度
int pos=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);
}
}
void priOrder(pBiTree T)
{
if (T != NULL){
printf ("%c", T-data);
priOrder(T-lchild);
priOrder(T-rchild);
}
}
void postOrder(pBiTree T)
{
if (T != NULL){
postOrder(T-lchild);
postOrder(T-rchild);
printf ("%c", T-data);
}
}
void freeNode(pBiTree T)
{
if (T != NULL){
freeNode(T-lchild);
freeNode(T-rchild);
free(T);
}
}
int main()
{
pBiTree root;
char level[28], inorder[28];
int n;
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 ("\n");
postOrder(root);
printf ("\n");
//freeNode(root);
}
return 0;
}
求用C语言实现二叉树层次遍历的递归算法，谢谢！！！
算法思想：层次遍历目前最普遍用的就是队列的那种方式，不是递归，但是用到while循环，既然题目要求用递归，可以用递归实现该while循环功能。算法如下：
void TransLevele(Tree *r)
{
if (r==NULL)
{
return ;
}
printf("%c",r-ch);
if (r-left != NULL)
{
InsertQueue(r-left);
}
if (r-right != NULL)
{
InsertQueue(r-right);
}
Tree *t = DeleteQueue();
TransLevele(t);
}
//测试程序，创建树输入例如ABD##E##C##,根左右创建的方式。
如下代码是测试通过的。
#include "stdlib.h"
#define MAX 100
typedef int Element;
typedef struct tree
{
Element ch;
struct tree *left;
struct tree *right;
}Tree;
typedef struct queue
{
Tree *a[MAX];
int front;
int rear;
}Queue;
Queue Qu;
void Init();
int InsertQueue(Element ch);
Tree *DeleteQueue();
void CreateTree(Tree **r);
void TransLevele(Tree *r);
void PrintTree(Tree *r);
int main()
{
Tree *r=NULL;
CreateTree(r);
PrintTree(r);
printf("\n");
TransLevele(r);
return 0;
}
void Init()
{
int i=0;
for (i=0; iMAX; i++)
{
Qu.a[i] = NULL;
}
Qu.front = 0;
Qu.rear = 0;
}
int InsertQueue(Tree *r)
{
if ( (Qu.rear+1)%MAX == Qu.front)
{
printf("Queue full!");
return 0;
}
Qu.a[Qu.rear] = r;
Qu.rear = (Qu.rear+1)%MAX;
return 1;
}
Tree *DeleteQueue()
{
if (Qu.front == Qu.rear)
{
printf("Queue empty");
return NULL;
}
Tree *t=NULL;
t = Qu.a[Qu.front];
Qu.front = (Qu.front+1)%MAX;
return t;
}
void CreateTree(Tree **r)
{
Element ch;
ch=getchar();
if (ch=='#')
{
(*r)=NULL;
return ;
}
*r = (Tree *)malloc(sizeof(Tree));
(*r)-ch = ch;
CreateTree(((*r)-left));
CreateTree(((*r)-right));
}
void PrintTree(Tree *r)
{
if (r==NULL)
{
return ;
}
printf("%c",r-ch);
PrintTree(r-left);
PrintTree(r-right);
}
void TransLevele(Tree *r)
{
if (r==NULL)
{
return ;
}
printf("%c",r-ch);
if (r-left != NULL)
{
InsertQueue(r-left);
}
if (r-right != NULL)
{
InsertQueue(r-right);
}
Tree *t = DeleteQueue();
TransLevele(t);
}
C语言 层次遍历二叉树
//队列的操作代码你自己写吧？
void
HierarchyBiTree(BiTree
Root){
LinkQueue
*Q;
//
保存当前节点的左右孩子的队列
InitQueue(Q);
//
初始化队列
if
(Root
==
NULL)
return
;
//树为空则返回
BiNode
*p
=
Root;
//
临时保存树根Root到指针p中
Visit(p-data);
//
访问根节点
if
(p-lchild)
EnQueue(Q,
p-lchild);
//
若存在左孩子，左孩子进队列
if
(p-rchild)
EnQueue(Q,
p-rchild);
//
若存在右孩子，右孩子进队列
while
(!QueueEmpty(Q))
//
若队列不空，则层序遍历
{
DeQueue(Q,
p);
//
出队列
Visit(p-data);//
访问当前节点
if
(p-lchild)
EnQueue(Q,
p-lchild);
//
若存在左孩子，左孩子进队列
if
(p-rchild)
EnQueue(Q,
p-rchild);
//
若存在右孩子，右孩子进队列
}
DestroyQueue(Q);
//
释放队列空间
return
;
}
