按層次遍歷二叉樹的演算法

Ⅰ 二叉樹的層次遍歷

二叉樹具有以下重要性質： 性質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);
}