1.實驗目的：
掌握二叉樹的結構特性以及二叉鏈表的存儲結構的特點及適用范圍。同時，掌握用指針類型描述、訪問和處理二叉樹的運算。

2.試驗問題：
建立一棵二叉樹，按層次遍歷該二叉樹，并顯示出這棵二叉樹。要求：以二叉鏈表作為存儲結構，按層次遍歷創建一棵二叉樹，從鍵盤接收輸入結點，用“A”,“B”,“C”,…來表示非空結點，用“*”來表示空結點，以“#”號結束，對此二叉樹進行層次遍歷并將遍歷結果輸出。

3.解題思路：
非遞歸層次遍歷二叉樹的算法基本思想：由層次遍歷的定義可知，層次遍歷是從根結點開始訪問，然后訪問它的左孩子和右孩子，接下來是它左孩子的左孩子和右孩子，右孩子的左孩子和右孩子，……，在訪問完某個結點后，一般不能馬上訪問它的左孩子和右孩子（除根結點等特殊情況外），需要把它的左右孩子信息保存起來。這種方式正好與隊列的操作特點吻合，所以可利用一個隊列結構來實現層次遍歷，其做法是：
1)首先將根結點入隊列；
2)當隊列不空，從對列中取出對頭結點訪問它，并在其左右孩子非空時，把它的左孩子和右孩子結點依次入隊列；
3)反復執行同樣操作，直到隊列為空時止。
用一維數組queue[MAXSIZE]實現循環隊列，變量front和rear為分別表示對頭指針和隊尾指針的指示器變量，并假定隊列有足夠的空間不會發生上溢。

4.程序實現：

#include "stdio.h" #include "malloc.h" #include "conio.h" #define MAXSIZE 100 typedef char elemtype;typedef struct btnode {elemtype data;struct btnode *lchild,*rchild; }bitnode,*bitree;typedef struct nodd {bitree addr;int parent; }sequre;bitree ins_node(bitree s,bitree t); void print_tree(bitree t); bitree create_ordbt(); sequre seq[MAXSIZE]; int n=0;bitree create_ordbt() {bitree t,s;elemtype x;t=NULL;printf("請按層次順序輸入結點1的值(以#號結束,*號為空的結點):\n");scanf("%c",&x);getchar();while(x!='#'){n++;if(x!='*'){s=(bitree)malloc(sizeof(bitnode));s->data=x;s->lchild=NULL;s->rchild=NULL;seq[n].addr=s;t=ins_node(s,t);}elseseq[n].addr=NULL;printf("請輸入結點%d的值（以#號結束，*號為空結點）：\n",n+1);x=getche();getchar();}return t; }bitree ins_node(bitree s,bitree t) {int kk;if(n==1)t=s;else{kk=n/2;if(n%2==0)seq[kk].addr->lchild=s;elseseq[kk].addr->rchild=s;}return t; }void print_tree(bitree t) {int i,j,k,nn,start,head,rear;sequre seqq[MAXSIZE];bitree p;if(t==NULL)return;head=0;nn=rear=0;seqq[rear].addr=t;for(;head<=rear && nn<MAXSIZE; head++){p=seqq[head].addr;if(p->lchild!=NULL)seqq[++rear].addr=p->lchild;if(p->rchild!=NULL)seqq[++rear].addr=p->rchild;}for(head=0,j=1,k=1;head <=rear;){printf("\n第%d層數據:",j);for(i=0,start=head;head<start+k;head++){printf("%c ",seqq[head].addr->data);if(seqq[head].addr->lchild==NULL)i=i-1;if(seqq[head].addr->rchild==NULL)i=i-1;}k=k*2+i;j++;} }main() {bitree tree;tree=create_ordbt();print_tree(tree); }

5.測試數據：

總結

以上是生活随笔為你收集整理的数据结构(三)打印二叉树中结点层次遍历序列的实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。