二叉樹的遍歷及線索化0001

1、青島理工大學(xué)數(shù)據(jù)結(jié)構(gòu)課程實驗報告課程名稱數(shù)據(jù)結(jié)構(gòu)班級網(wǎng)絡(luò)102實驗日期2012/4/26姓名徐夢婷學(xué)號201007110實驗成績實驗名稱二叉樹的遍歷及線索化實驗?zāi)康募耙笳莆找徊鏄涞慕?，用遞歸方法先序、中序、后序遍歷和非遞歸 的中序遍歷及層次遍歷還有二叉樹的線索化以及中序遍歷的算法及 代碼實現(xiàn)。實 驗 環(huán) 境硬件平臺：普通的PC機(jī)軟件平臺：Windows 2003操作系統(tǒng)編程環(huán)境：VisualC+實 驗 內(nèi) 容1、建立一棵二叉樹，定義它的鏈?zhǔn)酱鎯Y(jié)構(gòu)，包括數(shù)據(jù)域和指針域2、掌握用遞歸方法的前中后序遍歷3、掌握非遞歸的中序遍歷（利用棧）和層次遍歷（利用隊列）4、掌握二叉樹的線索化，定義二叉線索

2、存儲結(jié)構(gòu)并對她進(jìn)行中序線 索化以及遍歷算 法 描 述 及 實 驗 步 驟1、typedef int TElemType;/定義了二叉樹的存儲結(jié)構(gòu) typedef struct BiTNodeTElemType data;/砧點域struct BiTNode *lchild,*rchild;/ 左右孩子指針BiTNode,*BiTree;typedef BiTree SElemType;/用遞歸方法建立一棵一叉樹void CreatBiTree(BiTree &T)if(ch=0)T=NULL; 創(chuàng)建了一棵空樹elseT=(BiTNode *)malloc(sizeof(BiTNode)

3、;/ 申請樹根結(jié)點空間T->data=ch;CreatBiTree(T->lchild);遞歸生成左子樹CreatBiTree(T->rchild);/遞歸生成右子樹2、/以遞歸先序遍歷為例void PreOrderTraverse(BiTree T,Status(*Visit)(TElemType e)if(T)Visit(T->data);/首先訪問根結(jié)點PreOrderTraverse(T->lchild,Visit);/然后遞歸遍歷左子樹 PreOrderTraverse(T->rchild,Visit);/最后遞歸遍歷右子樹/中序遍歷時先遞歸遍歷左

4、子樹，然后訪問根結(jié)點，最后遞歸遍歷 右子樹；后序遍歷"時先遞歸遍歷"左子樹，然后遞歸遍歷"右子樹，最后 訪問根結(jié)點3、/先把棧及隊列相關(guān)操作的頭文件包括進(jìn)來1)根指針入棧，2)向左走到左盡頭(入棧操作)3)出棧，訪問結(jié)點4)向右走一步，入棧，循環(huán)到第二步，直到?？?層次遍歷時，若樹不空，則首先訪問根結(jié)點，然后，依照其雙親結(jié) 點訪問的順序，依次訪問它們的左、右孩子結(jié)點；4.首先建立二叉線索存儲：包含數(shù)據(jù)域，左右孩子指針以及左右標(biāo)志typedef enum Link=0,Thread=1 PointerTag;typedef struct BiThrNodeTElem

5、Type data;struct BiThrNode *lchild,*rchild;/ 左右孩子指針PointerTag LTag,RTag;/E 右標(biāo)志BiThrNode, *BiThrTree;建立前驅(qū)線索和后繼線索，并用中序遍歷進(jìn)行中序線索化，然后最后一個結(jié)點線索化調(diào)試過程及實驗結(jié)果把測試數(shù)據(jù)放在f:filedata.txt里，測試數(shù)據(jù)為:1 2 4 0 0 0 3 5 0 0 0育創(chuàng)建一樣杈寸二F面是遞歸方法的先序遍歷樹立F面是遞歸方法的 中序遍歷權(quán)寸宣. 12±53F面是遞歸方法的后序遍歷樹富.T面是三£遞歸的 中序遍歷樹工.F面是層次遍歷樹工- LN34sPi

6、'ess An u y 七o cone inue訪問結(jié)點是指訪問該結(jié)點的數(shù)據(jù)域，弄清楚各個指針?biāo)傅念愋徒Y(jié)附#include<queue> using namespace std;#include<stdio.h>#include<string.h>#include<stdlib.h>#include<math.h>#include"SqStack.h"typedef int Status;typedef int TElemType;/函數(shù)結(jié)果狀態(tài)代碼#define TRUE 1#define FALSE

7、0#define OK 1#define ERROR 0#define INFEASIBLE -1 typedef BiTree QElemType;/單鏈隊列一一隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)typedef struct QNode QElemType data; QNode *next;*QueuePtr;struct LinkQueueQueuePtr front,rear;/ 隊頭、隊尾指針 ;錄void InitQueue(LinkQueue &Q) / 構(gòu)造一個空隊列 Qif(!(Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode) exit(OV

8、ERFLOW);Q.front->next=NULL;void EnQueue(LinkQueue &Q,QElemType e) /插入元素e為Q的新的隊尾元素QueuePtr p;if(!(p=(QueuePtr)malloc(sizeof(QNode) / 存儲分配失敗 exit(OVERFLOW);p->data=e;p->next=NULL;Q.rear->next=p;Q.rear=p;Status DeQueue(LinkQueue &Q,QElemType &e) /若隊列不空、刪除Q的隊頭元素、用e返回其值、并返回OK、否則返回

9、ERROR QueuePtr p;if(Q.front=Q.rear)return ERROR;p=Q.front->next; e=p->data;Q.front->next=p->next;if(Q.rear=p)Q.rear=Q.front;free(p); return OK;Status QueueEmpty(LinkQueue Q) /若Q為空隊列，則返回TRUE,否則返回FALSE if(Q.front->next=NULL)return TRUE;else return FALSE;/函數(shù)指針visit指向這個函數(shù) Status print(TEl

10、emType data) printf("%d",data); return OK;/創(chuàng)建一棵樹，字符代表結(jié)點，空格代表空樹 void CreatBiTree(BiTree &T)int ch;scanf("%d",&ch);if(ch=0)T=NULL;/這是一棵空樹 else T=(BiTNode *)malloc(sizeof(BiTNode);/ 申請結(jié)點空間，放樹 根結(jié)點if(!T)exit(OVERFLOW);T->data=ch;CreatBiTree(T->lchild);遞歸生成左子樹CreatBiTree(

11、T->rchild);/遞歸生成右子樹 /void PreOrderTraverse(BiTree T,Status(*Visit)(TElemType e)if(T)Visit(T->data);/首先訪問根結(jié)點PreOrderTraverse(T->lchild,Visit);/然后遞歸遍歷左子樹PreOrderTraverse(T->rchild,Visit);/最后遞歸遍歷右子樹)/遞歸中序遍歷void InOrderTraverse(BiTree T,Status(*Visit)(TElemType e) if(T)/T不是空樹InOrderTraverse(

12、T->lchild,Visit);/首先遞歸遍歷左子樹Visit(T->data);/訪問根結(jié)點InOrderTraverse(T->rchild,Visit);/最后遞歸遍歷右子樹 )/遞歸后序遍歷void PostOrderTraverse(BiTree T,Status(*Visit)(TElemType e) if(T)PostOrderTraverse(T->lchild,Vis。/遞歸遍歷左子樹 PostOrderTraverse(T->rchild,Vis。/遞歸遍歷右子樹 Visit(T->data);/訪問根結(jié)點/非遞歸的中序遍歷(利用棧)

13、Status InOrderTraverse2(BiTree T,Status (* Visit)(TElemType e)SqStack S;InitStack(S);BiTree p;Push(S,T);僑艮指針入棧while(!StackEmpty(S)while(GetTop(S,p)&&p)Push(S,p->lchild);/向左走到盡頭Pop(S,p);/空指針退棧if(!StackEmpty(S)訪問結(jié)點、向Pop(S,p);if(!Visit(p->data)return ERROR;Push(S,p->rchild);return OK;/

14、層次遍歷(利用隊列)void BFSTraverse(BiTree T,Status (* Visit)(TElemType e)LinkQueue Q;QElemType p;InitQueue(Q);/置空的輔助隊列if(T)EnQueue(Q,T);朋艮結(jié)點入隊while(!QueueEmpty(Q)DeQueue(Q,p);/4寸頭出隊并置為pVisit(p->data );if(p->lchild)EnQueue(Q,p->lchild);if(p->rchild)EnQueue(Q,p->rchild);int main()freopen("

15、f:filedata.txt","r",stdin);BiTree T;printf("請創(chuàng)建一棵樹：n");CreatBiTree(T);printf("下面是遞歸方法的先序遍歷樹T.n");PreOrderTraverse(T,print);printf("下面是遞歸方法的中序遍歷樹T.n");InOrderTraverse(T,print);printf("下面是遞歸方法的后序遍歷樹T.n");PostOrderTraverse(T,print);printf("下面是

16、非遞歸的中序遍歷樹 T.n");InOrderTraverse2(T,print);printf("下面是層次遍歷樹T.n");BFSTraverse(T,print);return 0;二叉樹的線索化/二叉樹的二叉線索存儲表示typedef enum Link=0,Thread=1 PointerTag;Link=0:指針、Thread=1 線索 typedef struct BiThrNode (TElemType data;struct BiThrNode *lchild,*rchild;/ 左右孩子指針PointerTag LTag,RTag;/E 右標(biāo)志

17、 BiThrNode, *BiThrTree;Status print(TElemType data) (printf("%d",data); return OK;BiThrTree pre;/全局變量，始終指向p剛剛訪問過的結(jié)點 /先序創(chuàng)建一棵二叉樹 void CreatBiThrTree(BiThrTree &T) (int ch;scanf("%d",&ch);if(ch=0)T=NULL;/這是一棵空樹 else (T=(BiThrNode *)malloc(sizeof(BiThrNode);if(!T)exit(OVERFLO

18、W);T->data=ch;CreatBiThrTree(T->lchild);/創(chuàng)建左子樹 if(T->lchild)T->LTag=Link;CreatBiThrTree(T->rchild);/ 創(chuàng)建右子樹 if(T->rchild)T->RTag=Link; /遞歸線索化 void InThreading(BiThrTree p) (/pre=p;if(p)/p不為空樹 (InThreading(p->lchild);/ 左子樹線索化if(!p->lchild)/ 前驅(qū)線索 (p->LTag=Thread;p->lchi

19、ld=pre;)if(!pre->rchild)/ 后繼線索(pre->RTag=Thread;pre->rchild=p;)pre=p;/保持pre指向p的前驅(qū)InThreading(p->rchild);/ 右子樹線索化 )/中序遍歷二叉樹，并將其中序線索化，Thrt指向頭結(jié)點 Status InOrderThreading(BiThrTree &Thrt,BiThrTree T) (if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode) exit(OVERFLOW);Thrt->LTag=Link;Thrt->RTag=Thread;/處頭結(jié)點Thrt->rchild=Thrt;/ 右指針回指 if(!T)Thrt->lchild=Thrt;/若二叉樹為空，則左指針回指 else (Thrt->lchild=T;pre=Thrt;InThreading(T);/中序遍歷進(jìn)行中序線索化pre->rchild=Thrt; pre->RTag=Thread;/