二叉树的遍历及线索化.doc
青 岛 理 工 大 学数据结构课程实验报告课程名称数据结构班级网络102实验日期2012/4/26姓名徐梦婷学号201007110实验成绩实验名称二叉树的遍历及线索化实验目的及要求 掌握二叉树的建立，用递归方法先序、中序、后序遍历和非递归的中序遍历及层次遍历还有二叉树的线索化以及中序遍历的算法及代码实现。实验环境硬件平台：普通的PC机软件平台：Windows 2003操作系统 编程环境：VisualC+实验内容1、 建立一棵二叉树，定义它的链式存储结构，包括数据域和指针域2、 掌握用递归方法的前中后序遍历3、 掌握非递归的中序遍历（利用栈）和层次遍历（利用队列）4、 掌握二叉树的线索化，定义二叉线索存储结构并对她进行中序线索化以及遍历算法描述及实验步骤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);/申请树根结点空间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);/最后递归遍历右子树 /中序遍历时先递归遍历左子树，然后访问根结点，最后递归遍历右子树；后序遍历时先递归遍历左子树，然后递归遍历右子树，最后访问根结点3、/先把栈及队列相关操作的头文件包括进来 1）根指针入栈， 2）向左走到左尽头（入栈操作） 3）出栈，访问结点 4）向右走一步，入栈，循环到第二步，直到栈空/层次遍历时，若树不空，则首先访问根结点，然后，依照其双亲结点访问的顺序，依次访问它们的左、右孩子结点;4.首先建立二叉线索存储：包含数据域，左右孩子指针以及左右标志typedef enum Link=0,Thread=1 PointerTag;typedef struct BiThrNodeTElemType data;struct BiThrNode *lchild,*rchild;/左右孩子指针PointerTag LTag,RTag;/左右标志BiThrNode, *BiThrTree; 建立前驱线索和后继线索，并用中序遍历进行中序线索化，然后最后一个结点线索化调试过程及实验结果把测试数据放在f:filedata.txt里，测试数据为：1 2 4 0 0 0 3 5 0 0 0总结访问结点是指访问该结点的数据域，弄清楚各个指针所指的类型附录#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 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1typedef BiTree QElemType; / 单链队列队列的链式存储结构 typedef struct QNode QElemType data; QNode *next; *QueuePtr; struct LinkQueue QueuePtr front,rear; / 队头、队尾指针 ;void InitQueue(LinkQueue &Q) / 构造一个空队列Q if(!(Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode) exit(OVERFLOW); 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，否则返回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(TElemType data)printf("%d",data);return OK;/创建一棵树，字符代表结点，空格代表空树void CreatBiTree(BiTree &T)int ch;scanf("%d",&ch);if(ch=0)T=NULL;/这是一棵空树elseT=(BiTNode *)malloc(sizeof(BiTNode);/申请结点空间，放树根结点if(!T)exit(OVERFLOW);T->data=ch;CreatBiTree(T->lchild);/递归生成左子树CreatBiTree(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(T->lchild,Visit);/首先递归遍历左子树Visit(T->data);/访问根结点InOrderTraverse(T->rchild,Visit);/最后递归遍历右子树/递归后序遍历void PostOrderTraverse(BiTree T,Status(*Visit)(TElemType e)if(T)PostOrderTraverse(T->lchild,Visit);/递归遍历左子树PostOrderTraverse(T->rchild,Visit);/递归遍历右子树Visit(T->data);/访问根结点/非递归的中序遍历（利用栈）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;/层次遍历(利用队列)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);/对头出队并置为pVisit(p->data );if(p->lchild)EnQueue(Q,p->lchild);if(p->rchild)EnQueue(Q,p->rchild);int main()freopen("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("下面是非递归的中序遍历树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 BiThrNodeTElemType data;struct BiThrNode *lchild,*rchild;/左右孩子指针PointerTag LTag,RTag;/左右标志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;/这是一棵空树elseT=(BiThrNode *)malloc(sizeof(BiThrNode);if(!T)exit(OVERFLOW);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->lchild=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;/若二叉树为空，则左指针回指elseThrt->lchild=T;pre=Thrt;InThreading(T);/中序遍历进行中序线索化pre->rchild=Thrt; pre->RTag=Thread;/最后一个结点线索化Thrt->rchild=pre;return OK;/递归中序遍历Status InOrderTraverse_Thr(BiThrTree T,Status(*Visit)(TElemType e)/T指向头结点，头结点的左链lchild指向根结点BiThrTree p;p=T->lchild;/p指向根结点while(p!=T)/空树或遍历结束时，p=Twhile(p->LTag=Link)p=p->lchild;if(!Visit(p->data)return ERROR;/访问左子树为空的结点while(p->RTag=Thread&&p->rchild!=T)p=p->rchild;Visit(p->data);/访问后继结点p=p->rchild;return OK;int main()freopen("f:filedata.txt","r",stdin);BiThrTree T,Thrt;printf("请创建一棵树，以0代表空树。n");CreatBiThrTree(T);InOrderThreading(Thrt,T);printf("下面是中序遍历树S.n");InOrderTraverse_Thr(Thrt,print);printf("n");return 0;9
