二叉树层次遍历（什么是树的层次遍历 要求通俗易懂）

本文目录

• 什么是树的层次遍历 要求通俗易懂
• 二叉树层次遍历怎么进行
• 二叉树的层次遍历
• 二叉树层次遍历算法
• 二叉树层次遍历

什么是树的层次遍历 要求通俗易懂

二叉树的层次遍历是指从二叉树的第一层（根节点）开始，从上至下逐层遍历，在同一层中，则按照从左到右的顺序对节点逐个访问。在逐层遍历过程中，按从顶层到底层的次序访问树中元素，在同一层中，从左到右进行访问。

其思想为：用一个队列保存被访问的当前节点的左右孩子以实现层序遍历。在进行层次遍历的时候，设置一个队列结构，遍历从二叉树的根节点开始，首先将根节点指针入队列，然后从队头取出一个元素，每取一个元素，执行下面两个操作：

1、访问该元素所指向的节点。

2、若该元素所指节点的左右孩子节点非空，则将该元素所指节点的左孩子指针和右孩子指针顺序入队。此过程不断进行，当队列为空时，二叉树的层次遍历结束。

扩展资料

由于遍历中所使用的数据结构是一个队列而不是栈，因此写一个按层遍历的递归程序很困难。如下程序用来对二叉树进行逐层遍历，它采用了队列数据结构。队列中的元素指向二叉树节点。当然，也可以采用公式化队列。

程序中，仅当树非空时，才进入w h i l e循环。首先访问根节点，然后把其子节点加到队列中。当队列添加操作失败时，由Add引发NoMem异常，由于没有捕获该异常，因此当异常发生时函数将退出。在把t的子节点加入队列后，要从队列中删除t元素。

参考资料来源：百度百科-逐层遍历

二叉树层次遍历怎么进行

设计一个算法层序遍历二叉树（同一层从左到右访问）。思想：用一个队列保存被访问的当前节点的左右孩子以实现层序遍历。
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 ;
这个已经很详细了！你一定可以看懂的！加油啊！

二叉树的层次遍历

二叉树具有以下重要性质： 性质1 二叉树第i层上的结点数目最多为2i-1(i≥1)。 证明：用数学归纳法证明： 归纳基础：i=1时，有2i-1=20=1。因为第1层上只有一个根结点，所以命题成立。 归纳假设：假设对所有的j(1≤j《i)命题成立，即第j层上至多有2j-1个结点，证明j=i时命题亦成立。 归纳步骤：根据归纳假设，第i-1层上至多有2i-2个结点。由于二叉树的每个结点至多有两个孩子，故第i层上的结点数至多是第i-1层上的最大结点数的2倍。即j=i时，该层上至多有2×2i-2=2i-1个结点，故命题成立。 性质2 深度为k的二叉树至多有2k-1个结点(k≥1)。 证明：在具有相同深度的二叉树中，仅当每一层都含有最大结点数时，其树中结点数最多。因此利用性质1可得，深度为k的二叉树的结点数至多为： 20+21+…+2k-1=2k-1 故命题正确。 性质3 在任意-棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则no=n2+1。 证明：因为二叉树中所有结点的度数均不大于2，所以结点总数(记为n)应等于0度结点数、1度结点(记为n1)和2度结点数之和： n=no+n1+n2 (式子1) 另一方面，1度结点有一个孩子，2度结点有两个孩子，故二叉树中孩子结点总数是： nl+2n2 树中只有根结点不是任何结点的孩子，故二叉树中的结点总数又可表示为： n=n1+2n2+1 (式子2) 由式子1和式子2得到： no=n2+1 满二叉树和完全二叉树是二叉树的两种特殊情形。 1、满二叉树(FullBinaryTree) 一棵深度为k且有2k-1个结点的二又树称为满二叉树。 满二叉树的特点： （1） 每一层上的结点数都达到最大值。即对给定的高度，它是具有最多结点数的二叉树。 （2） 满二叉树中不存在度数为1的结点，每个分支结点均有两棵高度相同的子树，且树叶都在最下一层上。 【例】图(a)是一个深度为4的满二叉树。 2、完全二叉树(Complete BinaryTree) 若一棵二叉树至多只有最下面的两层上结点的度数可以小于2，并且最下一层上的结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树。 特点： （1） 满二叉树是完全二叉树，完全二叉树不一定是满二叉树。 （2） 在满二叉树的最下一层上，从最右边开始连续删去若干结点后得到的二叉树仍然是一棵完全二叉树。 （3） 在完全二叉树中，若某个结点没有左孩子，则它一定没有右孩子，即该结点必是叶结点。 【例】如图(c)中，结点F没有左孩子而有右孩子L，故它不是一棵完全二叉树。 【例】图(b)是一棵完全二叉树。 性质4 具有n个结点的完全二叉树的深度为 证明：设所求完全二叉树的深度为k。由完全二叉树定义可得： 深度为k得完全二叉树的前k-1层是深度为k-1的满二叉树，一共有2k-1-1个结点。 由于完全二叉树深度为k，故第k层上还有若干个结点，因此该完全二叉树的结点个数： n》2k-1-1。 另一方面，由性质2可得： n≤2k-1， 即：2k-1-l《n≤2k-1 由此可推出：2k-1≤n《2k，取对数后有： k-1≤lgn《k 又因k-1和k是相邻的两个整数，故有 , 由此即得： 注意： 的证明【参见参考书目】

二叉树层次遍历算法

#include《stdio.h》
#include《stdlib.h》
typedef char datatype;
typedef struct node
{datatype data;
struct node *lchild,*rchild;
}bitree;
bitree *Q;
bitree *creat()
{
bitree *root,*s;
int front,rear;
root=NULL;
char ch;
front=1;rear=0;
ch=getchar();
while(ch!=’0’)
{
s=NULL;
if(ch!=’@’)
{s=(bitree *)malloc(sizeof(bitree));
s-》data=ch;
s-》lchild=NULL;
s-》rchild=NULL;
}
rear++;
Q[rear]=s;
if(rear==1)
root=s;
else
{
if(s&&Q[front])
if(rear%2==0)
Q[front]-》lchild=s;
else
Q[front]-》rchild=s;
if(rear%2==1)
front++;
}
ch=getchar();
}
return root;
}
void cengci(bitree *t)
{
bitree *Queue,*p;
int front=0,rear=0;
if(t)
{
p=t;
Queue[rear]=p;
rear=(rear+1)%20;
while(front!=rear)
{
p=Queue[front];
printf(“%c“,p-》data);
front=(front+1)%100;
if(p-》lchild)
{
Queue[rear]=p-》lchild;
rear=(rear+1)%100;
}
if(p-》rchild)
{
Queue[rear]=p-》rchild;
rear=(rear+1)%20;
}
}
}
}

void main()
{struct node *tree;
tree=(bitree *)malloc(sizeof(bitree));
tree=creat();
cengci(tree);
}

二叉树层次遍历

/**
 * 层序遍历
 */
void LevelOrderTraversal(BinTree *BT) {
BinTree *T;
T = BT;
if (!T) {
return;
}
Queue *Q = InitQueue();  /* 生成一个队列 */
EnQueue(Q, T);  /* 根节点入队 */
while (!IsQueueEmpty(Q)) {  /* 队列不为空,弹出一个元素 */
T = DeQueue(Q);
Visited(T);  /* 访问 */
if (T-》Left)  /* 左子树不为空入队 */
EnQueue(Q, T-》Left);
if (T-》Right)  /* 右子树不为空入队 */
EnQueue(Q, T-》Right);
}
}

你的代码貌似不对，原因是：你只是把根节点进了队列！看看我写的！

同时你也可以直接用百度搜索“C实现二叉树（模块化集成，遍历的递归与非递归实现）”，这是博客园的一个博文，里面有关二叉树的前中后层遍历的递归与非递归算法，比较全面。