二叉樹的遍歷及線索化0001

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

2、存儲(chǔ)結(jié)構(gòu)并對(duì)她進(jìn)行中序線 索化以及遍歷算 法 描 述 及 實(shí) 驗(yàn) 步 驟1、typedef int TElemType;/定義了二叉樹的存儲(chǔ)結(jié)構(gòu) typedef struct BiTNodeTElemType data;/砧點(diǎn)域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、;/ 申請(qǐng)樹根結(jié)點(diǎn)空間T->data=ch;CreatBiTree(T->lchild);遞歸生成左子樹CreatBiTree(T->rchild);/遞歸生成右子樹2、/以遞歸先序遍歷為例void PreOrderTraverse(BiTree T,Status(*Visit)(TElemType e)if(T)Visit(T->data);/首先訪問根結(jié)點(diǎn)PreOrderTraverse(T->lchild,Visit);/然后遞歸遍歷左子樹 PreOrderTraverse(T->rchild,Visit);/最后遞歸遍歷右子樹/中序遍歷時(shí)先遞歸遍歷左

4、子樹，然后訪問根結(jié)點(diǎn)，最后遞歸遍歷 右子樹；后序遍歷"時(shí)先遞歸遍歷"左子樹，然后遞歸遍歷"右子樹，最后 訪問根結(jié)點(diǎn)3、/先把棧及隊(duì)列相關(guān)操作的頭文件包括進(jìn)來(lái)1)根指針入棧，2)向左走到左盡頭(入棧操作)3)出棧，訪問結(jié)點(diǎn)4)向右走一步，入棧，循環(huán)到第二步，直到?？?層次遍歷時(shí)，若樹不空，則首先訪問根結(jié)點(diǎn)，然后，依照其雙親結(jié) 點(diǎn)訪問的順序，依次訪問它們的左、右孩子結(jié)點(diǎn)；4.首先建立二叉線索存儲(chǔ)：包含數(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)行中序線索化，然后最后一個(gè)結(jié)點(diǎn)線索化調(diào)試過程及實(shí)驗(yàn)結(jié)果把測(cè)試數(shù)據(jù)放在f:filedata.txt里，測(cè)試數(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é)點(diǎn)是指訪問該結(jié)點(diǎn)的數(shù)據(jù)域，弄清楚各個(gè)指針?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;/單鏈隊(duì)列一一隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)typedef struct QNode QElemType data; QNode *next;*QueuePtr;struct LinkQueueQueuePtr front,rear;/ 隊(duì)頭、隊(duì)尾指針 ;錄void InitQueue(LinkQueue &Q) / 構(gòu)造一個(gè)空隊(duì)列 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的新的隊(duì)尾元素QueuePtr p;if(!(p=(QueuePtr)malloc(sizeof(QNode) / 存儲(chǔ)分配失敗 exit(OVERFLOW);p->data=e;p->next=NULL;Q.rear->next=p;Q.rear=p;Status DeQueue(LinkQueue &Q,QElemType &e) /若隊(duì)列不空、刪除Q的隊(duì)頭元素、用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為空隊(duì)列，則返回TRUE,否則返回FALSE if(Q.front->next=NULL)return TRUE;else return FALSE;/函數(shù)指針visit指向這個(gè)函數(shù) Status print(TEl

10、emType data) printf("%d",data); return OK;/創(chuàng)建一棵樹，字符代表結(jié)點(diǎn)，空格代表空樹 void CreatBiTree(BiTree &T)int ch;scanf("%d",&ch);if(ch=0)T=NULL;/這是一棵空樹 else T=(BiTNode *)malloc(sizeof(BiTNode);/ 申請(qǐng)結(jié)點(diǎn)空間，放樹 根結(jié)點(diǎn)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é)點(diǎn)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é)點(diǎn)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é)點(diǎn)/非遞歸的中序遍歷(利用棧)

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é)點(diǎn)、向Pop(S,p);if(!Visit(p->data)return ERROR;Push(S,p->rchild);return OK;/

14、層次遍歷(利用隊(duì)列)void BFSTraverse(BiTree T,Status (* Visit)(TElemType e)LinkQueue Q;QElemType p;InitQueue(Q);/置空的輔助隊(duì)列if(T)EnQueue(Q,T);朋艮結(jié)點(diǎn)入隊(duì)while(!QueueEmpty(Q)DeQueue(Q,p);/4寸頭出隊(duì)并置為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("請(qǐng)創(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;二叉樹的線索化/二叉樹的二叉線索存儲(chǔ)表示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é)點(diǎn) /先序創(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é)點(diǎn) Status InOrderThreading(BiThrTree &Thrt,BiThrTree T) (if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode) exit(OVERFLOW);Thrt->LTag=Link;Thrt->RTag=Thread;/處頭結(jié)點(diǎn)Thrt->rchild=Thrt;/ 右指針回指 if(!T)Thrt->lchild=Thrt;/若二叉樹為空，則左指針回指 else (Thrt->lchild=T;pre=Thrt;InThreading(T);/中序遍歷進(jìn)行中序線索化pre->rchild=Thrt; pre->RTag=Thread;/