二叉树的遍历及线索化

1、青岛理工大学数据结构课程实验报告课程名称数据结构班级网络102实验日期2012/4/26姓名徐梦婷学号201007110实验成绩实验名称二叉树的遍历及线索化实验目的及要求掌握一叉树的建立，用递归方法先序、中序、后序遍历和非递归 的中序遍历及层次遍历还有二叉树的线索化以及中序遍历的算法及 代码实现。实 验 环 境硬件平台：普通的PC机软件平台：Windows 2003操作系统编程环境：VisualC+实 验 内 容1、建立一棵二叉树，定义它的链式存储结构，包括数据域和指针域2、掌握用递归方法的前中后序遍历3、掌握非递归的中序遍历（利用栈）和层次遍历（利用队列）4、掌握二叉树的线索化，定义二叉线索

2、存储结构并对她进行中序线 索化以及遍历算 法 描 述 及 实 验 步 骤1、typedef int TElemType;/定义了二叉树的存储结构 typedef struct BiTNodeTElemType data;/砧点域struct BiTNode *lchild,*rchild;/ 左右孩子指针BiTNode,*BiTree;typedef BiTree SElemType;/用递归方法建立一棵一叉树void CreatBiTree(BiTree &T)if(ch=0)T=NULL; 创建了一棵空树elseT=(BiTNode *)malloc(sizeof(BiTNode)

3、;/ 申请树根结点空间T->data=ch;CreatBiTree(T->lchild);递归生成左子树CreatBiTree(T->rchild);/递归生成右子树2、/以递归先序遍历为例void PreOrderTraverse(BiTree T,Status(*Visit)(TElemType e)if(T)Visit(T->data);/首先访问根结点PreOrderTraverse(T->lchild,Visit);/然后递归遍历左子树 PreOrderTraverse(T->rchild,Visit);/最后递归遍历右子树/中序遍历时先递归遍历左

4、子树，然后访问根结点，最后递归遍历 右子树；后序遍历"时先递归遍历"左子树，然后递归遍历"右子树，最后 访问根结点3、/先把栈及队列相关操作的头文件包括进来1)根指针入栈，2)向左走到左尽头(入栈操作)3)出栈，访问结点4)向右走一步，入栈，循环到第二步，直到栈空/层次遍历时，若树不空，则首先访问根结点，然后，依照其双亲结 点访问的顺序，依次访问它们的左、右孩子结点；4.首先建立二叉线索存储：包含数据域，左右孩子指针以及左右标志typedef enum Link=0,Thread=1 PointerTag;typedef struct BiThrNodeTElem

5、Type data;struct BiThrNode *lchild,*rchild;/ 左右孩子指针PointerTag LTag,RTag;/E 右标志BiThrNode, *BiThrTree;建立前驱线索和后继线索，并用中序遍历进行中序线索化，然后最后一个结点线索化调试过程及实验结果把测试数据放在f:filedata.txt里，测试数据为:1 2 4 0 0 0 3 5 0 0 0育创建一样杈寸二F面是递归方法的先序遍历树立F面是递归方法的 中序遍历权寸宣. 12±53F面是递归方法的后序遍历树富.T面是三£递归的 中序遍历树工.F面是层次遍历树工- LN34sPi

6、'ess An u y 七o cone inue访问结点是指访问该结点的数据域，弄清楚各个指针所指的类型结附#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;/函数结果状态代码#define TRUE 1#define FALSE

7、0#define OK 1#define ERROR 0#define INFEASIBLE -1 typedef BiTree QElemType;/单链队列一一队列的链式存储结构typedef struct QNode QElemType data; QNode *next;*QueuePtr;struct LinkQueueQueuePtr front,rear;/ 队头、队尾指针 ;录void InitQueue(LinkQueue &Q) / 构造一个空队列 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;/函数指针visit指向这个函数 Status print(TEl

10、emType data) printf("%d",data); return OK;/创建一棵树，字符代表结点，空格代表空树 void CreatBiTree(BiTree &T)int ch;scanf("%d",&ch);if(ch=0)T=NULL;/这是一棵空树 else T=(BiTNode *)malloc(sizeof(BiTNode);/ 申请结点空间，放树 根结点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);/首先访问根结点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);/访问根结点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);/访问根结点/非递归的中序遍历(利用栈)

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)访问结点、向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);朋艮结点入队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("请创建一棵树：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 右标志

17、 BiThrNode, *BiThrTree;Status print(TElemType data) (printf("%d",data); return OK;BiThrTree pre;/全局变量，始终指向p刚刚访问过的结点 /先序创建一棵二叉树 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);/创建左子树 if(T->lchild)T->LTag=Link;CreatBiThrTree(T->rchild);/ 创建右子树 if(T->rchild)T->RTag=Link; /递归线索化 void InThreading(BiThrTree p) (/pre=p;if(p)/p不为空树 (InThreading(p->lchild);/ 左子树线索化if(!p->lchild)/ 前驱线索 (p->LTag=Thread;p->lchi

19、ld=pre;)if(!pre->rchild)/ 后继线索(pre->RTag=Thread;pre->rchild=p;)pre=p;/保持pre指向p的前驱InThreading(p->rchild);/ 右子树线索化 )/中序遍历二叉树，并将其中序线索化，Thrt指向头结点 Status InOrderThreading(BiThrTree &Thrt,BiThrTree T) (if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode) exit(OVERFLOW);Thrt->LTag=Link;Thrt->RTag=Thread;/处头结点Thrt->rchild=Thrt;/ 右指针回指 if(!T)Thrt->lchild=Thrt;/若二叉树为空，则左指针回指 else (Thrt->lchild=T;pre=Thrt;InThreading(T);/中序遍历进行中序线索化pre->rchild=Thrt; pre->RTag=Thread;/