当前位置:首页 » 编程语言 » 层次遍历二叉树算法c语言
扩展阅读
webinf下怎么引入js 2023-08-31 21:54:13
堡垒机怎么打开web 2023-08-31 21:54:11

层次遍历二叉树算法c语言

发布时间: 2022-07-24 09:03:17

A. 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
}

B. 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
;
}

C. 请帮忙写一下二叉树的层序遍历,用C语言实现

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#define N 100
typedef struct tnode
{
struct tnode *lchild;
struct tnode *rchild;
char data;
}TNode;
typedef struct node
{
TNode **front;
TNode **rear;
}QNode;
/*
**创建二叉树
*/
void
init_tree(TNode *&p)
{
char data;
scanf("%c",&data);
if(data!='#'){
p=(TNode *)malloc(sizeof(TNode));
assert(p!=NULL);
p->data=data;
init_tree(p->lchild);
init_tree(p->rchild);
}
else p=NULL;
}
/*
**广度遍历二叉树
*/
void
guang_show(TNode *p)
{
QNode Q;
Q.front=Q.rear=(TNode **)malloc(N*sizeof(TNode *));
assert(Q.rear!=NULL);
*Q.rear++=p;
while(Q.front!=Q.rear){
printf("%c",(*(Q.front))->data);
p=*Q.front++;
if(p->lchild!=NULL)*Q.rear++=p->lchild;
if(p->rchild!=NULL)*Q.rear++=p->rchild;
}
printf("\n");
}

int
main()
{
TNode *p;
init_tree(p);
guang_show(p);
return 0;
}

D. 用c语言实现二叉树的层次遍历(用非递归方法)

使用队列,每出一个节点,将该节点的子节点入队。so easy

E. C语言二叉树的创建和遍历

我写了一个二叉树 你给看看 一定能行的 我自己用了
#include "stdio.h"
#include "malloc.h"
#include "string.h"
#include "stdlib.h"
#define Max 20 //结点的最大个数
typedef struct BinTNode{
char data;
struct BinTNode *lchild,*rchild;
}BinTNode,*BinTree; //自定义二叉树的结点类型
//定义二叉树的指针
int NodeNum,leaf; //NodeNum为结点数,leaf为叶子数

//==========以广义表显示二叉树==============
void DisTree(BinTree T)
{
if(T)
{
printf("%c",T->data);
if((T->lchild)||(T->rchild))
{
if(T->lchild)
{
printf("%c",'(');
DisTree(T->lchild);
}
if(T->rchild)
{
printf("%c",',');
DisTree(T->rchild);
printf("%c",')');
}
}
}
}
//==========基于先序遍历算法创建二叉树==============
//=====要求输入先序序列,其中加入虚结点"#"以示空指针的位置==========
BinTree CreatBinTree(BinTree T)
{
char ch;
ch=getchar();
if(ch=='#')
T=NULL;
else
{
if(!(T=(BinTNode *)malloc(sizeof(BinTNode))))
printf("Error!");
T->data=ch;
T->lchild=CreatBinTree(T->lchild);
T->rchild=CreatBinTree(T->rchild);
}
return T;
}
//========NLR 先序遍历=============
void Preorder(BinTree T)
{
if(T)
{
printf("%c",T->data);
Preorder(T->lchild);
Preorder(T->rchild);
}
}
//========LNR 中序遍历===============
void Inorder(BinTree T)
{
if(T){
Inorder(T->lchild);
printf("%c",T->data);
Inorder(T->rchild);
}
}
//==========LRN 后序遍历============
void Postorder(BinTree T)
{
if(T){
Postorder(T->lchild);
Postorder(T->rchild);
printf("%c",T->data);
}
}
//=====采用后序遍历求二叉树的深度、结点数及叶子数的递归算法========
int TreeDepth(BinTree T)
{
int hl,hr,max;
if(T){
hl=TreeDepth(T->lchild); //求左深度
hr=TreeDepth(T->rchild); //求右深度
max=hl>hr? hl:hr; //取左右深度的最大值
NodeNum=NodeNum+1; //求结点数
if(hl==0&&hr==0)
leaf=leaf+1; //若左右深度为0,即为叶子。
return(max+1);
}
else return(0);
}
//====利用"先进先出"(FIFO)队列,按层次遍历二叉树==========
void Levelorder(BinTree T)
{
int front=0,rear=1;
BinTNode *cq[Max],*p; //定义结点的指针数组cq
cq[1]=T; //根入队
while(front!=rear)
{
front=(front+1)%NodeNum;
p=cq[front]; //出队
printf("%c",p->data); //出队,输出结点的值
if(p->lchild!=NULL){
rear=(rear+1)%NodeNum;
cq[rear]=p->lchild; //左子树入队
}
if(p->rchild!=NULL){
rear=(rear+1)%NodeNum;
cq[rear]=p->rchild; //右子树入队
}
}
}
//==========主函数=================
void main()
{
BinTree T,root;
int i,depth;
printf("\n");
printf("输入完全二叉树的先序序列:"); //输入完全二叉树的先序序列,
// 用#代表虚结点,如ABD###CE##F##
root=CreatBinTree(T); //创建二叉树,返回根结点
DisTree(root);
printf("\n");
do //从菜单中选择遍历方式,输入序号。
{
printf("\t********** 菜单 ************\n");
printf("\n");
printf("\t1: 先序遍历\n");
printf("\t2: 中序遍历\n");
printf("\t3: 后序遍历\n");
printf("\t4: 该树的深度,结点数,叶子数\n");
printf("\t5: 层次遍历\n"); //按层次遍历之前,先选择4,求出该树的结点数。
printf("\t0: 退出\n");
printf("\t*******************************\n");
scanf("%d",&i);
//输入菜单序号(0-5)
switch(i)
{
case 1: {printf("Print Bin_tree Preorder: ");
Preorder(root); //先序遍历
}break;
case 2: {printf("Print Bin_Tree Inorder: ");
Inorder(root); //中序遍历
}break;
case 3: {printf("Print Bin_Tree Postorder: ");
Postorder(root); //后序遍历
}break;
case 4: {depth=TreeDepth(root); //求树的深度及叶子数
printf("树深=%d 树总结点数=%d",depth,NodeNum);
printf(" 树叶子数=%d",leaf);
}break;
case 5: {printf("LevePrint Bin_Tree: ");
Levelorder(root); //按层次遍历
}break;
default: exit(1);
}
}while(i>=0&&i<6);
}

兄弟你看看 不懂再往下留言 记得给我的劳动成果一点点奖励哦!!

F. 如何用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;
//结束
}

G. 求一个c语言遍历二叉树的算法

#include <stdio.h>
#include <stdlib.h>
//1 根据二叉树的性质5,结点按完全二叉树来编号,则根据结点编号,
// 就可算出其双亲结点的编号,以及该结点是左孩子还是右孩子,
// 这样一来,就可把该结点的指针赋予双亲结点的相应指针域。
// 怎样找到双亲结点呢?,在输入双亲结点的同时要把结点的指针
// 保存起来。也就是说,要设计一个指针数组,来保存每个结点指针。
// 这样,当输入下层结点时,才能找到它的双亲。
//2 回想单链表的建立过程,单链表建立过程中,只需把当前结点,
// 当成前驱结点,故只需设计一个指针变量即可。

typedef char ElementType;

typedef struct node //二叉树链表结点
{
ElementType data;
struct node *lchild,*rchild;//左、右孩子指针
}BinNode,*BinTree; //结点和结点指针的标识符

BinNode * creat(void) //建二叉树链表(返回根结点的指针)
{
int i,j;
ElementType x;
BinNode *q,*s[20];//结点指针、辅助数组(存放结点的指针,该结点有可能是双亲结点)
BinNode *t=NULL; //根结点指针(目前是空树,生成树后要返回根结点指针)

printf("\n 请输入结点编号i和结点值x");
printf("\n 如:1A 2B 3C 4D 5E 7F 00(全为0,输入结束)");
printf("\n 或:1A 2B 3C 4D 6F 7G 00(全为0,输入结束)");
printf("\n 或:1A 2B 3C 5E 7G 15M 00(全为0,输入结束)\n");
scanf("%d%c",&i,&x); //输入结点编号及结点值

while((i!=0)&&(x!=0))
{
q=(BinNode *)malloc(sizeof(BinNode));//申请结点内存
q->data=x; //保存数据
q->lchild=NULL;
q->rchild=NULL;
s[i]=q; //s[i]存放第i号结点的指针
if(i==1) //1号结点是根结点
t=q; //保存根结点指针,以备返回
else
{
j=i/2; //由该结点号求双亲结点号
if((i%2)==0)
s[j]->lchild=q; //i为偶数是左孩子,该结点指针存入双亲结点的左孩子指针
else
s[j]->rchild=q; //i为奇数是右孩子,该结点指针存入双亲结点的右孩子指针
}
scanf("%d%c",&i,&x);//继续输入结点编号和结点值
}
return t; //返回根结点的指针(二叉链表的指针)
}

void DisplayBinTree(BinTree T)//用缩进表示二叉树
{
BinTree stack[100],p; //栈(结点指针数组)、当前结点指针
int level[100]; //栈(每层根结点对应的空格 数 )
int flag[100]; //栈(flag[]=0,1,2分别表示是根结点、左子树、右子树 )
int top,n,i; //栈顶指针,空格个数,循环变量

if(T!=NULL) //若有根结点
{
top=1; //1号结点(根结点 )
stack[top]=T; //入栈(保存根结点指针)
level[top]=1; //显示空格的个数
flag[top]=0; //根结点
while(top>0) //有根结点
{
p=stack[top]; //取根结点指针
n=level[top]; //取显示空格的个数

for(i=1;i<=n;i++)//显示空格(缩进)
printf(" ");

if(flag[top]==0) //若是根结点
printf("T:%c\n",p->data); //显示根结点
else //不是根结点
{
if(flag[top]==2) //是右子树根结点
printf("R:%c\n",p->data); //显示右子树根结点
if(flag[top]==1) //是左子树根结点
printf("L:%c\n",p->data,top); //显示左子树根结点
}

top--; //显示一个(出栈一个)结点,top-1

if(p->rchild!=NULL)//若有右孩子
{
top++; //保存一个根结点,top+1
stack[top]=p->rchild;//保存右子树根结点
level[top]=n+3;
flag[top]=2;
}
if(p->lchild!=NULL)//若有左孩子
{
top++;
stack[top]=p->lchild;//保存左子树根结点
level[top]=n+3;
flag[top]=1;
}
// printf("level[top]=%d\n",level[top]);
}
}
}

main()
{
BinNode *T; //根结点的指针
T=creat(); //建二叉树
printf("\n用缩进表示二叉树的层次(如ppt62所示):\n");
DisplayBinTree(T);
getch();
}

H. 求用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; i<MAX; 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);
}