二叉樹層次遍歷演算法
『壹』 設二叉樹以二叉鏈表存儲，試設計演算法，實現二叉樹的層序遍歷。
按層次遍歷演算法如下：
#include <iostream>
using namespace std;
typedef struct treenode { //樹結點結構
int data;
struct treenode *left;
struct treenode *right;
}TreeNode;
typedef struct stack{ //棧結點結構
TreeNode *node;
struct stack *next;
}STACK;
void Traversal(TreeNode *root)
{
STACK *head = NULL;
STACK *tail = NULL;
if (root != NULL) //根結點入棧
{
head = new STACK();
head->next = NULL;
head->node = root;
tail = head;
}
while(head != NULL)
{
STACK *temp;
if (head->node->left != NULL) //棧頂結點的左結點入棧
{
temp = new STACK();
temp->next = NULL;
temp->node = head->node->left;
tail->next = temp;
tail = temp;
}
if (head->node->right != NULL) //棧頂結點的右結點入棧
{
temp = new STACK();
temp->next = NULL;
temp->node = head->node->right;
tail->next = temp;
tail = temp;
}
cout<<head->node->data<<endl; //結點出棧
temp = head;
head = head->next;
delete(head);
}
}
『貳』 層序遍歷二叉樹
#include<stdio.h>
#include<stdlib.h>
#define m 100
typedef char etype;
typedef struct bitnode
{
etype data;
struct bitnode *lch,*rch;
}bitnode,*bitree;
bitree que[m];
int front=0,rear=0;
bitnode *creat_bt1();
bitnode *creat_bt2();
void preorder(bitnode *p);
void inorder(bitnode *p);
void postorder(bitnode *p);
void enqueue(bitree);
bitree delqueue();
void levorder(bitree);
int treedepth(bitree);
void prtbtree(bitree,int);
void exchange(bitree);
int leafcount(bitree);
void paintleaf(bitree);
bitnode *t;
int count=0;
void main()
{
char ch;int k;
do{
printf("\n\n\n");
printf("\n==========主菜單==============");
printf("\n 1.建立二叉樹方法 1");
printf("\n 2.建立二叉樹方法 2");
printf("\n 3.先序遞歸遍歷二叉樹");
printf("\n 4.中序遞歸遍歷二叉樹");
printf("\n 5.後序遞歸遍歷二叉樹");
printf("\n 6.層次遍歷二叉樹");
printf("\n 7.計算二叉樹的高度");
printf("\n 8.計算二叉樹中葉結點個數");
printf("\n 9.交換二叉樹的左右子樹");
printf("\n 10.列印二叉樹");
printf("\n 0.結束程序運行");
printf("\n===============================");
printf("\n 請輸入您的選擇(0,1,2,3,4,5,6,7,8,9,10)");
scanf("%d",&k);
switch(k)
{case 1:t=creat_bt1();break;
case 2:printf("\n請輸入二叉樹各節點的值：");fflush(stdin);
t=creat_bt2();break;
case 3:if(t)
{printf("先序遍歷二叉樹：");
preorder(t);
printf("\n");
}
else printf("二叉樹為空!\n");
break;
case 4:if(t)
{printf("中序遍歷二叉樹：");
inorder(t);
printf("\n");
}
else printf("二叉樹為空!\n");
break;
case 5:if(t)
{printf("後序遍歷二叉樹：");
postorder(t);
printf("\n");
}
else printf("二叉樹為空!\n");
break;
case 6:if(t)
{printf("層次遍歷二叉樹：");
levorder(t);
printf("\n");
}
else printf("二叉樹為空!\n");
break;
case 7:if(t)
{printf("二叉樹的高度為：%d",treedepth(t));
printf("\n");
}
else printf("二叉樹為空!\n");
break;
case 8:if(t)
{printf("二叉樹的葉子結點數為：%d\n",leafcount(t));
printf("二叉樹的葉結點數為：");paintleaf(t);
printf("\n");
}
else printf("二叉樹為空!\n");
break;
case 9:if(t)
{printf("二叉樹的左右子樹：\n");
exchange(t);
prtbtree(t,0);
printf("\n");
}
else printf("二叉樹為空!\n");
break;
case 10:if(t)
{printf("逆時針旋轉90度輸出的二叉樹：\n");
prtbtree(t,0);
printf("\n");
}
else printf("二叉樹為空!\n");
break;
case 0:exit(0);
}
}while(k>=1&&k<=10);
printf("\n再見! 按回車鍵，返回…\n");
ch=getchar();
}
bitnode *creat_bt1()
{
bitnode *t,*p,*v[20];int i,j;etype e;
printf("\n請輸入二叉樹各結點的編號和對應的值(如：1，a):");
scanf("%d,%c",&i,&e);
while(i!=0&&e!='#')
{
p=(bitnode *)malloc(sizeof(bitnode));
p->data=e;p->lch=NULL;p->rch=NULL;
v[i]=p;
if(i==1)t=p;
else
{j=i/2;
if(i%2==0) v[j]->lch=p;
else
v[j]->rch=p;
}
printf("\n 請繼續輸入二叉樹各結點的編號和對應的值：");
scanf("%d,%c",&i,&e);
}
return(t);
}
bitnode *creat_bt2()
{
bitnode *t;etype e;
scanf("%c",&e);
if(e=='#')
t=NULL;
else
{
t=(bitnode *)malloc(sizeof(bitnode));
t->data=e;
t->lch=creat_bt2();
t->rch=creat_bt2();
}
return(t);
}
void preorder(bitnode *p){
if(p)
{
printf("%3c",p->data);
preorder(p->lch);
preorder(p->rch);
}
}
void inorder(bitnode *p)
{
if(p){
inorder(p->lch);
printf("%3c",p->data);
inorder(p->rch);
}
}
void postorder(bitnode *p)
{
if(p)
{
postorder(p->lch);
postorder(p->rch);
printf("%3c",p->data);
}
}
void enqueue(bitree T)
{
if(front!=(rear+1)%m)
{rear=(rear+1)%m;
que[rear]=T;}
}
bitree delqueue()
{
if(front==rear)return NULL;
front=(front+1)%m;
return(que[front]);
}
void levorder(bitree T)
{
bitree p;
if(T)
{
enqueue(T);
while(front!=rear)
{
p=delqueue();
printf("%3c",p->data);
if(p->lch!=NULL)enqueue(p->lch);
if(p->rch!=NULL)enqueue(p->rch);
}
}
}
int treedepth(bitree bt)
{
int hl,hr,max;
if(bt!=NULL)
{
hl=treedepth(bt->lch);
hr=treedepth(bt->rch);
max=(hl>hr)? hl:hr;
return(max+1);
}
else
return(0);
}
void prtbtree(bitree bt,int level)
{
int j;
if(bt){
prtbtree(bt->rch,level+1);
for(j=0;j<=6*level+1;j++)printf(" ");
printf("%c\n",bt->data);
prtbtree(bt->lch,level+1);
}
}
void exchange(bitree bt)
{
bitree p;
if(bt)
{p=bt->lch;bt->lch=bt->rch;bt->rch=p;
exchange(bt->lch);exchange(bt->rch);
}
}
int leafcount(bitree bt)
{
if(bt!=NULL)
{
leafcount(bt->lch);
leafcount(bt->rch);
if((bt->lch==NULL)&&(bt->rch==NULL))
count++;
}
return(count);
}
void paintleaf(bitree bt)
{
if(bt!=NULL)
{
if(bt->lch==NULL&&bt->rch==NULL)
printf("%3c",bt->data);
paintleaf(bt->lch);
paintleaf(bt->rch);
}
}
『叄』 二叉樹遍歷方法有幾種
二叉樹遍歷方法最常用的大致有四種：
先序遍歷，也叫先根遍歷。就是先訪問根結點，再訪問左子樹，最後訪問右子樹。
中序遍歷，也叫中根遍歷。就是先訪問左子樹，再訪問根節點，最後訪問右子樹。
後序遍歷，也叫後根遍歷。就是先訪問左子樹，再訪問右子樹，最後訪問根結點。
按層次遍歷，就是對二叉樹從上到下訪問每一層，在每一層中都是按從左到右進行訪問該層中的每一個節點。
『肆』 二叉樹的層次遍歷
設計一個演算法層序遍歷二叉樹（同一層從左到右訪問）。思想：用一個隊列保存被訪問的當前節點的左右孩子以實現層序遍歷。
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"
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;
//結束
}
『陸』 求用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);
}
『柒』 二叉樹層次遍歷
/**
*層序遍歷
*/
voidLevelOrderTraversal(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實現二叉樹（模塊化集成，遍歷的遞歸與非遞歸實現）」，這是博客園的一個博文，裡面有關二叉樹的前中後層遍歷的遞歸與非遞歸演算法，比較全面。
『捌』 二叉樹的層次遍歷
二叉樹具有以下重要性質： 性質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是相鄰的兩個整數，故有 , 由此即得： 注意： 的證明【參見參考書目】
『玖』 什麼是樹的層次遍歷 要求通俗易懂
二叉樹的層次遍歷是指從二叉樹的第一層（根節點）開始，從上至下逐層遍歷，在同一層中，則按照從左到右的順序對節點逐個訪問。在逐層遍歷過程中，按從頂層到底層的次序訪問樹中元素，在同一層中，從左到右進行訪問。
其思想為：用一個隊列保存被訪問的當前節點的左右孩子以實現層序遍歷。在進行層次遍歷的時候，設置一個隊列結構，遍歷從二叉樹的根節點開始，首先將根節點指針入隊列，然後從隊頭取出一個元素，每取一個元素，執行下面兩個操作：
1、訪問該元素所指向的節點。
2、若該元素所指節點的左右孩子節點非空，則將該元素所指節點的左孩子指針和右孩子指針順序入隊。此過程不斷進行，當隊列為空時，二叉樹的層次遍歷結束。
(9)二叉樹層次遍歷演算法擴展閱讀
由於遍歷中所使用的數據結構是一個隊列而不是棧，因此寫一個按層遍歷的遞歸程序很困難。如下程序用來對二叉樹進行逐層遍歷，它採用了隊列數據結構。隊列中的元素指向二叉樹節點。當然，也可以採用公式化隊列。
程序中，僅當樹非空時，才進入w h i l e循環。首先訪問根節點，然後把其子節點加到隊列中。當隊列添加操作失敗時，由Add引發NoMem異常，由於沒有捕獲該異常，因此當異常發生時函數將退出。在把t的子節點加入隊列後，要從隊列中刪除t元素。