按层次遍历二叉树的算法

Ⅰ 二叉树的层次遍历

二叉树具有以下重要性质： 性质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是相邻的两个整数，故有 , 由此即得： 注意： 的证明【参见参考书目】

Ⅱ 在按层次遍历二叉树的算法中，需要借助的辅助数据结构是

辅助的就是队列了，如果是堆栈就成了深度优先算法了；其实这里辅助结构决定了算法的性质，你可以换成最大堆，最小堆等，就可以达到很多不同的效果

Ⅲ 二叉树--按层遍历

今天练习的算法是按层遍历一个二叉树。

我们还是用这张老的二叉树来举例子吧：

按层遍历的意思是从树的跟节点开始，一层层遍历并输出节点的值。输出的结果使用二维的数组存放，我们使用List<List<Integer>>来表示。上图的结果为：
[
[F],
[B,G],
[A,D,I],
[C,E,H]
]

老规矩先看图：

实现最主要的技巧就是使用队列（Queue），我还是使用递归的思想来分析吧，每次进入递归前带有四个参数orderList、queue、level、preSize。
先稍微分析下四个参数作用吧：

基本实现逻辑如下：
1.先从根节点开始，初始化orderList、queue、level、preSize，其中orderList为空，queue中存放root节点，level为0，preSize为1。
2.进入递归方法，首先循环从queue队列中取出preSize数量的节点；然后挨个遍历取出的节点，将节点的值添加到orderList对应的层(level)中；同时将节点的左右子节点均添加到queue队列中，并且记录存放到queue中的节点数量以备下次递归使用；最后根据记录的下一层节点数量判断是否需要继续递归。

核心是要边遍历某一层的时候同时将该层节点的所有节点添加到queue中，并且记录下一层总的节点数，这样才能保证下一层遍历时不会从队列中取到非该层的节点。

算法相关实现源码地址： https://github.com/xiekq/rubs-algorithms

Ⅳ 求用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);
}

Ⅳ 以二叉连表做存储结构，试编写按层次顺序遍历二叉树的算法

//二叉树，按层次访问
//引用如下地址的思想，设计一个算法层序遍历二叉树（同一层从左到右访问）。思想：用一个队列保存被访问的当前节点的左右孩子以实现层序遍历。
//http://..com/link?url=a9ltidaf-SQzCIsa
typedef struct tagMyBTree
{
int data;
struct tagMyBTree *left,*right;
}MyBTree;

void visitNode(MyBTree *node)
{
if (node)
{
printf("%d ", node->data);
}

}
void visitBTree(queue<MyBTree*> q);
void createBTree(MyBTree **tree)
{
int data = 0;
static int initdata[15] = {1,2,4,0,0,5,0,0,3,6,0,0,7,0,0};//构造成满二叉树，利于查看结果
static int i = 0;
//scanf("%d", &data);
data = initdata[i++];
if (data == 0)
{
*tree = NULL;
}
else
{
*tree = (MyBTree*)malloc(sizeof(MyBTree));
if (*tree == NULL)
{
return;
}
(*tree)->data = data;

createBTree(&(*tree)->left);

createBTree(&(*tree)->right);

}
}

void visitBTreeTest()
{
queue<MyBTree*> q;
MyBTree *tree;
createBTree(&tree);
q.push(tree);
visitBTree(q);
}

void visitBTree(queue<MyBTree*> q)
{
if (!q.empty())
{
MyBTree *t = q.front();
q.pop();
visitNode(t);
if (t->left)
{
q.push(t->left);
}
if (t->right)
{
q.push(t->right);
}

visitBTree(q);
}
}

Ⅵ 写出层次遍历二叉树的算法。（提示：可以利用队列作为辅助工具）

void TravLevel(BTNode *b)
{
BTNode *Qu[MaxSize]; //定义循环队列
int front,rear; //定义队首和队尾指针
front=rear=0; //置队列为空队列
if (b!=NULL)
printf("%c ",b->data);
rear++; //结点指针进入队列
Qu[rear]=b;
while (rear!=front) //队列不为空
{
front=(front+1)%MaxSize;
b=Qu[front]; //队头出队列
if (b->lchild!=NULL) //输出左孩子,并入队列
{
printf("%c ",b->lchild->data);
rear=(rear+1)%MaxSize;
Qu[rear]=b->lchild;
}
if (b->rchild!=NULL) //输出右孩子,并入队列
{
printf("%c ",b->rchild->data);
rear=(rear+1)%MaxSize;
Qu[rear]=b->rchild;
}
}
printf("\n");
}

Ⅶ 二叉树层次遍历算法

#include<stdio.h>
#include<stdlib.h>
typedef char datatype;
typedef struct node
{datatype data;
struct node *lchild,*rchild;
}bitree;
bitree *Q[100];
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[100],*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);
}