二叉樹的建立及遍歷

二叉樹的建立及遍歷實(shí)驗(yàn)?zāi)康模赫莆諛湫谓Y(jié)構(gòu)的特點(diǎn)，二叉樹的存儲方式以及相應(yīng)操作。實(shí)驗(yàn)內(nèi)容：任務(wù)1：按先序遍歷序列建立二叉樹的二叉鏈表，已知先序序列為：ABCFFDEFGFFFFFFO(F表示空格)。并寫一個函數(shù)treenodes()統(tǒng)計(jì)該二叉樹的節(jié)點(diǎn)個數(shù)。如果有可能，寫一個輸出函數(shù)treeprint()用樹形結(jié)構(gòu)打印出該二叉樹。任務(wù)2：編寫出按照層次遍歷的思想對樹的左孩子右兄弟表示方法的存儲結(jié)構(gòu)進(jìn)行逐層遍歷的算法，并給出測試程序及運(yùn)行結(jié)果。任務(wù)3：編寫出在利用四個數(shù)組表示一個二叉樹的存儲結(jié)構(gòu)的情況下，根據(jù)給定序號找出所有祖先節(jié)點(diǎn)的算法，設(shè)計(jì)出先序、中序及后序遍歷的遞歸算法并根據(jù)給定的數(shù)據(jù)給出測試結(jié)果。［說明］以上任務(wù)中選做2個，計(jì)算機(jī)各專業(yè)及電控學(xué)院學(xué)生必須選擇任務(wù)2作為任務(wù)之一。其他理工科各專業(yè)學(xué)生任意選擇2個，文科學(xué)生選任務(wù)1或任務(wù)3之一。程序代碼：#include"stdio.h"#include"stdlib.h"#include"malloc.h"typedefcharTElemType; 〃定義數(shù)據(jù)的類型typedefstructBiTNode〃二叉樹的結(jié)點(diǎn){TElemTypedata;structBiTNode*lchild,*rchild;}BiTNode;typedefstructQNode〃隊(duì)列{BiTNodedata;structQNode*next;}Queue;typedefstruct〃隊(duì)列的頭指針和尾指針{Queue*front;Queue*rear;}LinkQueue;intJT=0;BiTNode*CreateBiTree()〃先序建立二叉樹{TElemTypech;BiTNode*T;scanf("%c",&ch);if(ch=='')T=NULL;elseif(!(T=(BiTNode*)malloc(sizeof(BiTNode))))exit(0);〃內(nèi)存分配失敗，退出T->data=ch;JT++;T->lchild=CreateBiTree();/建立左子樹T->rchild=CreateBiTree();/建立右子樹}returnT;〃建立成功返回二叉樹}intInitQueue(LinkQueue*Q)//初始化隊(duì)列{Q->front=Q->rear=(Queue*)malloc(sizeof(Queue));if(!Q->front)exit(0); 〃內(nèi)存分配失敗退出Q->front->next=NULL;return1; 〃初始化成功返回1}intEnQueue(LinkQueue*Q,BiTNodee)〃向隊(duì)列中插入元素{Queue*p;p=(Queue*)malloc(sizeof(Queue));if(!p)exit(0);p->data=e;p->next=NULL;Q->rear->next=p;Q->rear=p;return1; 〃插入成功返回1}intDeQueue(LinkQueue*Q,BiTNode*e)〃出隊(duì){Queue*p;if(Q->front==Q->rear) 〃隊(duì)列為空return0;p=Q->front->next;*e=p->data;Q->front->next=p->next;if(Q->rear==p)Q->rear=Q->front;free(p);return1;〃出隊(duì)成功返回1intEmptyQueue(LinkQueue*Q) //判斷隊(duì)列是否為空隊(duì)列if(Q->rear==Q->front)〃為空返回1return1;elsereturn0;voidLevelTraverse(BiTNode*T) 〃隊(duì)列的層次遍歷{LinkQueueQ;BiTNode*p;InitQueue(&Q);EnQueue(&Q,*T);P=T;while(!EmptyQueue(&Q)){DeQueue(&Q,p);printf("%c",p->data);if(p->lchild)EnQueue(&Q,*p->lchild);if(p->rchild)EnQueue(&Q,*p->rchild);voidPreOrderTraverse(BiTNode*btn) 〃遞歸先序遍歷{if(btn!=NULL){printf("%c",btn->data);PreOrderTraverse(btn->lchild);PreOrderTraverse(btn->rchild);}}voidInOrderTraverse(BiTNode*btn)〃遞歸中序遍歷{if(btn!=NULL){InOrderTraverse(btn->lchild);printf("%c",btn->data);InOrderTraverse(btn->rchild);voidPostOrderTraverse(BiTNode*btn)〃遞歸后序遍歷{if(btn!=NULL){PostOrderTraverse(btn->lchild);PostOrderTraverse(btn->rchild);printf("%c",btn->data);}}main(){BiTNode*btn;printf("\n輸入二叉樹空節(jié)點(diǎn)輸"”：\n");btn=CreateBiTree();printf("\n遞歸先序遍歷二叉樹的結(jié)果:\n");PreOrderTraverse(btn); 〃遞歸先序遍歷建立的二叉樹printf("\n遞歸中序遍歷二叉樹的結(jié)果:\n");InOrderTraverse(btn);printf("\n遞歸后序遍歷二叉樹的結(jié)果:\n");PostOrderTraverse(btn);printf("\n二叉樹的結(jié)點(diǎn)數(shù)為:％d\n"JT); 〃二叉樹結(jié)點(diǎn)的數(shù)目printf("\n層次遍歷二叉樹的結(jié)果:\n");LevelTraverse(btn);printf("\n");}結(jié)果：可"C:\u5er5\Admini5trator\De5kto件夷、二s■樹的遞歸逼歷.非遞歸遍I五和層次遍I五I口II回IIk^I腌入二叉樹空節(jié)點(diǎn)輸“”:abdehjcfigk歸先序遍歷二