当前位置：首页 > news >正文

二叉树的层序遍历及代码

news 2026/6/16 17:10:51

5.3.1二叉树的层序遍历

1781599348994

1781599362200

#include<stdio.h>void LevelOrder(BiTree T){LinkQueue Q;InitQueue(Q);// 初始化辅助队列 BiTree p;EnQueue(Q,T);//将根节点入队 while(!IsEmpty(Q)){//队列不空则循环 DeQueue(Q,p);//对头结点出队 visit(p);//访问出队节点 if(p->lchild!=NULL)Enqueue(Q,p->lchild)//左孩子入队 if(p->rchild!=NULL)Enqueue(Q,p->rchild)//右孩子入队 }
}

1781600114968

#include<stdio.h>
#include<stdlib.h>//二叉树的结点（链式存储） 
typedef struct BiTNode{char data;struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;//链式队列结点 
typedef struct LinkNode{BiTNode *data;struct LinkNode *next;
}LinkNode;typedef struct{LinkNode *front,*rear;//队头队尾 
}LinkQueue; void LevelOrder(BiTree T){LinkQueue Q;InitQueue(Q);// 初始化辅助队列 BiTree p;EnQueue(Q,T);//将根节点入队 while(!IsEmpty(Q)){//队列不空则循环 DeQueue(Q,p);//对头结点出队 visit(p);//访问出队节点 if(p->lchild!=NULL)EnQueue(Q,p->lchild);//左孩子入队 if(p->rchild!=NULL)EnQueue(Q,p->rchild);//右孩子入队 }
}

# 可运行
#include<stdio.h>
#include<stdlib.h>//二叉树结点
typedef struct BiTNode{char data;struct BiTNode *lchild,*rchild;
}BiTNode, *BiTree;//链式队列结点
typedef struct LinkNode{BiTNode *data;struct LinkNode *next;
}LinkNode;typedef struct{LinkNode *front,*rear;
}LinkQueue;//队列基础函数声明
void InitQueue(LinkQueue *Q);
bool IsEmpty(LinkQueue *Q);
bool EnQueue(LinkQueue *Q, BiTNode *x);
bool DeQueue(LinkQueue *Q, BiTNode *&x);
void visit(BiTNode *p);//层序遍历
void LevelOrder(BiTree T){if(T == NULL) return;  //空树直接返回LinkQueue Q;InitQueue(&Q);         //传队列地址BiTree p;EnQueue(&Q, T);while(!IsEmpty(&Q)){DeQueue(&Q, p);visit(p);if(p->lchild != NULL)EnQueue(&Q, p->lchild);if(p->rchild != NULL)EnQueue(&Q, p->rchild);}
}//访问函数
void visit(BiTNode *p){printf("%c ", p->data);
}//下面是配套队列实现（大题可一并写上，完整不丢分）
void InitQueue(LinkQueue *Q){Q->front = Q->rear = (LinkNode*)malloc(sizeof(LinkNode));Q->front->next = NULL;
}bool IsEmpty(LinkQueue *Q){return Q->front == Q->rear;
}bool EnQueue(LinkQueue *Q, BiTNode *x){LinkNode *s = (LinkNode*)malloc(sizeof(LinkNode));s->data = x; s->next = NULL;Q->rear->next = s;Q->rear = s;return true;
}bool DeQueue(LinkQueue *Q, BiTNode *&x){if(IsEmpty(Q)) return false;LinkNode *p = Q->front->next;x = p->data;Q->front->next = p->next;if(Q->rear == p) Q->rear = Q->front;free(p);return true;
}

1781600177873